spfa

可以判断是否有负环，可与 [[图论/dijkstra]] 连用

struct edge {
  int v, w;
};

vector<edge> e[maxn];
int dis[maxn], cnt[maxn], vis[maxn];
queue<int> q;

bool spfa(int n, int s) {
  memset(dis, 63, sizeof(dis));
  dis[s] = 0, vis[s] = 1;
  q.push(s);
  while (!q.empty()) {
    int u = q.front();
    q.pop(), vis[u] = 0;
    for (auto ed : e[u]) {
      int v = ed.v, w = ed.w;
      if (dis[v] > dis[u] + w) {
        dis[v] = dis[u] + w;
        cnt[v] = cnt[u] + 1;  // 记录最短路经过的边数
        if (cnt[v] >= n) return false;
        // 在不经过负环的情况下，最短路至多经过 n - 1 条边
        // 因此如果经过了多于 n 条边，一定说明经过了负环
        if (!vis[v]) q.push(v), vis[v] = 1;
      }
    }
  }
  return true;
}

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();
    }
}