前置：bellman-ford

---

$spfa$是$Bellman?Ford$算法的改進。在$Bellman?Ford$中，我們在每一輪中枚舉了每一條邊，但是實際上，在上一輪中沒有被更新的點所延伸出來的邊是不需要訪問的，因為上一輪中沒有被更新的點值沒變，邊權沒變，再向下也只是重復一次，不會更新出新的值，所以是無效訪問。$spfa$就是省略了$Bellman?Ford$中的這些無效訪問。

具體寫法參考$BFS$思路，用隊列維護需要更新的點。同時，我們要關注下一個要更新的點在不在隊列中，如果在隊列中就不需要重復入隊了。（入隊了也是重復更新，做無用功）

$spfa$也具有$Bellman?Ford$有的判斷負環的功能。在上篇講過，每個點最多只會被更新$n$次，所以可以同時維護一個$cnt$數組，表示每個點被更新的次數，只要有一個點被更新超過$n$次就退出，判為存在負環。

---

例題：

【模板】Bellman-Ford算法-StarryCoding | 踏出編程第一步

題目描述

$n$點$m$邊的帶負權有向圖（連通，可能存在重邊與自環），求$1$到所有點的單源最短路的距離。

保證結點$1$可以到達所有結點。

如果圖中存在負環，則只輸出一個整數$?1$。

輸入描述

第一行兩個整數$n,m。(2\le n,m\le 1\times 10^4)$

接下來$m$行，每行一條單向邊$x,y,z$表示存在一條從$x$到$y$的距離為$z$的通道。$(1\le x,y\le n,?10^9\le z\le 10^9)$

輸出描述

一行$n$個整數，第$i$個整數表示從點$1$到點$n$的最短距離。

如果圖中存在負環，則只輸出一個整數$?1$。

輸入樣例1

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

輸出樣例1

0 1 -1 0 -5

解

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 9;
using ll = long long;
const ll inf = 2e18;struct Edge
{int x;ll w;
};int n, m;
vector<Edge> g[N];
ll d[N];bool spfa(int st)
{//兩行初始化，不要忘記for(int i = 1; i <= n; ++i) d[i] = inf;d[st] = 0;queue<int> q;       //隊列存儲需要更新的點bitset<N> inq;      //inq[i]表示第i個點在不在隊列中q.push(st);         vector<int> cnt(n + 1);     //計數while(q.size())     {int x = q.front(); q.pop(); inq[x] = false;for(auto [y, w] : g[x])         //更新所有邊{if(d[y] > d[x] + w)         //如果能被更新，更新且入隊{if(++ cnt[y] >= n) return true;     //出現負環，退出d[y] = d[x] + w;if(!inq[y]){q.push(y);inq[y] = true;}}}}return false;
}void solve()
{cin >> n >> m;for(int i = 1; i <= m; ++i){int u, v;ll w; cin >> u >> v >> w;g[u].push_back({v, w});}if(spfa(1)) cout << -1 << '\n';else{for(int i = 1; i <= n; ++i) cout << d[i] << ' ';}
}int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int _ = 1;while(_--) solve();return 0;
}

易錯提醒：還還還是別忘記初始化，別忘記初始化，別忘記初始化。