SPFA判负环

#include <bits/stdc++.h>
using namespace std;
const int N=1e4+5;
const int inf=2147483647;
int n,m,s;
struct edge{
	int to;
	int w;
};
vector<edge>G[N];
bool vis[N];
int dis[N];
int cnt[N];//统计次数 
bool spfa(){//bool类型判负环 
	for(int i=1;i<=n;i++)dis[i]=inf;
	dis[1]=0;
	queue<int>q;
	q.push(1);
	while(!q.empty()){
		int now=q.front();
		q.pop();
		for(auto x:G[now]){
			int nex=x.to;
			int val=x.w;
			if(dis[now]+val<dis[nex]){
				dis[nex]=dis[now]+val;
				cnt[nex]=cnt[now]+1;//松弛+1 
				if(cnt[nex]>=n)return 0;//如果松弛>=n,那么说明有负环 
				if(vis[nex])continue;
				vis[nex]=1;
				q.push(nex);
			}
		}
	}
	return 1;
}	
int main(){
	int T;
	cin>>T;
	while(T--){//T次询问 
		cin>>n>>m;
		for(int i=1;i<=m;i++){
			int u,v,w;
			cin>>u>>v>>w;
			G[u].push_back({v,w});
		}
		bool f=spfa();
		if(!f)cout<<"YES\n";
		else cout<<"NO\n";
		for(int i=1;i<=n;i++){
			G[i].clear();
			cnt[i]=0;
			vis[i]=0;
		}//一定不要忘记清空 
	} 
	return 0;
}