P3385 【模板】负环

#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
struct edge{
	int from,to,weight;
}e[6001];
int dist[3001];

int main()
{
	int i,j,k,n,m,u,v,w,cnt,t,change;
	
	cin>>t;
	for(i=1;i<=t;i++)
	{
		cnt=0;
		cin>>n>>m;
		for(j=1;j<=m;j++)
		{
			cin>>u>>v>>w;
			if(w>=0)
			{
				cnt++;
				e[cnt].from=u;
				e[cnt].to=v;
				e[cnt].weight=w;
				cnt++;
				e[cnt].from=v;
				e[cnt].to=u;
				e[cnt].weight=w;
			}
			else
			{
				cnt++;
				e[cnt].from=u;
				e[cnt].to=v;
				e[cnt].weight=w;
			}
		}
		
		for(k=1;k<=n;k++) dist[k]=INF;
		dist[1]=0;
		
		for(j=1;j<=n;j++)
		{
			change=0;
			for(k=1;k<=cnt;k++)
			{
				if(dist[e[k].from]<INF && dist[e[k].from]+e[k].weight<dist[e[k].to])
				{
					change++;
					dist[e[k].to]=dist[e[k].from]+e[k].weight;
				}
			}
			if(change==0)
			{
				cout<<"NO"<<endl;
				break;
			}
		}
	}
	if(change!=0) cout<<"YES"<<endl;
	return 0;
}