前置：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;
}

易错提醒：还还还是别忘记初始化，别忘记初始化，别忘记初始化。