题目描述
给定一个n个点m条边的有向图，图中可能存在重边和自环。
所有边的长度都是1，点的编号为1~n。
请你求出1号点到n号点的最短距离，如果从1号点无法走到n号点，输出-1。
输入格式
第一行包含两个整数n和m。
接下来m行，每行包含两个整数a和b，表示存在一条从a走到b的长度为1的边。
输出格式
输出一个整数，表示1号点到n号点的最短距离。
数据范围
1≤n,m≤105
输入样例
4 5
1 2
2 3
3 4
1 3
1 4
输出样例
1
算法1
方法
邻接表&数组模拟队列
C++ 代码
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=1e5+10;
int q[N],d[N]; //q[]存储当前队列走到的数值，d[]记录当前点到第1个点的距离
int h[N],e[N],ne[N],idx; //h[]表示链表头结点，e[]存储当前这个结点的元素,ne[]存储当前这个结点到的下一个结点的坐标，idx表示当前用到了第几个点，因为是有向图，最大是N
int n,m; //n是结点个数，m是边的条数
void add(int a,int b) //将b插入到a的数组中，详情请看yxc的单链表讲解视频，（网址附下）
{
e[idx]=b; //在b的链表头插入a，在当前结点存下数值b
ne[idx]=h[a]; //让当前结点的next指针指向头结点指向的点
h[a]=idx; //将头结点的next指针指向的点指向当前这个点
idx++; //让idx往后增加
}
int bfs() //输出结点n到结点1的最短距离
{
int hh=0,tt=0; //hh代表队列的头结点，tt代表队列的尾结点
q[0]=1; //让第0个位置为数值1
memset(d,-1,sizeof d);//初始化d数组，让每一个距离都为-1，用来查看当前这个数值有没有被走过
d[1]=0; //让第一个点的距离为0
while(hh<=tt) //如果队列不是空的，模拟队列详情请看yxc的模拟队列讲解视频，（网址附下）
{
int t=q[hh++]; //t存下当前队列头结点的数值，头结点再往后走
for(int i=h[t];i!=-1;i=ne[i]) //将当前的t的点为链表头，开始遍历链表
{
int j=e[i]; //用j将当前链表的元素存下
if(d[j]==-1) //如果当前这个结点的数值没有被走过
{
d[j]=d[t]+1; //这个数值到1的距离等于链表头距离加上1
q[++tt]=j; //将tt往前挪（挪之前tt<hh），挪到当前hh的位置，存储下当前这个j值
}
}
}
return d[n]; //返回第n个点距离第1个点的最短距离
}
int main()
{
scanf("%d%d",&n,&m); //输入结点数n和边的条数m
memset(h,-1,sizeof h); //将所有链表头都初始化为空（等于-1）
for(int i=0;i<m;i++) //循环m次，输入m条边
{
int a,b;
scanf("%d%d",&a,&b);
add(a,b); //将b插入a
}
printf("%d",bfs()); //输出第n个点距离第1个点的最短距离
return 0;
}
