概要

この問題は、火災が発生している部屋を避けながら、すべての避難者が非常出口である部屋 \(T\) に避難するために必要な最小ターン数を求める問題です。 避難者同士は互いに干渉しないため、それぞれの避難者が「火災の部屋を避けた最短経路」で部屋 \(T\) を目指すときの、最大所要時間を求める問題に帰着されます。

考察

1. 避難者の独立性

問題文より、「各避難者の行動は互いに影響しません」とあります。同じ部屋に何人いてもよく、廊下ですれ違うことも可能です。 したがって、各避難者は他の避難者を気にする必要がなく、自分にとっての最短ルートで非常出口 \(T\) へ向かえばよいことになります。 全員が避難を完了するまでの最小ターン数は、「各避難者が \(T\) に到達するのにかかるターン数」の最大値となります。

2. 火災の部屋の扱い

火災が発生している部屋に入ると即座に脱落してしまいます。また、火災の部屋を「通過」することもできません。 これは、グラフ上で火災の部屋が「通行禁止の障害物（壁）」になっていると考えることができます。 したがって、火災の部屋を一切通らないような経路のみを考える必要があります。

3. 効率的な最短経路の求め方

素朴な方法として、避難者 \(i\)（\(1 \le i \le K\)）ごとに、初期位置 \(S_i\) から \(T\) への最短経路を幅優先探索（BFS）などで求めるとどうなるでしょうか？ 避難者の数 \(K\) は最大で \(2 \times 10^5\)、グラフの探索には \(O(N + M)\) かかるため、全体の計算量は \(O(K(N + M))\) となり、実行時間制限に間に合いません（TLE）。

ここで、「すべての避難者の目的地が同じ部屋 \(T\) である」という点に注目します。 スタート地点を各避難者の初期位置とするのではなく、ゴールである部屋 \(T\) を始点として1回だけ幅優先探索（BFS）を行うことで、部屋 \(T\) からすべての部屋への最短距離を一度に求めることができます。 グラフは双方向に移動可能（無向グラフ）であるため、「\(T\) から各部屋への最短距離」はそのまま「各部屋から \(T\) への最短距離」と一致します。

アルゴリズム

1. 初期チェック: 避難者の初期位置 \(S_i\) の中に、火災が発生している部屋 \(P_j\) が含まれているかを確認します。もし含まれていれば、その避難者は開始時点で即座に脱落するため、避難は不可能です。この時点で -1 を出力して終了します。

2. 逆方向からの幅優先探索（BFS）: 非常出口 \(T\) を始点として、キューを用いた幅優先探索（BFS）を行います。

   • 各部屋への最短距離を記録する配列 dist を \(-1\) で初期化します。
   • dist[T] = 0 とし、キューに \(T\) を追加します。
   • キューから部屋 \(u\) を取り出し、隣接する部屋 \(v\) を探索します。
   • もし \(v\) が火災の部屋でなく、かつ未訪問（dist[v] == -1）であれば、dist[v] = dist[u] + 1 と更新してキューに \(v\) を追加します。

3. 答えの集計: 各避難者 \(i\) について、初期位置からの最短距離 dist[S[i]] を確認します。

   • もし dist[S[i]] == -1 の場合、その避難者は火災を避けて \(T\) に到達することができません。この場合は -1 を出力して終了します。
   • 到達可能な場合は、dist[S[i]] の最大値を答えの候補として更新していきます。

4. 出力: すべての避難者が到達可能であれば、求めた最大値を出力します。

計算量

• 時間計算量: \(O(N + M + K + Q)\)

  • 隣接リストの構築に \(O(M)\)、火災の部屋のフラグ設定に \(O(Q)\) かかります。
  • 非常出口 \(T\) からのBFSは、各頂点と各辺を最大1回ずつ走査するため \(O(N + M)\) です。
  • 各避難者の初期位置のチェックと最大値の集計に \(O(K)\) かかります。
  • 全体として線形時間で動作するため、制約 \(2 \times 10^5\) に対して十分高速に実行できます。

• 空間計算量: \(O(N + M)\)

  • グラフを表現する隣接リストに \(O(N + M)\)、最短距離を記録する dist 配列や火災フラグの保持に \(O(N)\) のメモリを使用します。

実装のポイント

• 火災の部屋の高速な判定: 「ある部屋 \(v\) が火災かどうか」を毎回 \(P\) の中から探すと時間がかかります。サイズ \(N + 1\) の真偽値（boolean）の配列 is_fire を用意し、is_fire[p] = true としておくことで、\(O(1)\) で判定できるようにしています。

• 到達不可能な場合の処理: グラフが連結であっても、火災の部屋によって進路が塞がれ、非常出口 \(T\) にたどり着けない部屋が存在する可能性があります。BFSの初期値 -1 のまま更新されなかった部屋に避難者がいる場合は、到達不可能（-1）と正しく判定する必要があります。

  ソースコード

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int main() {
    // 高速な入出力
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M, K, Q, T;
    if (!(cin >> N >> M >> K >> Q >> T)) return 0;

    vector<vector<int>> adj(N + 1);
    for (int i = 0; i < M; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    vector<int> S(K);
    for (int i = 0; i < K; ++i) {
        cin >> S[i];
    }

    vector<bool> is_fire(N + 1, false);
    for (int i = 0; i < Q; ++i) {
        int p;
        cin >> p;
        is_fire[p] = true;
    }

    // 初期位置が火災の発生している部屋である避難者がいる場合、即座に脱落
    for (int i = 0; i < K; ++i) {
        if (is_fire[S[i]]) {
            cout << -1 << "\n";
            return 0;
        }
    }

    // 非常出口 T からの最短経路を BFS で求める（火災の部屋は避ける）
    vector<int> dist(N + 1, -1);
    queue<int> q;

    dist[T] = 0;
    q.push(T);

    while (!q.empty()) {
        int u = q.front();
        q.pop();

        for (int v : adj[u]) {
            if (!is_fire[v] && dist[v] == -1) {
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }

    int ans = 0;
    for (int i = 0; i < K; ++i) {
        if (dist[S[i]] == -1) {
            // 到達不可能な避難者がいる場合
            cout << -1 << "\n";
            return 0;
        }
        ans = max(ans, dist[S[i]]);
    }

    cout << ans << "\n";

    return 0;
}

この解説は gemini-3.5-flash-thinking によって生成されました。