代码
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
const int N = 1e5 + 10;
int head[N], e[N], ne[N],idx;
int n, m;
int dist[N];
void add(int a, int b)
{
e[idx] = b;
ne[idx] = head[a];
head[a] = idx++;
}
int bfs()
{
queue<int> q;
memset(dist, -1, sizeof dist); // todo 初始化距离
q.push(1);
dist[1] = 0; //? 最开始的时候 只有第一个点被遍历过了 他的距离是 0
while (q.size()) {
auto t = q.front(); // todo 每一次取得我们的队头
q.pop();
for (int i = head[t]; i != -1; i = ne[i]) {
int j = e[i];
if (dist[j] == -1) //! 如果 j 没有被扩展过
{
dist[j] = dist[t] + 1;
q.push(j);
}
}
}
return dist[n]; //! 返回最后一个搜到的点的距离
}
int main()
{
cin >> n >> m;
memset(head, -1, sizeof head);
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
add(a, b);
}
cout << bfs() << endl;
return 0;
}
int j = e[i];
为什么不是 j = ne[i] 呀??用j来表示 i这个点的值
ne[i]表示模拟邻接表里面的指针,指向下一个元素
为什么没有加add(b,a)呢?
他是有向图呀
q[]数组存的啥啊?
队列, bfs是用队列来维护的,所以这里使用 q[ ] 来用数组模拟了一个队列
你这个add的写法,好像是从b到a的边吧?
# 连接一条 从a 到 b 的边