spfa

可以判断是否有负环，可与 dijkstra 连用

void solve() {
    int n, m;cin >> n >> m;
    vector<vector<pair<int, int>>> g(n + 1);
    for (int i = 0;i < m;i++) {
        int u, v, w;cin >> u >> v >> w;
        if (w >= 0) {
            g[v].push_back({u,w});
        }
        g[u].push_back({v,w});
    }
    queue<int> q;
    vector<int> dis(n + 1, INT_MAX), vis(n + 1), cnt(n + 1);
    dis[1] = 0;vis[1] = 1;
    q.push(1);
    while (q.size()) {
        int u = q.front();q.pop();
        vis[u] = 0;
        for (auto [v, w] : g[u]) {
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                cnt[v] = cnt[u] + 1;
                if (cnt[v] >= n) {
                    cout << "YES\n";return;
                }
                if (vis[v] == 0) {
                    vis[v] = 1;q.push(v);
                }
            }
        }
    }
    cout << "NO\n";
}

P3385

#include<bits/stdc++.h>
using namespace std;
int t,n,m;
struct{
    int v, w, next;
} a[100000];
int head[50000],dis[50000],cnt[50000];
bool vis[50000];
int edge;
queue<int> q;
void add(int u,int v,int w)
{
    a[++edge].v = v;
    a[edge].w = w;
    a[edge].next = head[u];
    head[u] = edge;
}
void spfa()
{
    memset(dis, 0x3f, sizeof dis);
    memset(vis, false, sizeof vis);
    memset(cnt, 0, sizeof cnt);
    while(!q.empty())
        q.pop();
    dis[1] = 0;
    vis[1] = 1;
    q.push(1);
    while(q.size())
    {
        int u = q.front();
        q.pop();
        vis[u] = 0;
        for (int i = head[u]; i;i=a[i].next)
        {
            int v = a[i].v, w = a[i].w;
            if(dis[v]>dis[u]+w)
            {
                dis[v] = dis[u] + w;
                cnt[v] = cnt[u] + 1;
                if(cnt[v]>=n)
                {
                    cout << "YES" << endl;
                    return;
                }
                if(!vis[v])
                    vis[v] = 1, q.push(v);
            }
        }
    }
    cout << "NO" << endl;
}
int main()
{
    ios::sync_with_stdio(0);
    cin >> t;
    while(t--)
    {
        memset(head, 0, sizeof head);///////
        cin >> n >> m;
        while(m--)
        {
            int u, v, w;
            cin >> u >> v >> w;
            add(u, v, w);
            if(w>=0)
                add(v, u, w);
        }
        spfa();
    }
}