题解 | #【模板】单源最短路1#

#include <bits/stdc++.h>
using namespace std;
const int MAX=5010;
vector<int> a[MAX];//存储无向边
bool mark[5010];//标记边是否已被遍历
int bfs(int b,int d)
{
    queue<pair<int,int>> q;//使用先进先出的队列进行bfs
    q.push({b,0});//pair储存当前位置和已走距离
    mark[b]=true;//更新点状态
    while(!q.empty())
    {
        int x=q.front().first;
        int y=q.front().second;
        q.pop();//将点出队
        if(x==d)
            return y;
        else
            for(int i=0;i<a[x].size();i++)
                if(!mark[a[x][i]])
                {
                    mark[a[x][i]]=true;//更新点状态
                    q.push({a[x][i],y+1});//将点入队
                }
    }
    return -1;//未能到达终点
}
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=0;i<m;i++)
    {
        int u,v;
        cin>>u>>v;
        a[u].push_back(v);
        a[v].push_back(u);
    }
    for(int i=0;i<=n+1;i++)
        mark[i]=false;//标记点状态
    int result=bfs(1,n);
    cout<<result;
    return 0;
}