【题目来源】
AcWing：847. 图中点的层次 - AcWing题库
【题目描述】
给定一个\(n\)个点\(m\)条边的有向图，图中可能存在重边和自环。所有边的长度都是\(1\)，点的编号为\(1\sim n\)。请你求出\(1\)号点到\(n\)号点的最短距离，如果从\(1\)号点无法走到\(n\)号点，输出\(-1\)。
【输入】
第一行包含两个整数\(n\)和\(m\)。
接下来\(m\)行，每行包含两个整数\(a\)和\(b\)，表示存在一条从\(a\)走到\(b\)的长度为\(1\)的边。
【输出】
输出一个整数，表示\(1\)号点到\(n\)号点的最短距离。
【输入样例】
4 5
1 2
2 3
3 4
1 3
1 4
【输出样例】
1
【算法标签】
《AcWing 847 图中点的层次》 #BFS#
【代码详解】
// 使用STL队列
#include <bits/stdc++.h>
using namespace std;const int N = 100010; // 节点最大数量
int n, m; // n: 节点数量，m: 边数量
int h[N], e[N], ne[N], idx; // 邻接表存储图，h: 头节点数组，e: 边终点数组，ne: 下一条边数组，idx: 边计数器
int d[N]; // 记录从起点到每个节点的距离
bool st[N]; // 记录节点是否被访问过
queue<int> q; // BFS队列// 添加一条有向边 a->b
void add(int a, int b)
{e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}// 广度优先搜索，返回从节点1到节点n的最短距离
int bfs()
{st[1] = true; // 标记起点为已访问q.push(1); // 起点入队memset(d, -1, sizeof(d)); // 初始化距离为-1（表示不可达）d[1] = 0; // 起点距离为0while (!q.empty()){int t = q.front(); // 取出队首节点q.pop();// 遍历当前节点的所有邻接节点for (int i = h[t]; i != -1; i = ne[i]){int j = e[i]; // 邻接节点编号if (!st[j]) // 如果邻接节点未被访问{st[j] = true; // 标记为已访问d[j] = d[t] + 1; // 更新距离q.push(j); // 入队}}}return d[n]; // 返回到达节点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; // 输出从1到n的最短距离return 0;
}
// 数据模拟队列
#include <bits/stdc++.h>
using namespace std;const int N = 100010; // 节点最大数量
int n, m; // n: 节点数量，m: 边数量
int h[N], e[N], ne[N], idx; // 邻接表存储图，h: 头节点数组，e: 边终点数组，ne: 下一条边数组，idx: 边计数器
int d[N], q[N]; // d: 记录从起点到每个节点的距离，q: 数组模拟队列// 添加一条有向边 a->b
void add(int a, int b)
{e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}// 广度优先搜索，返回从节点1到节点n的最短距离
int bfs()
{int hh = 0, tt = 0; // 队列头尾指针q[0] = 1; // 起点入队memset(d, -1, sizeof(d)); // 初始化距离为-1（表示不可达）d[1] = 0; // 起点距离为0while (hh <= tt) // 队列不为空{int t = q[hh++]; // 取出队首节点// 遍历当前节点的所有邻接节点for (int i = h[t]; i != -1; i = ne[i]){int j = e[i]; // 邻接节点编号if (d[j] == -1) // 如果邻接节点未被访问{d[j] = d[t] + 1; // 更新距离q[++tt] = j; // 入队}}}return d[n]; // 返回到达节点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; // 输出从1到n的最短距离return 0;
}
【运行结果】
4 5
1 2
2 3
3 4
1 3
1 4
1