评测记录

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#define N 100000
#define M 1000000
using namespace std;
struct E
{
    int nxt,to,d;
}e[M];
int h[N],ne,vis[N],dis[N];
void add(int a,int b,int c)
{
    e[++ne]=(E){h[a],b,c};
    h[a]=ne;
}
bool flag ;
void clr()
{
    memset(e,0,sizeof e);
    memset(vis,0,sizeof vis);
    memset(dis,0x3f,sizeof dis);
    memset(h,0,sizeof h);
    flag=0;
}
void spfa(int u)// 有无负环
{
    vis[u]=1;
    for(int i=h[u],v;i;i=e[i].nxt)
    {
        v=e[i].to;
        if(dis[v]>dis[u]+e[i].d)
        {
            dis[v]=dis[u]+e[i].d;
            if(vis[v]||flag) {flag=1;return;}
            spfa(v);
        }
    }
    vis[u]=0;
    return;
}
int t,n,m;
int main()
{
    cin>>t;
    while(t--)
    {
        cin>>n>>m;
        clr();
        for(int i=1,x,y,z;i<=m;i++)
        {
            cin>>x>>y>>z;
            add(x,y,z);
            if(z>=0) add(y,x,z);
        }
        for(int i=1;i<=n;i++){ spfa(i); if(flag)break;}
        if(flag) cout<<"YES\n";
        else cout<<"NO\n";
    }
}