题目描述
给定一个 n 个点 m 条边的有向图,图中可能存在重边和自环。
所有边的长度都是 1,点的编号为 1∼n。
请你求出 1 号点到 n 号点的最短距离,如果从 1 号点无法走到 n 号点,输出 −1。
输入格式
第一行包含两个整数 n 和 m。
接下来 m 行,每行包含两个整数 a 和 b,表示存在一条从 a 走到 b 的长度为 1 的边。
输出格式
输出一个整数,表示 1 号点到 n 号点的最短距离。
数据范围
1≤n,m≤10^5
输入样例:
4 5
1 2
2 3
3 4
1 3
1 4
输出样例:
1
算法
BFS+数组模拟
C++ 代码
//此题要求的是最短路所以用BFS
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int hh,tt,idx,n,m;//hh,tt队头队尾,idx每++一次即多一条边
int d[N],h[N],e[N],ne[N],q[N];//d数组存步数,h数组形成一个邻接表头部,
void add(int a,int b){//e存的表示以h【n】中n为起始点与它相邻的点的编号有那些,ne相当于单链表的next指针,q数组模拟队列
e[idx]=b;
ne[idx]=h[a];
h[a]=idx++;//add函数将h(head)数组对应的头n是图中编号为n的结点相邻的点存到对应的单链表中
}
void bfs(){
q[0]=1,d[1]=0;//初始令第一个顶点入队列,并使顶点1的步数为0表示从1开始
while(hh<=tt){//当队列不为空
int t=q[hh++];//取出队头元素并弹出队头元素
for(int i=h[t];i!=-1;i=ne[i]){//遍历以n为结点的单链表,找到与之相邻的点的编号e[i]
int j=e[i];//j代表与t相邻的点的编号
if(d[j]==-1){//如果这个点没有走过,则步数+1,就标记为已经走过,遇到重边与环会因为不满足条件跳过
d[j]=d[t]+1;//步数加1
q[++tt]=j;//把这个点存进队列,等到若干次循环我们就会判断该点相邻的点有没有n,第一次遇到我们就会给它
//赋值d[n],后面再遇到必定更大,我们就不必考虑了,因为这是一层层的遍历,第二次到n时不满足,
// 也不会继续赋值给它
}
}
}
}
int main(){
ios::sync_with_stdio(false);//cin,cout加速
cin.tie(0);
cout.tie(0);
cin>>n>>m;
memset(h,-1,sizeof(h));//初始化
memset(d,-1,sizeof(d));
for(int i=0;i<m;i++){//插入边
int a,b;
cin>>a>>b;
add(a,b);
}
bfs();//经过一次bfs找到从1到1~n所有步数最短路用d数组存储,没有就用-1输出
cout<<d[n]<<endl;
return 0;
}