Bellman-Ford 算法

• $O(nm)$
• 判负环：做完 $n-1$ 轮之后，再做一轮，看有没有优化

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, m;
int u[2005], v[2005], w[2005];
const int INF = 1LL * 2000 * 1'000'000'000;
int dis[2005];
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
        cin >> u[i] >> v[i] >> w[i];

    for (int i = 1; i <= n; i++)
        dis[i] = INF;
    dis[1] = 0;
    for (int t = 1; t <= n - 1; t++)
        for (int i = 1; i <= m; i++)
            dis[v[i]] = min(dis[v[i]], dis[u[i]] + w[i]);

    for (int i = 1; i <= n; i++)
        if (dis[i] == INF)
            cout << -1 << " ";
        else
            cout << dis[i] << " ";
    return 0;
}

队列优化的 BF 算法 / SPFA 算法

• $O(km)$（$k$ 表示平均入队次数，随即图一般可以视作常数）
• $O(nm)$ 可以构造特殊图，把 SPFA 卡成和 BF 一样的时间复杂度
• 判负环：记录入队次数，如果一个点入队超过了 $n-1$ 次，那说明存在负环。

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, m;
const int INF = 1LL * 2000 * 1'000'000'000;
int dis[2005];
queue<int> q;
vector<pair<int, int>> e[2005];
bool inQ[2005]; // 在不在队列中
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        e[u].push_back({v, w});
    }

    for (int i = 1; i <= n; i++)
    {
        dis[i] = INF;
        inQ[i] = false;
    }
    dis[1] = 0;
    inQ[1] = true;
    q.push(1);
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        inQ[u] = false; // 现在不在队列里了
        for (int i = 0; i < e[u].size(); i++)
        {
            int v = e[u][i].first;
            int w = e[u][i].second;
            if (dis[v] > dis[u] + w)
            {
                dis[v] = dis[u] + w;
                if (!inQ[v])
                {
                    q.push(v);
                    inQ[v] = true;
                }
            }
        }
    }

    for (int i = 1; i <= n; i++)
        if (dis[i] == INF)
            cout << -1 << " ";
        else
            cout << dis[i] << " ";
    return 0;
}