AcWing0847 图中点的层次
给定一个 n 个点 m 条边的有向图,图中可能存在重边和自环。
所有边的长度都是 1 ,点的编号为 1∼n 。
请你求出 1 号点到 n 号点的最短距离,如果从 1 号点无法走到 n 号点,输出 −1 。
输入格式
第一行包含两个整数 n 和 m 。
接下来 m 行,每行包含两个整数 a 和 b,表示存在一条从 a 走到 b 的长度为 1 的边。
输出格式
输出一个整数,表示 1 号点到 n 号点的最短距离。
数据范围
1 ≤ n , m ≤ 10^5
输入样例:
4 5
1 2
2 3
3 4
1 3
1 4
输出样例:
1
算法思想:
采用BFS来求解单源最短路径。 int dist[1..n]
维护所有顶点到原点的最短路径长度。
根据BFS遍历所有节点。对于每一个结点 u
,遍历其所有孩子节点。访问每一个孩子节点 v
时,若该节点时首次访问,则更新其路径长度,即 dist[v] = dist[u] + 1
。
若到达节点 n ,则返回当前路径长度。否则,即所有可达节点已访问,则返回 -1 。
算法1-BFS(105 ms):
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 100000, M = 100000;
int n, idx;
int first[N + 1], ne[M + 1], vertex[M + 1];
void addEdge(int a, int b) {
vertex[++idx] = b;
ne[idx] = first[a];
first[a] = idx;
}
int BFS() {
queue<int> que;
int dist[N + 1];
for (int i = 1; i <= n; ++i) {
dist[i] = -1;
}
// 源点入队
que.push(1);
dist[1] = 0;
while (que.size()) {
int u = que.front();
que.pop();
// 遍历 u 的所有出边
for (int i = first[u]; i; i = ne[i]) {
int v = vertex[i];
if (dist[v] == -1) {
que.push(v);
dist[v] = dist[u] + 1;
}
// 如果到达终点,返回当前距离
if (v == n) {
return dist[v];
}
}
}
// 若所有可达点已遍历,返回 -1
return -1;
}
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
int m;
cin >> n >> m;
while (m--) {
int a, b;
cin >> a >> b;
addEdge(a, b);
}
cout << BFS();
return 0;
}