题目

代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,alen,ans[111000],cnt[111000],last[550000],w;
bool b[111000];
struct edge {
    int x,y,c,pre;
}a[111000];
void add(int x,int y,int c) {
    a[++alen]=edge{x,y,c,last[x]};
    last[x]=alen;
}
bool spfa() {
    memset(ans,0x7f,sizeof(ans));ans[1]=0;
    memset(b,0,sizeof(b));b[1]=true;
    memset(cnt,0,sizeof(cnt));
    queue<int> q;
    q.push(1);
    while(!q.empty() ) {
        int x=q.front();
        for(int ix=last[x];ix;ix=a[ix].pre) {
            int y=a[ix].y;
            if(ans[y]>ans[x]+a[ix].c) {
                ans[y]=ans[x]+a[ix].c;
                cnt[y]=cnt[x]+1;if(cnt[y]>n) return 1;
                if(!b[y]) {
                    b[y]=true;
                    q.push(y);
                }
            }
        }
        b[x]=false;
        q.pop();
    }
    return 0;
}
int main() {
    int T;
    cin>>T;
    while(T--) {
        cin>>n>>m;
        memset(last,0,sizeof(last));alen=0;
        for(int i=1;i<=m;i++) {
            int x,y,c;
            cin>>x>>y>>c;
            if(c>=0) {
                add(x,y,c);
                add(y,x,c); 
            }
            else {
                add(x,y,c);
            }
        }
        if(spfa()) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0;
}