题目描述
给定一个 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
(树与图的广度优先遍历) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int e[N],ne[N],h[N],idx;
int n,m;
int d[N];
void add(int a,int b)//构造临接链表
{
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int bfs()
{
queue<int> p;
p.push(1);//从1开始到n
memset(d,-1,sizeof d);//初始化d为-1,而d[1]=0,1到本身的距离为0
d[1]=0;
while(!p.empty())
{
int t=p.front();
p.pop(); //for循环是两边搜,即广搜
for(int i=h[t];i!=-1;i=ne[i])//遍历临接链表
{ //牢记:i是地址不是节点上的数
int j=e[i];//记录i地址对应的节点上的数
if(d[j]==-1)//没被遍历过
{
d[j]=d[t]+1;
p.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;
}
//错点:1(36)记得初始化h为-1;
// 2(23)int j=e[i]而不是h[i];
//总结反思:1、
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla