AcWing 847. 图中点的层次
原题链接
简单
作者:
尼古拉斯小布丁
,
2021-08-26 16:44:46
,
所有人可见
,
阅读 196
AcWing 847.图中点的层次
/*
AcWing 847.图中点的层次
因为这个图的所有边权重都是1, 所以可用宽搜求最短距离
queue <--- 1
while(queue不空){
t <--- 队头
拓展t所有邻点
if(x未遍历){
queue<--- x
d[x] = d[t]+1
}
}
对于这个版本的代码的理解并不深刻,第一次不是自己写出来的,对于数组模拟邻接表还有些困惑
主要是针对idx++这行代码、idx是全局变量这样写, 就表明其他单链表h[x]它的头节点不是从0开始
与第一个单链表的头节点从数组下标0开始不一样,有些不太适应
*/
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 100010;
int n,m;
int h[N], e[N], ne[N], idx;
int q[N], dist[N]; //数组模拟的队列; 每个节点距离1号店的最短距离
/* 添加一条边a->b
e[idx] 指的是a点所连接的点,即b点
ne[a] 指的是a点的上一条边的编号
h[a] 中存的就是a点的边的编号,即idx
idx 为每一条边的编号
*/
void add(int a, int b){
e[idx] = b, ne[idx]=h[a], h[a]=idx++;
}
int bfs(){
int hh=0, tt=0;
q[0] = 1;
memset(dist, -1, sizeof dist);
dist[1] = 0;
while(hh<=tt){
int t = q[hh++];
for(int i=h[t];i!=-1;i=ne[i]){
int j = e[i];
if(dist[j]==-1){
dist[j]=dist[t]+1;
q[++tt]=j;
}
}
}
return dist[n];
}
int main(){
cin>>n>>m;
int a,b;
memset(h, -1, sizeof h);
for(int i=0;i<m;i++){
cin>>a>>b;
add(a, b);
}
cout<<bfs()<<endl;
return 0;
}