Overview

This problem asks for the minimum number of turns required for all evacuees to reach room \(T\) (the emergency exit) while avoiding rooms that are on fire. Since evacuees do not interfere with each other, the problem reduces to finding the maximum time required when each evacuee heads toward room \(T\) via the “shortest path that avoids rooms on fire.”

Analysis

1. Independence of Evacuees

According to the problem statement, “each evacuee’s actions do not affect others.” Any number of people can be in the same room, and they can pass each other in corridors. Therefore, each evacuee does not need to worry about other evacuees and can simply take their own shortest route to the emergency exit \(T\). The minimum number of turns until everyone has evacuated is the maximum value of “the number of turns it takes for each evacuee to reach \(T\)”.

2. Handling Rooms on Fire

Entering a room on fire causes immediate elimination. Also, it is not possible to “pass through” a room on fire. This can be thought of as rooms on fire acting as “impassable obstacles (walls)” on the graph. Therefore, we only need to consider paths that do not pass through any room on fire.

3. Efficient Shortest Path Computation

As a naive approach, what happens if we compute the shortest path from each evacuee \(i\) (\(1 \le i \le K\)) from their initial position \(S_i\) to \(T\) using breadth-first search (BFS)? The number of evacuees \(K\) can be up to \(2 \times 10^5\), and graph traversal takes \(O(N + M)\), so the total computation is \(O(K(N + M))\), which will not fit within the time limit (TLE).

Here, we focus on the key observation that “all evacuees have the same destination, room \(T\)”. Instead of starting from each evacuee’s initial position, we can perform BFS just once starting from the goal room \(T\), which allows us to compute the shortest distance from room \(T\) to all rooms at once. Since the graph allows bidirectional movement (undirected graph), “the shortest distance from \(T\) to each room” is exactly equal to “the shortest distance from each room to \(T\).”

Algorithm

1. Initial Check: Check whether any evacuee’s initial position \(S_i\) is a room \(P_j\) that is on fire. If so, that evacuee is immediately eliminated at the start, making evacuation impossible. Output -1 and terminate.

2. Reverse BFS (Breadth-First Search): Perform BFS using a queue starting from the emergency exit \(T\).

   • Initialize the array dist that records the shortest distance to each room with \(-1\).
   • Set dist[T] = 0 and add \(T\) to the queue.
   • Dequeue a room \(u\) and explore adjacent rooms \(v\).
   • If \(v\) is not a room on fire and has not been visited (dist[v] == -1), update dist[v] = dist[u] + 1 and add \(v\) to the queue.

3. Aggregating the Answer: For each evacuee \(i\), check the shortest distance from their initial position dist[S[i]].

   • If dist[S[i]] == -1, that evacuee cannot reach \(T\) while avoiding fires. In this case, output -1 and terminate.
   • If reachable, update the answer candidate with the maximum value of dist[S[i]].

4. Output: If all evacuees can reach the exit, output the computed maximum value.

Complexity

• Time Complexity: \(O(N + M + K + Q)\)

  • Building the adjacency list takes \(O(M)\), and setting fire room flags takes \(O(Q)\).
  • BFS from the emergency exit \(T\) visits each vertex and each edge at most once, so it is \(O(N + M)\).
  • Checking each evacuee’s initial position and aggregating the maximum takes \(O(K)\).
  • Overall, it runs in linear time, which is sufficiently fast for constraints of \(2 \times 10^5\).

• Space Complexity: \(O(N + M)\)

  • The adjacency list representing the graph uses \(O(N + M)\), and the dist array for recording shortest distances and the fire flags use \(O(N)\) memory.

Implementation Notes

• Fast determination of rooms on fire: Searching through \(P\) every time to check “whether a room \(v\) is on fire” would be time-consuming. By preparing a boolean array is_fire of size \(N + 1\) and setting is_fire[p] = true, we can determine this in \(O(1)\).

• Handling unreachable cases: Even if the graph is connected, rooms on fire may block paths, making it possible that some rooms cannot reach the emergency exit \(T\). If an evacuee is in a room that remained at the initial value of -1 (never updated by BFS), it must be correctly determined as unreachable (-1).

  Source Code

#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;
}

This editorial was generated by gemini-3.5-flash-thinking.