概要

ビル内の避難者全員が、火災の部屋を避けながら非常出口に到達できるか判定し、可能なら全員が避難完了するまでの最小ターン数を求める問題です。

考察

重要な気づき：避難者同士は互いに影響しない

問題文に「廊下や部屋に通行人数の上限はなく」「各避難者の行動は互いに影響しません」と明記されています。これは非常に重要な条件で、各避難者は独立に最短経路で避難できることを意味します。

つまり、避難者 \(i\) にとっての最適行動は、火災の部屋を避けながら部屋 \(T\) への最短経路を進むことです。

答えの導出

各避難者が独立に動けるため： - 避難者 \(i\) が避難完了するまでの最小ターン数 = 火災の部屋を通らない \(S_i\) から \(T\) への最短距離 - 全員の避難完了までの最小ターン数 = 全避難者の中での最大値

もし火災を避けて \(T\) に到達できない避難者が1人でもいれば、答えは \(-1\) です。

なぜ火災の部屋を「通過」できないか

1ターンで移動できるのは隣接する部屋1つまでです。火災の部屋に移動した時点で脱落チェックにより脱落するため、火災の部屋を経由地として通り抜けることは不可能です。したがって、火災の部屋を完全に除外したグラフ上での最短距離を求めればよいです。

アルゴリズム

1. いずれかの避難者の初期位置が火災の部屋なら、即座に -1 を出力
2. 非常出口 \(T\) を始点として、火災の部屋を除外したグラフ上でBFS（幅優先探索）を行い、各部屋への最短距離を求める
3. 全避難者の初期位置 \(S_i\) について：
   • \(S_i = T\) ならターン \(0\) で避難完了（距離 \(0\)）
   • \(S_i\) に到達できない（距離が未定義）なら -1 を出力
   • そうでなければ距離を記録
4. 全避難者の距離の最大値が答え

具体例

部屋が5つあり、\(T = 1\)、火災が部屋3で発生している場合：

1 - 2 - 3 - 4 - 5

部屋3が火災なので、部屋4や5から部屋1へは到達不可能（部屋3を通過できない）。部屋4や5に避難者がいれば答えは -1 です。

計算量

• 時間計算量: \(O(N + M + K)\)
  • BFS: \(O(N + M)\)
  • 各避難者の距離確認: \(O(K)\)
• 空間計算量: \(O(N + M)\)
  • 隣接リスト: \(O(N + M)\)
  • 距離配列: \(O(N)\)

実装のポイント

• BFSの始点を \(T\)（出口）にすることで、各部屋から \(T\) への距離を一度のBFSで全て計算できる（無向グラフなので \(T\) からの距離 = \(T\) への距離）

• 火災の部屋は BFS の訪問対象から除外する（v not in fire の条件）

• 火災の部屋を set で管理することで、判定を \(O(1)\) で行える

• \(Q = 0\) の場合（火災なし）の空行入力に注意が必要だが、split() で読み込めば問題ない

  ソースコード

import sys
from collections import deque

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    K = int(input_data[idx]); idx += 1
    Q = int(input_data[idx]); idx += 1
    T = int(input_data[idx]); idx += 1
    
    adj = [[] for _ in range(N + 1)]
    for _ in range(M):
        u = int(input_data[idx]); idx += 1
        v = int(input_data[idx]); idx += 1
        adj[u].append(v)
        adj[v].append(u)
    
    S = []
    for i in range(K):
        S.append(int(input_data[idx])); idx += 1
    
    fire = set()
    for i in range(Q):
        fire.add(int(input_data[idx])); idx += 1
    
    # Check if any evacuee starts on fire
    for s in S:
        if s in fire:
            print(-1)
            return
    
    # BFS from T, avoiding fire rooms
    dist = [-1] * (N + 1)
    dist[T] = 0
    queue = deque()
    queue.append(T)
    
    while queue:
        u = queue.popleft()
        for v in adj[u]:
            if dist[v] == -1 and v not in fire:
                dist[v] = dist[u] + 1
                queue.append(v)
    
    ans = 0
    for s in S:
        if s == T:
            continue
        if dist[s] == -1:
            print(-1)
            return
        if dist[s] > ans:
            ans = dist[s]
    
    print(ans)

main()

---

この解説は claude4.6opus-thinking によって生成されました。