AcWing 847. 图中点的层次

给定一个n个点m条边的有向图,图中可能存在重边和自环。

所有边的长度都是1,点的编号为1~n。

请你求出1号点到n号点的最短距离,如果从1号点无法走到n号点,输出-1。

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
int h[N],ne[N],to[N],d[N],num,x,y,n,m;
queue<int>q;
void add(int u,int v)
{
    ne[++num]=h[u];
    to[num]=v;
    h[u]=num;
}
int bfs(int s)
{
    for(int i=2;i<=n;++i)d[i]=-1;
    q.push(s);d[1]=0;
    while(!q.empty())
    {
        int u=q.front();q.pop();
        if(u==n)return d[n];
        for(int i=h[u];i;i=ne[i])
        {
            int v=to[i];
            if(d[v]==-1)
            {
                d[v]=d[u]+1;
                q.push(v);
            }
        }
    }return -1;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i){scanf("%d%d",&x,&y);add(x,y);}
    cout<<bfs(1)<<endl;    
    return 0;
}

 

AcWing 847. 图中点的层次

上一篇:C#读写txt文件方法汇总


下一篇:c#常用文件操作