Evacuation Plan [第五回 アルゴリズム実技検定 I]

https://atcoder.jp/contests/past202012-open/tasks/past202012_i

前提知識

• bfs

解説

https://atcoder.jp/contests/past202012-open/submissions/22291597

標高が設定されているが、計算途中に変化したりはしないので、水路と標高を合わせて
有向グラフと考えることで標高のことは一旦忘れることにする。
この問題は終点が複数個所与えられていて、そこに最短経路でどうやって移動できるかを考える問題である。
各辺の重みは1で固定なので最短経路問題ではあるが、bfsで解くことができる。
今回のように終点から始点を逆算するような場合でも同様にbfsで解くことができる。
頂点を逆に移動していく必要があるので、有向グラフではあるが、辺の向きを逆にしておこう。
あとはオーソドックスにbfsしていけばいい。

int N, M, K, H[201010], C[201010];
int ans[201010];
vector<int> E[201010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M >> K;
    rep(i, 0, N) cin >> H[i];
    rep(i, 0, N) ans[i] = inf;
    queue<int> que;
    rep(i, 0, K) {
        cin >> C[i]; C[i]--;
        ans[C[i]] = 0;
        que.push(C[i]);
    }
    rep(i, 0, M) {
        int a, b; cin >> a >> b;
        a--; b--;
        if (H[a] < H[b]) E[a].push_back(b);
        else E[b].push_back(a);
    }
    
    while (!que.empty()) {
        int cu = que.front();
        que.pop();

        fore(to, E[cu]) if (ans[to] == inf) {
            ans[to] = ans[cu] + 1;
            que.push(to);
        }
    }

    rep(i, 0, N) {
        if (ans[i] == inf) printf("-1\n");
        else printf("%d\n", ans[i]);
    }
}