AcWing 847. 图中点的层次(带注释)
原题链接
简单
作者:
容验
,
2020-12-27 13:11:21
,
所有人可见
,
阅读 321
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int n,m;//n点数,m边数
int h[N],e[N],ne[N],idx;//h[a]中存放的是点a邻接点的地址
int d[N],q[N];//距离和维护的队列
void add(int a,int b){
e[idx]=b, ne[idx]=h[a] , h[a]=idx++ ;
}
int bfs(){
int hh=0,tt=0;
while(hh<=tt){//hh兜底,tt在前探索的双指针操作法
int a=q[hh++];//取出队列头元素
for(int i=h[a];i!=-1;i=ne[i]){//h[a]中存放的是a的第一个邻接点地址i
int j=e[i];
if(d[j]==-1){//倘若j没有被遍历过
d[j]=d[a]+1;//在a点到1的距离基础上加一
q[++tt]=j;
}
}
}
return d[n];
}
int main(){
cin>>n>>m;
memset(h,-1,sizeof h); //使邻接链表的尾节点都为-1
for(int i=0 ; i<m ; i++){
int a,b;
cin>>a>>b;
add(a,b);
}
memset(d,-1,sizeof d);// d=-1表示没有被遍历过
q[0]=1;//将一号元素加入队列
d[1]=0;//一号元素到自身的距离是0
bfs();
cout<<bfs()<<endl;
return 0;
}