题解：P3385 【模板】负环

· · 题解

由于某些原因，导致这道题不卡 SPFA，所以可以用 SPFA 来做。

SPFA 类似 BFS，但是只要某个节点如果【从 1 号节点到这个节点的最短距离】可以通过这种走法更新最优值，那么就可以更新并加入队列。

然而有这样一种图，它是带有负环的。负环：边的权值总和为负数的环。如果最短路走到了负环中的节点，那么它就可以绕着这个环走，越走它的权值越小，一圈圈走下去，最终到达负无穷。那此时最短路就没有意义了，因此我们需要判断负环。

SPFA 中如果一个节点被走到了超过 n 次，那么这个图就一定有负环了。因为如果没有负环，那么一圈圈走就不是最短路，那么最短路就不会有一个节点走超过 1 次，加起来一共就有 n 次。

详见代码。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn = 2e3 + 10;
ll n, m, f[maxn], vis[maxn];
vector<pair<ll, ll> > edge[maxn];
queue<ll> q;
void solve()
{
    cin >> n >> m;
    for (ll i = 1; i <= n; i++) // 十年 OI 一场空，多测不清见祖宗
    {
        edge[i].clear();
        f[i] = 0x3f3f3f3f'3f3f3f3f; // 注意赋成 INF
        vis[i] = 0;
    }
    while (!q.empty())
    {
        q.pop();
    }
    while (m--)
    {
        ll u, v, w;
        cin >> u >> v >> w;
        edge[u].push_back({v, w});
        if (w >= 0) // 注意读题
        {
            edge[v].push_back({u, w});
        }
    }
    q.push(1);
    f[1] = 0;
    bool flag = false;
    while (!q.empty())
    {
        ll u = q.front();
        q.pop();
        for (auto [v, w] : edge[u]) // C++17 语法
        {
            if (f[u] + w < f[v]) // 如果可以更新
            {
                q.push(v); // 那么就更新，并加入队列
                f[v] = f[u] + w;
                if (++vis[v] > n) // 检测到有负环
                {
                    flag = true;
                    break;
                }
            }
        }
        if (flag)
        {
            break;
        }
    }
    if (flag)
    {
        cout << "YES\n";
    }
    else
    {
        cout << "NO\n";
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    ll t; cin >> t; while (t--)
    solve();
    return 0;
}