SPFA求负环

SPFA看入队次数，入队次数>n则说明一定有负环

#include<bits/stdc++.h>
using namespace std;
const int maxn=2005;
const int maxm=20005;
const long long inf=2147483647;
int n,m,cnt0;
int dis[maxn],vis[maxn],head[maxn],cnt[maxn];
struct Edge
{int nxt,to,dis;
}edge[maxm];
void add(int u,int v,int w)
{edge[++cnt0].nxt=head[u];edge[cnt0].to=v;edge[cnt0].dis=w;head[u]=cnt0;
}
bool spfa()
{queue<int> q;for(int i=1;i<=n;i++){dis[i]=inf;vis[i]=0;}q.push(1);dis[1]=0;vis[1]=1;cnt[1]++;while(!q.empty()){int u=q.front();q.pop();vis[u]=0;for(int i=head[u];i;i=edge[i].nxt){int v=edge[i].to;if(dis[v]>(long long)dis[u]+edge[i].dis){dis[v]=dis[u]+edge[i].dis;if(vis[v]==0){vis[v]=1;q.push(v);cnt[v]++;if(cnt[v]>n) return 1;}}}}return 0;
}
void init()
{memset(dis,0,sizeof dis);memset(vis,0,sizeof vis);memset(cnt,0,sizeof cnt);memset(edge,0,sizeof edge);memset(head,0,sizeof head);cnt0=0;
}
int main()
{int T;cin>>T;while(T--){init();cin>>n>>m;for(int i=1;i<=m;i++){int u,v,w;cin>>u>>v>>w;add(u,v,w);if(w>=0) add(v,u,w);}if(spfa()) cout<<"YES"<<endl;else cout<<"NO"<<endl;}return 0;
}
``