#include <bits/stdc++.h>
using namespace std;


int head[2005],ver[4005],wei[4005],ne[4005],idx;
int n,m,cnt[2005],dis[2005];
bool vis[2005];

void add(int u,int v,int w){
	ver[++idx]=v,wei[idx]=w,ne[idx]=head[u],head[u]=idx;
}
bool spfa(){
	queue<int> q;
	q.push(1);
	vis[1]=true;
	dis[1]=0;
	while(!q.empty()){
		int u=q.front();
		q.pop();
		vis[u]=false;
		for(int i=head[u];i;i=ne[i]){
			int v=ver[i],w=wei[i];
			if(dis[v]>dis[u]+w){
				dis[v]=dis[u]+w;
				if(!vis[v]){
					q.push(v);
					vis[v]=true;
					cnt[v]++;
					if(cnt[v]>=n) return true;
				}
			}
		}
	}
	return false;
}
int main(){
	int T;
	cin>>T;
	while(T--){
		cin>>n>>m;
		memset(head,0,sizeof(head));
		memset(cnt,0,sizeof(cnt));
		memset(vis,0,sizeof(vis));
		memset(dis,0x3f,sizeof(dis));
		idx=0;
		for(int i=1;i<=m;++i){
			int u,v,w;
			cin>>u>>v>>w;
			if(w>=0){
				add(u,v,w);
				add(v,u,w);
			}
			else add(u,v,w);
		}
		puts(spfa()? "YES":"NO");
	}
	return 0;
}

保证链式前向星写的没有问题

错误数据：

.in

.out