AcWing 847. 图中点的层次
原题链接
简单
作者:
墨白
,
2021-01-06 12:39:01
,
所有人可见
,
阅读 282
C++ 代码
#include <iostream>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 100010,M = N*2;
int n,m;
int e[N],ne[N],h[N],idx;
bool st[N];
int dis[N];
void add(int a, int b){
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
queue<int> q;
int main(){
cin >> n >> m;
q.push(1);
memset(dis,-1,sizeof dis);
memset(h,-1,sizeof h);
dis[1] = 0;
while(m--){
int a, b;
cin >> a >> b;
add(a,b);
}
while(!q.empty()){
int iter = q.front();
q.pop();
for(int i = h[iter];i != -1;i = ne[i]){
int j = e[i];
if(dis[j] == -1) {
q.push(j);
dis[j] = dis[iter] + 1;
}
}
}
cout << dis[n] <<endl;
return 0;
}