SPFA判断有无负权回路

注意事项

一，判断有无负环时候不需要初始会dist数组，但是当我们判断是否存在以某个点为起点的负环，则需要把，qu.push(pos),dist[pos] = 0,其他置为memset(dist,0x3f,sizeof dist)，负环可能以任意一点为起点，所以就需要把所有起点放入队列之中！

二，判断存在条件是cnt[j] >= n,这里cnt[j] 应该是入队的次数，即st == [false]之后，而不是松弛的次数！

P3385 【模板】负环
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
int n,m;
const int N = 4e4+9;
int idx,h[N],e[N],ne[N],w[N];
bool st[N];
int qu[N],dist[N],cnt[N];
void add(int a,int b,int c)
{
    e[idx] = b,ne[idx] = h[a],w[idx] = c,h[a] = idx++;
}

bool spfa()
{
    memset(cnt,0,sizeof cnt);
    memset(dist,0x3f,sizeof dist);
    memset(st,false,sizeof st);
    int hh = 0,tt = 0;
    qu[tt++] = 1;
    dist[1] = 0;
    while(hh != tt)
    {
        int t = qu[--tt];
        st[t] = false;
        for(int i=h[t]; ~i; i=ne[i])
        {
            int j = e[i];
            if(dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                if(!st[j])
                {
                    cnt[j] = cnt[t] + 1;
                    if(cnt[j] >= n) return true;
                    st[j] = true;
                    qu[tt++] = j;
                }
            }
        }
    }
    return false;
}

int main()
{
    //freopen("P3385_9.in","r",stdin);
    //freopen("out.txt","w",stdout);
    int _;
    cin >> _;
    while(_--)
    {
        memset(h,-1,sizeof(h));
        idx = 0;
        cin >> n >> m;
        for(int i=1; i<=m; i++)
        {
            int a,b,c;
            cin >> a >> b >> c;
            add(a,b,c);
            if(c >= 0)
            {
                add(b,a,c);
            }
        }
        if(spfa()) puts("YES");
        else puts("NO");
    }
    return 0;
}