#include<bits/stdc++.h>
using namespace std;
const int INF = (1<<30);
struct Edge{
	int next,to,w;
};
int head[20000],idx = 0,t,dis[20000],n,w;;
void add(Edge edge[],int from,int to,int w){
	idx++;
	edge[idx].next = head[from];
	edge[idx].to = to;
	edge[idx].w = w;
	head[from] = idx;
}

int ford(Edge edge[],int s){
	for(int i = 1;i<=n;i++) dis[i] = INF;
	dis[s] = 0;
	for(int i = 1;i<=n;i++){
		for(int j = 1;j<=n;j++){
			for(int k = head[j];k!=0;k = edge[k].next){
				if(dis[j]+edge[k].w < dis[edge[k].to]){
					dis[edge[k].to] = dis[j]+edge[k].w; 
				} 
			}	
		} 
	}
	
	for(int i = 1;i<=n;i++){
		for(int k = head[i];k!=0;k = edge[k].next){ 
			if(dis[i]+edge[k].w < dis[edge[k].to]){
				return 1; 
			}
		}· 
	}
	return 0;
}
int main(){ 
	cin>>t;
	for(int i = 1;i<=t;i++){
		
		Edge edge[40000];
		memset(head,0,sizeof(head));
		idx = 0;
		cin>>n>>w;
		for(int j = 1;j<=w;j++){
			int u,v,f;
			cin>>u>>v>>f;
			if(f>=0){
				add(edge,u,v,f);
				add(edge,v,u,f);
			}else{
				add(edge,u,v,f);
			}
			
		}
		int d = ford(edge,1);
		if(d==1){
			cout<<"YES"<<endl; 
		}else{
			cout<<"NO"<<endl;
		}
	}
	

	return 0;
} 

第十一点 1 4 3 2 3 -1 3 4 -1 4 2 -1 错误的原因是因为虽然有负环 但是 没有从特定点1开始。 想咨询一下大佬 应该如何加上判断从1点开始的存在的负环。是要加上dfs????