给定一个 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号节点能否到n号节点 的 最短距离，广度优先遍历即可。
思路步骤：
-
用 d 数组保存1号节点到各个节点的距离，初始时，都是 -1。
-
用 st 数组标记各个节点有没有走到过。
-
从 1 号节点开始，广度优先遍历：
-
1 号节点入队列，dist[1] 的值更新为 0。
-
如果队列非空，就取出队头，找到队头节点能到的所有节点。如果队头节点能到走到的节点没有标记过，就将节点的dist值更新为队头的dist值+1，然后入队。
-
重复步骤 2 直到队列为空。
-
这个时候，d 数组中就存储了 1 号节点到各个节点的距离了。如果距离是无穷大，则不能到达，输出 -1，如果距离不是无穷大，则能到达，输出距离。
图的存储： 邻接表， 单链表形式
-
用 h 数组保存各个节点能到的第一个节点的编号。开始时，h[i] 全部为 -1。
-
用 e 数组保存节点编号，ne 数组保存 e 数组对应位置的下一个节点所在的索引。
-
用 idx 保存下一个 e 数组中，可以放入节点位置的索引
-
插入边使用的头插法，例如插入：a->b。首先把b节点存入e数组，e[idx] = b。然后 b 节点的后继是h[a]，ne[idx] = h[a]。最后，a 的后继更新为 b 节点的编号，h[a] = idx，索引指向下一个可以存储节点的位置，idx ++ 。
下面代码看似有一丢丢长，实际上的核心代码就6行。所以说需要牢记
code:
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N = 100010;
int n, m;
int h[N], e[N], ne[N], idx; //邻接表数据结构
int d[N]; //存储节点1到n的距离
void add(int a, int b) // 邻接表存储模版
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
int bfs()
{
memset(d, -1, sizeof d); // 初始化距离
queue<int> q;
d[1] = 0; // 初始化节点1的距离为0
q.push(1); // 放入初始化条件
while(q.size())
{
int t = q.front(); // 取出队头
q.pop();
//=============================================================================================
// ne[i]上的点都是与i节点距离为1的点
for(int i = h[t]; i != -1; i = ne[i]) //遍历所有t节点能到的点，i为节点索引
{
// 向外走一步
int j = e[i]; //通过索引i得到t能到的节点编号
if(d[j] == -1) //如果没有遍历过
{
d[j] = d[t] + 1; // 因为路径长度都是1，所以直接在上一步的基础上加上1即可
q.push(j); // 将j加到队列中
}
}
}
return d[n];
//=================================================================================================
}
int main()
{
cin >> n >> m;
memset(h, -1, sizeof h);
for(int i =0; i < m; i ++)
{
int a, b;
cin >> a >> b;
add(a, b);
}
cout << bfs() << endl;
return 0;
}