10 分求调

#include<bits/stdc++.h>
using namespace std;
const int N=3010,M=10010;
int n,m,idx,h[N],e[M],ne[M],w[M],cnt[N],st[N],d[N];
bool spfa(){
    queue<int> q;
    for(int i=1;i<=n;i++) st[i]=1,q.push(i);
    while(q.size()){
        auto t=q.front();
        q.pop();
        st[t]=0;
        for(int i=h[t];~i;i=ne[i]){
            if(d[e[i]]>d[t]+w[i]){
                d[e[i]]=d[t]+w[i];
                cnt[e[i]]++;
                if(cnt[e[i]]>=n) return 1;
                if(!st[e[i]]) st[e[i]]=1,q.push(e[i]);
            }
        }
    }
    return 0;
}
int main(){
    int t;
    cin>>t;
    while(t--){
        cin>>n>>m;
        memset(h,-1,sizeof h);
        for(int i=0;i<m;i++){
            int a,b,c;
            cin>>a>>b>>c;
            e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
        }
        if(spfa()) cout<<"YES\n";
        else cout<<"NO\n";
    }
}