概要

本問題は、火災が発生している部屋（障害物）を避けながら、複数の避難者（スタート地点）が非常出口 \(T\)（ゴール地点）へ避難するために必要な最小ターン数を求める問題です。全員が避難を完了するまでの時間は、各避難者が非常出口に到達するまでにかかる時間の「最大値」となります。

考察

1. 避難者同士の独立性

問題文より、「各避難者の行動は互いに影響しません」とあります。したがって、避難者ごとに「非常出口 \(T\) までに何ターンかかるか」を独立に計算し、その中の最大値を求めればよいことになります。

2. 火災の部屋の扱い

火災が発生している部屋に侵入すると脱落してしまいます。したがって、火災が発生している部屋は「通行不可能な障害物（壁）」とみなすことができます。 また、避難者の初期位置がすでに火災の部屋である場合は、シミュレーション開始時に即座に脱落するため、この時点で全員の避難は不可能（答えは -1）となります。

3. 素朴なアプローチと高速化

各避難者のスタート地点 \(S_i\) から非常出口 \(T\) への最短経路を、避難者ごとに幅優先探索（BFS）などで求めるとどうなるでしょうか。 避難者の数 \(K\)、部屋の数 \(N\)、廊下の数 \(M\) はそれぞれ最大で \(2 \times 10^5\) です。避難者ごとに BFS を行うと、最悪の場合の時間計算量は \(O(K(N + M))\) となり、実行時間制限（TLE）に間に合いません。

ここで、「ゴールから逆方向に探索する」という逆転の発想をします。 スタート地点は \(K\) 個ありますが、ゴール地点（非常出口 \(T\)）は 1つだけ です。 非常出口 \(T\) を始点として、火災の部屋を避けるようにして1回だけ BFS を行えば、すべての部屋から \(T\) への最短距離を \(O(N + M)\) で一挙に求めることができます。

アルゴリズム

1. 初期チェック: 避難者の初期位置 \(S_i\) の中に、火災が発生している部屋 \(P_j\) が含まれているかを判定します。含まれている場合は、避難不可能として即座に -1 を出力して終了します。

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

   • 距離配列 dist を \(-1\) で初期化し、dist[T] = 0 とします。
   • キューに \(T\) を追加します。
   • キューから部屋 \(u\) を取り出し、隣接する部屋 \(v\) について以下をチェックします。
     • 部屋 \(v\) で火災が発生していない。
     • 部屋 \(v\) が未訪問（dist[v] == -1）である。
     • 条件を満たす場合、dist[v] = dist[u] + 1 と更新し、キューに \(v\) を追加します。

3. 答えの集計: 各避難者の初期位置 \(S_i\) について、dist[S_i] を確認します。

   • dist[S_i] == -1 の避難者が1人でもいれば、その避難者は非常出口にたどり着けないため -1 を出力します。
   • すべての避難者が到達可能な場合、dist[S_i] の最大値が求める最小ターン数となります。

計算量

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

  • グラフの構築に \(O(M)\)、火災の位置の記録に \(O(Q)\) かかります。
  • 非常出口 \(T\) からの BFS は、各頂点と各辺を最大1回ずつ走査するため \(O(N + M)\) です。
  • 各避難者の初期位置のチェックおよび最大値の集計に \(O(K)\) かかります。
  • 全体として \(O(N + M + K)\) となり、実行時間制限に対して十分に高速です。

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

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

実装のポイント

• 初期位置がゴールのケース: 最初から非常出口 \(T\) にいる避難者は 0 ターンで避難完了となります。BFS の初期条件で dist[T] = 0 と設定しているため、このケースも特別扱いすることなく正しく処理できます。

• 高速な入出力: Python では入力数が多いため、sys.stdin.read().split() を用いてすべての入力を一度に読み込むことで、入出力によるオーバーヘッドを減らすことができます。

  ソースコード

import sys
from collections import deque


def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    N = int(input_data[0])
    M = int(input_data[1])
    K = int(input_data[2])
    Q = int(input_data[3])
    T = int(input_data[4])

    adj = [[] for _ in range(N + 1)]
    idx = 5
    for _ in range(M):
        u = int(input_data[idx])
        v = int(input_data[idx + 1])
        adj[u].append(v)
        adj[v].append(u)
        idx += 2

    S = [int(x) for x in input_data[idx : idx + K]]
    idx += K

    fire = [False] * (N + 1)
    for _ in range(Q):
        p = int(input_data[idx])
        fire[p] = True
        idx += 1

    # 初期位置が火災の部屋である避難者がいるかチェック
    for s in S:
        if fire[s]:
            print(-1)
            return

    # TからBFSで最短経路を求める
    dist = [-1] * (N + 1)
    dist[T] = 0
    queue = deque([T])

    while queue:
        u = queue.popleft()
        d = dist[u]
        for v in adj[u]:
            if not fire[v] and dist[v] == -1:
                dist[v] = d + 1
                queue.append(v)

    # 各避難者の最短ターンの最大値を求める
    ans = 0
    for s in S:
        if dist[s] == -1:
            print(-1)
            return
        if dist[s] > ans:
            ans = dist[s]

    print(ans)


if __name__ == "__main__":
    solve()

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