提交记录

#include<bits/stdc++.h>
using namespace std;
const int N=2e3+10,M=3e3+10;
int t,n,n1,m,u[N],v[N],w[N],d[M];
int main(){
	int i,j,x,y,z;
	scanf("%d",&t);
	while(t--){
		m=0;
		memset(d,0x3f,sizeof(d));
		d[1]=0;
		scanf("%d%d",&n,&n1);
		while(n1--){
			scanf("%d%d%d",&x,&y,&z);
			if(z>=0){
				m++;
				u[m]=x,v[m]=y,w[m]=z;
				m++;
				u[m]=y,v[m]=x,w[m]=z;
			}else{
				m++;
				u[m]=x,v[m]=y,w[m]=z;
			}
		}for(i=1;i<n;i++){
			for(j=1;j<=m;j++){
				if(d[u[j]]+w[j]<d[v[j]]){
					d[v[j]]=d[u[j]]+w[j];
				}
			}
		}bool flag=false;
		for(i=1;i<=m;i++){
			if(d[u[i]]+w[i]<d[v[i]]){
				flag=true;
				break;
			}
		}if(flag)printf("YES\n");
		else printf("NO\n");
	}
	return 0;
}