AOJ 0623 Zombie Island

問題文

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0623

解法

危険な街を列挙さえすれば，あとはただの単一始点最短路問題．
危険な街を列挙するには，ゾンビに支配された街を全て，最初にqueueにプッシュしておくだけで十分である．

計算量は O(N + MlogN)

ソースコード

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pll = pair<ll, ll>;

constexpr ll INF = 1e18;

int main() {
    int N, M, K, S;
    ll P, Q;
    cin >> N >> M >> K >> S;
    cin >> P >> Q;

    vector<ll> zd(N, INF);
    queue<int> que1;
    for(int i=0; i<K; ++i) {
        int c;
        cin >> c;
        c--;
        que1.push(c);
        zd[c] = 0;
    }

    vector<vector<int>> g(N);
    for(int i=0; i<M; ++i) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    while(!que1.empty()) {
        int v = que1.front();
        que1.pop();
        for(auto to : g[v]) {
            if(zd[to] == INF) {
                zd[to] = zd[v] + 1;
                que1.push(to);
            }
        }
    }

    vector<ll> d(N, INF);
    d[0] = 0;
    priority_queue<pll, vector<pll>, greater<pll>> que;
    que.push(make_pair(0, 0));
    while(!que.empty()) {
        pll p = que.top();
        que.pop();
        int v = p.second;
        if(d[v] < p.first) {
            continue;
        }
        for(auto to : g[v]) {
            if(zd[to] == 0) {
                continue;
            }
            ll cost = to == N-1 ? 0 : (zd[to] > S ? P : Q);
            if(d[to] > d[v] + cost) {
                d[to] = d[v] + cost;
                que.push(make_pair(d[to], to));
            }
        }
    }
    cout << d[N-1] << endl;
}