// 负环 SPFA 算法 O(kM~NM)
#include<bits/stdc++.h>
using namespace std;

const int N=510,M=5210;
int idx,h[N],to[M],ww[M],ne[M];
void add(int a,int b,int c){
  to[++idx]=b,ww[idx]=c,ne[idx]=h[a],h[a]=idx;
}
int n,m1,m2;
int d[N],cnt[N];
bool vis[N];

bool spfa(){
  memset(d,0,sizeof d);
  memset(cnt,0,sizeof cnt);
  memset(vis,0,sizeof vis);
  queue<int> q;
  for(int i=1; i<=n; i++) q.push(i),vis[i]=true;
  while(!q.empty()){
    int u=q.front(); q.pop(); vis[u]=false;
    for(int i=h[u]; i; i=ne[i]){
      int v=to[i];
      if(d[v]>d[u]+ww[i]){
        d[v]=d[u]+ww[i];
        cnt[v]=cnt[u]+1; //记录走过的边数
        if(cnt[v]==n) return true; //有负环
        if(!vis[v]) q.push(v), vis[v]=true;
      }
    }
  }
  return false; //无负环
}
int main(){
  int T; scanf("%d",&T);
  for(int a,b,c;T--;){
    scanf("%d%d%d",&n,&m1,&m2);
    idx=0; memset(h,0,sizeof h);
    for(int i=0; i<m1; i++){
      scanf("%d%d%d",&a,&b,&c);
      add(a,b,c),add(b,a,c);
    }
    for(int i=0; i<m2; i++){
      scanf("%d%d%d",&a,&b,&c);
      add(a,b,-c); //有向边
    }
    
    if(spfa()) puts("YES");
    else puts("NO");
  }
}

D03 最短路 Bellman-Ford 算法 SPFA 算法

/*
多一个数组dd，dd[x]表示当d[x]时从出发点1到点x经过的点数
如果dd[x]>n时，说明出现了环，而且环的所有边的权值和为负数。 
*/
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N=5010;
vector<PII>G[N];
int n,d[N],dd[N];bool v[N];
bool spfa()
{
    memset(d,0x3f,sizeof(d));
    memset(dd,0,sizeof(dd));
    memset(v,0,sizeof(v));
    queue<int>q;
	for(int i=1;i<=n;i++) dd[i]=1,v[i]=1,q.push(i);
    while(!q.empty())
    {
        int x=q.front();q.pop();
        v[x]=0;
        for(auto i:G[x])
        {
            int y=i.first,w=i.second;
            if(d[y]>d[x]+w)
            {
                d[y]=d[x]+w;
                dd[y]=dd[x]+1;if(dd[y]>n)return true;//怎么可能经过大于n个点，负环 
                if(!v[y])q.push(y),v[y]=1;
            }
        }
    }
    return false;
}
int main()
{
    int T;scanf("%d",&T);
    while(T--)
    { 
        int m1,m2;scanf("%d%d%d",&n,&m1,&m2);
        memset(G,0,sizeof(G));
        for(int i=1,x,y,w;i<=m1;i++)scanf("%d%d%d",&x,&y,&w),G[x].push_back({y,w}),G[y].push_back({x,w});
        for(int i=1,x,y,w;i<=m2;i++)scanf("%d%d%d",&x,&y,&w),G[x].push_back({y,-w});
        if(spfa())printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}