【题目来源】
AcWing：851. spfa求最短路 - AcWing题库
【题目描述】
给定一个\(n\)个点\(m\)条边的有向图，图中可能存在重边和自环，边权可能为负数。请你求出\(1\)号点到\(n\)号点的最短距离，如果无法从\(1\)号点走到\(n\)号点，则输出 impossible。数据保证不存在负权回路。
【输入】
第一行包含整数\(n\)和\(m\)。接下来\(m\)行每行包含三个整数 \(x,y,z\)，表示存在一条从点\(x\)到点\(y\)的有向边，边长为\(z\)。
【输出】
输出一个整数，表示\(1\)号点到\(n\)号点的最短距离。如果路径不存在，则输出 impossible。
【输入样例】
3 3
1 2 5
2 3 -3
1 3 4
【输出样例】
2
【解题思路】
【算法标签】
《AcWing 851 SPFA求最短路》 #最短路# #spfa#
【代码详解】
#include <bits/stdc++.h>
using namespace std;// 定义常量
const int N = 100010, M = N, INF = 1e9; // N为节点数上限，M为边数上限，INF为无穷大// 定义邻接表相关数组
int h[N], e[M], w[M], ne[M], idx; // h存储每个节点的第一条边的索引，e存储边的终点，w存储边的权重，ne存储下一条边的索引，idx为边的计数器
int dist[N]; // dist存储从起点到每个节点的最短距离
queue<int> q; // 队列用于广度优先搜索
bool st[N]; // st标记节点是否在队列中// 定义节点数和边数
int n, m;// 添加边的函数
void add(int a, int b, int c) {e[idx] = b, w[idx] = c; // 设置边的终点和权重ne[idx] = h[a], h[a] = idx++; // 更新邻接表
}// SPFA算法实现
int spfa() {fill(dist, dist + N, INF); // 初始化距离为无穷大dist[1] = 0; // 起点距离设为0q.push(1); // 将起点加入队列st[1] = true; // 标记起点在队列中while (!q.empty()) {int nd = q.front(); q.pop(); // 取出队首元素st[nd] = false; // 标记该节点不在队列中for (int i = h[nd]; i != -1; i = ne[i]) { // 遍历所有邻接边int j = e[i]; // 邻接节点if (dist[j] > dist[nd] + w[i]) { // 如果通过当前节点到达邻接节点更近dist[j] = dist[nd] + w[i]; // 更新最短距离if (!st[j]) { // 如果邻接节点不在队列中q.push(j); // 将邻接节点加入队列st[j] = true; // 标记邻接节点在队列中}}}}return dist[n]; // 返回从起点到终点的最短距离
}// 主函数
int main() {cin >> n >> m; // 输入节点数和边数memset(h, -1, sizeof(h)); // 初始化邻接表头指针为-1while (m--) { // 读取所有边的信息int a, b, c;cin >> a >> b >> c;add(a, b, c); // 添加边}int ans = spfa(); // 计算最短路径if (ans == INF) cout << "impossible"; // 如果无法到达终点，输出"impossible"else cout << dist[n]; // 否则输出最短距离return 0;
}【运行结果】
3 3
1 2 5
2 3 -3
1 3 4
2