题目描述
图中点的层次详细注释版
样例
#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号点到各个点的距离
void add(int a, int b)
{
e[idx] = b; ne[idx] = h[a]; h[a] = idx++; //建立邻接表
}
int bfs()
{
memset(d, -1, sizeof d);//初始化 使没有遍历到的点到1点都是-1
d[1] = 0;
queue<int>q;//创建一个队列、
q.push(1);//1点进入队列
while (q.size())//如果队列不为空
{
int t = q.front();//取出队列首个元素
q.pop();//弹出队列元素
for (int i = h[t];i != -1;i = ne[i])//遍历这个点相连的点
{
int j = e[i];
if (d[j] == -1)//j这个点没有被便利过
{
d[j] = d[t] + 1;
q.push(j);//j进队
}
}
}
return d[n];
}
int main()
{
cin >> n >> m;
memset(h, -1, sizeof h);//初始化邻接表
while(m--)
{
int a, b;
cin >> a >> b;
add(a, b);
}
cout << bfs() << endl;
return 0;
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla