BFS解决边长为1的单源最短路径

⬅ 返回

1、例题

2、思路

3、图的存储

4、代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#define PI 3.14159
using namespace std;
 
typedef pair<int, int> PII;
typedef long long LL;
const int MAX_INT = 0x3f3f3f3f;
const int N = 1e5 + 15;
const int mod = 1e9 + 7;
//---------------------------------------------------------
//邻接表
int n;
int g[N];//g[i]存储的顶点i所能到达的结点号
int e[N];//e[i]即结点i所对应的顶点号
int ne[N];//下一个顶点
int idx=1;//结点号
queue<int> q;
int status[N];
int dist[N];
//---------------------------------------------------------
 
void bfs(){
 
    q.push(1);
    status[1] = 1;
    dist[1] = 0;
 
    while(q.size())
    {
        auto t = q.front();//t为当前顶点号
        q.pop();
        for(int i=g[t];i!=-1;i=ne[i])
        {
            int u = e[i];//取出顶点
            if(status[u]==0){
                status[u]=1;
                q.push(u);
                dist[u] = dist[t] + 1; 
            } 
        }
 
    }
 
}
void solve()
{
    memset(g,-1,sizeof g);
    memset(dist,0x3f,sizeof dist);
    int m;
    cin>>n>>m;
    while(m--)
    {
        int a,b;
        cin>>a>>b;//从a到b的边 
        e[idx] = b;
        ne[idx]=g[a];
        g[a] = idx++;
    }
    bfs();
    if(dist[n]==MAX_INT)
        cout<<-1<<endl;
    else
        cout<<dist[n]<<endl;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int T = 1;
    while (T--)
    {
        solve();
    }
}