SPFA判断负环

#include <bits/stdc++.h>
using namespace std;
const int N=2e4+5,inf=1e9;
int t,n,m,dis[N],cnt[N];
bool vis[N];
struct node{
	int v,w;
};
vector<node> g[N];
bool spfa(){
	queue<int> q;
	memset(vis,0,sizeof(vis));
	vis[1]=1;
	cnt[1]=0;
	q.push(1);
	while(!q.empty()){
		int u=q.front();
		q.pop();
		vis[u]=0;
		for(auto e:g[u]){
			int v=e.v,w=e.w;
			if(dis[u]+w<dis[v]){
				dis[v]=dis[u]+w;
				cnt[v]=cnt[u]+1;
				if(cnt[v]>=n){
					return true;//存在负环
				}
				if(!vis[v]){
					vis[v]=1;
					q.push(v);
				}
			}
		}
	}
	return false;//不存在负环
}
int main(){
	cin>>t;
	while(t--){
		cin>>n>>m;
		dis[1]=0;
		fill(dis+2,dis+n+1,inf);
		for(int i=1;i<=n;i++){
			g[i].clear();
		}
		for (int i=1;i<=m;i++){
			int u,v,w;
			cin>>u>>v>>w;
			g[u].push_back({v,w});
			if(w>=0){
				g[v].push_back({u,w});
			}
		}
		bool flag=spfa();
		if(flag){
			cout<<"YES"<<endl;
		}
		else{
			cout<<"NO"<<endl;
		}
	}
	return 0;
}