P3385求调 有偿

#include<bits/stdc++.h>
#define INF 0xffffffff
using namespace std;
const int MAXN = 3333;
const int MOD = 1e9+7;
typedef long long int llint;
int M, N, K, T, n, m;
struct Graph
{
    vector<llint> to;
    vector<llint> l;
}g[MAXN];
bool vis[MAXN];
llint dis[MAXN];
int cnt[MAXN];
inline void add(int u, int v, int w)
{
    g[u].to.push_back(v);
    g[u].l.push_back(w);
}
bool spfa()
{
    queue<int> q;
    q.push(1);
    vis[1] = 1;
    dis[1] = 0;
    cnt[1]++;
    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        vis[u] = 0;
        for(int i=0;i<g[u].l.size();i++)
        {
            int v = g[u].to[i];
            if(dis[u]+g[u].l[i] < dis[v])
            {
                dis[v] = dis[u]+g[u].l[i];
                if(!vis[v])
                {
                    vis[v] = 1;
                    q.push(v);
                    cnt[v]++;
                    if(cnt[v] > n)
                    {
                        return 1;
                    }
                }
            }
        }
    }
    return 0;
}
void solve()
{
    if(spfa())
    {
        cout<<"YES"<<endl;
    }
    else
    {
        cout<<"NO"<<endl;
    }
}
void init()
{
    for(int i=1;i<=n;i++)
    {
        dis[i] = INF;
    }
    for(int i=1;i<=n;i++)
    {
        g[i].l.clear();
        g[i].to.clear();
    }
    memset(vis, 0, sizeof(vis));
    memset(cnt, 0, sizeof(cnt));
}
int main()
{
    cin>>T;
    while(T--)
    {
        init();
        cin>>n>>m;
        int u, v, w;
        for(int i=1;i<=m;i++)
        {
            cin>>u>>v>>w;
            add(u, v, w);
            if(w >= 0)
            {
                add(v, u, w);
            }
        }
        solve();
    }
    return 0;
}