RT

#include<bits/stdc++.h>
using namespace std; 
const int N=20005;
const int M=60005;
const long long INF=2147483647;
struct e
{
	int to,nxt,w;
}e[M];
int h[M],mp[N][N],vis[N],dij[N],sum[N],n,m,cnt;
void add (int u,int v,int w)
{
	e[cnt].w=w;
	e[cnt].to=v;
	e[cnt].nxt=h[u];
	h[u]=cnt++;
	return ;
}
bool spfa (int x)
{
	for(int i=0;i<n;i++){
		dij[i]=INF;
		vis[i]=0;
	}
	queue<int> q;
	q.push(x);
	sum[x]=0;
	vis[x]=1;
	while(!q.empty()){
		int v=q.front();
		q.pop();
		vis[v]=0;
		for(int i=1;i<=n;i++){
			if(dij[i]>dij[v]+mp[v][i])
			{
				dij[i]=dij[v]+mp[v][i];
				if(!vis[i])
				{
					if(++sum[i]>=n)
					{
						return 0;
					}
					else
					{
						q.push(i);
						vis[i]=1;
					}
				}
			}
		}
	}
	int ans=-1;
	for(int i=1;i<=n;i++){
		if(dij[i]>ans) ans=dij[i];
	}
	return 1;
}
int main ()
{
	int t;
	scanf("%d",&t);
	for(int k=1;k<=t;k++){
		scanf("%d%d",&n,&m);
		for(int i=1,u,v,w;i<=m;i++){
			scanf("%d%d%d",&u,&v,&w);
			if(w>=0)
			{
				add(u,v,w);
				add(v,u,w);
			}
			else
			{
				add(u,v,w);
			}
		}
		if(!spfa(1))
		{
			printf("YES\n");
		}
		else
		{
			printf("NO\n");
		}
	}
	return 0;
}

感谢！