AcWing 851. spfa算法如何改写为求最短路的？

本文共计664个文字，预计阅读时间需要3分钟。

题目：给定一个有向图，其中可能存在重边和自环，边权为负数。请求出从1号点到n号点的最短距离，如果无法从1号点走到n号点，则输出impossible。

输入：$ n $ 个整数，表示图中所有点的边权。

输出：从1号点到n号点的最短距离，如果无法到达，则输出impossible。

题目

给定一个 $n$ 个点 $m$ 条边的有向图，图中可能存在重边和自环， 边权可能为负数。

请你求出 $1$ 号点到 $n$ 号点的最短距离，如果无法从 $1$ 号点走到 $n$ 号点，则输出 impossible。

数据保证不存在负权回路。

输入格式 第一行包含整数 $n$ 和 $m$。

接下来 $m$ 行每行包含三个整数 $x,y,z$，表示存在一条从点 $x$ 到点 $y$ 的有向边，边长为 $z$。

输出格式 输出一个整数，表示 $1$ 号点到 $n$ 号点的最短距离。

如果路径不存在，则输出 impossible。

数据范围 $1≤n,m≤10^5$，图中涉及边长绝对值均不超过 10000。

输入样例：

3 3 1 2 5 2 3 -3 1 3 4

输出样例：

2

思路

bellman-ford算法基本思路：

for i in 1~n for a, b, w in i所有边 d[b] = min(d[b], d[a] + w[a][b])

spfa算法是bellman-ford算法的优化，优化了更新过程，尽可能确保每次更新距离都是有效的，基本思路：

queue <-- 1 存储变小的点，初始为1 while queue t = q.front q.pop 更新t的所有出边，并将出边端点加入队列

代码

#include <iostream> #include <cstring> #include <queue> using namespace std; const int N = 100010; int n, m; int h[N], e[N], w[N], ne[N], idx; int d[N]; bool st[N]; void add(int a, int b, int c) { e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ; } int spfa() { memset(d, 0x3f, sizeof d); memset(st, false, sizeof st); d[1] = 0; st[1] = true; queue<int> q; q.push(1); while (q.size()) { int t = q.front(); q.pop(); st[t] = false; for (int i = h[t]; i != -1; i = ne[i]) { int j = e[i]; if (d[j] > d[t] + w[i]) { d[j] = d[t] + w[i]; if (!st[j]) { q.push(j); st[j] = true; } } } } return d[n]; } int main() { scanf("%d%d", &n, &m); memset(h, -1, sizeof h); while (m -- ) { int a, b, c; scanf("%d%d%d", &a, &b, &c); add(a, b, c); } auto t = spfa(); if (t == 0x3f3f3f3f) puts("impossible"); else printf("%d\n", t); return 0; }