题解 | #跑酷大湿#

J

路径搜索

• n：节点数量（位置）
• m：火源数量
• s：玩家起始位置
• fire：火源位置数组
• g：无向图的邻接表表示

第一步：计算火势蔓延距离（BFS）

vector<int> fd(n+1,1e9);  // 火到达每个节点的最短时间
queue<int> q;
for(auto x:fire){ fd[x]=0; q.push(x); }
while(!q.empty()){
    int u=q.front(); q.pop();
    for(auto v:g[u]) if(fd[v]>fd[u]+1){ fd[v]=fd[u]+1; q.push(v); }
}

• 从所有火源开始多源BFS
• 计算火到达每个节点的最短时间

第二步：玩家逃生路径搜索（BFS）

vector<int> sd(n+1,1e9);  // 玩家到达每个节点的最短时间
q.push(s);
sd[s]=0;

// 特殊检查：如果起点是叶子节点且没有火，直接成功
if(g[s].size()<=1 && fd[s]>0){ cout<<0; return 0; }

while(!q.empty()){
    int u=q.front(); q.pop();
    for(auto v:g[u]){
        // 关键条件：玩家能比火先到达v，且不会在到达时遇到火
        if(sd[v]>sd[u]+1 && sd[u]+1<fd[v]){
            sd[v]=sd[u]+1;
            // 如果到达叶子节点，逃生成功
            if(g[v].size()==1){ cout<<sd[v]; return 0; }
            q.push(v);
        }
    }
}

逃生条件：

1. 时间优势：sd[u]+1 < fd[v] - 玩家到达下一节点的时间必须早于火势
2. 安全边界：到达叶子节点（g[v].size() == 1）即视为逃生成功
3. 起点检查：如果起点就是叶子节点且没有火，直接逃生成功

• 时间复杂度：O(n + m) - 两次BFS遍历
• 空间复杂：O(n + m) - 存储图和距离数组
• 策略：玩家必须始终比火势快一步，最终到达地图边界（叶子节点）

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n,m,s;
    cin>>n>>m>>s;
    vector<int> fire(m);
    for(int i=0;i<m;i++) cin>>fire[i];
    vector<vector<int>> g(n+1);
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    vector<int> fd(n+1,1e9), sd(n+1,1e9);
    queue<int> q;
    for(auto x:fire){ fd[x]=0; q.push(x); }
    while(!q.empty()){
        int u=q.front(); q.pop();
        for(auto v:g[u]) if(fd[v]>fd[u]+1){ fd[v]=fd[u]+1; q.push(v); }
    }
    if(g[s].size()<=1 && fd[s]>0){ cout<<0; return 0; }
    q.push(s);
    sd[s]=0;
    while(!q.empty()){
        int u=q.front(); q.pop();
        for(auto v:g[u]){
            if(sd[v]>sd[u]+1 && sd[u]+1<fd[v]){
                sd[v]=sd[u]+1;
                if(g[v].size()==1){ cout<<sd[v]; return 0; }
                q.push(v);
            }
        }
    }
    cout<<-1;
}