AcWing 847. 图中点的层次
原题链接
简单
作者:
HUE菜鸡联盟
,
2021-12-06 19:12:57
,
所有人可见
,
阅读 96
#include<iostream>
#include<algorithm>
#include<vector>
#include<math.h>
#include<queue>
#include<stack>
#include<string.h>
#define for0(x,n) for(int x=0;x<n;x++)
#define for1(x,n) for(int x=1;x<=n;x++)
using namespace std;
typedef long long ll;//long long
typedef pair<double,double>PDD;
typedef pair<int,int> PII;
const int tt=1e5+10,mod=1e9+7,INF=0x7f7f7f7f7f7f7f7f;
int n,m;
int ans=0;
vector<int>G[tt];
queue<int>q;
int vis[tt];
int d[tt];
void bfs(int x,int y)
{
q.push(x);
while(!q.empty())
{
int now=q.front();
q.pop();
for0(i,G[now].size())
{
int to=G[now][i];
if(d[to]<=d[now]+1)continue;
d[to]=min(d[to],d[now]+1);
q.push(to);
}
// for1(i,n)cout<<d[i]<<' ';cout<<endl;
}
}
int main()
{
cin>>n>>m;
for0(i,n+1)d[i]=INF;
for0(i,m)
{
int x,y;
cin>>x>>y;
G[x].push_back(y);
}
d[1]=0;
bfs(1,0);
d[n]==INF?cout<<-1:cout<<d[n];
}