题解：B4292 [蓝桥杯青少年组省赛 2022] 路线

LotleTos · 2025-04-02 17:00:22 · 题解

由于道路是双向的，所以求每个点到点 n 的距离就是求点 n 到那个点的距离。

考虑使用广度优先搜索，从节点 n 开始搜索，这样一路搜下去，就能求出所有能到达的节点的距离了，把答案数组初始化为 -1，这样不能到达就能直接输出了。

代码

#include<bits/stdc++.h>
using namespace std;
vector<int> a[110];
int ans[110];
bool b[110];
queue<int> q;
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int x,y;
        cin>>x>>y;
        a[x].push_back(y); 
        a[y].push_back(x); 
    }
    for(int i=1;i<=n;i++){
        ans[i]=-1;
    }
    ans[n]=0;
    q.push(n);
    b[n]=1;
    while(q.size()){
        int x;
        x=q.front();
        q.pop();
        for(int i=0;i<a[x].size();i++){
            if(b[a[x][i]]==0){
                q.push(a[x][i]);
                b[a[x][i]]=1;
                ans[a[x][i]]=ans[x]+1;
            }
        }
    }
    for(int i=1;i<n;i++){
        cout<<ans[i]<<" ";
    }
}