题意：判是否有负环

分析：SPFA 入队n次以上有负环

 

 

#define M 505struct Node{    int v,val,next;}edge[M<<4];int len;int head[M],  n,  rt;int dist[M], pre[M], vis[M], times[M];void add(int &kind, int v, int val){
   //起点  终点  权值    edge[len].next = kind;    edge[len].v = v;    edge[len].val = val;    kind = len++;}deque
     
       que;bool SPFA(){    que.push_back(rt);  dist[rt]=0;  //pre[rt]=-1;    while( !que.empty() ){        int u = que.front(); que.pop_front(); vis[u] = 0;        for(int i = head[u]; i != -1; i = edge[i].next) {            int v = edge[i].v,  val = edge[i].val;            if(dist[v] > dist[u]+val) {                dist[v] = dist[u]+val; //pre[v]=u;                if( !vis[v] ){                    int t = que.front();                    if(dist[v] > dist[t]) que.push_back(v);                    else que.push_front(v);                    vis[v] = 1; times[v]++;                    if(times[v]>=n) return false;//入队次数>=n  则有负环                }            }        }    }    return true;}void init(){    len = 0;    memset(head,-1, sizeof head);    memset(dist, 1, sizeof dist);    memset(times, 0, sizeof times);    memset( vis, 0, sizeof vis );    //memset( pre, 1, sizeof pre );    while(!que.empty()) que.pop_front();}void build(){       // 处理rt    int m,w, a, b, c;           rt=1;    scanf("%d%d%d", &n, &m, &w);    while( m-- ){        scanf("%d%d%d", &a, &b, &c);        add(head[a], b, c);        add(head[b], a, c);    }    while( w-- ){        scanf("%d%d%d", &a, &b, &c);        add(head[a], b, -c);    }}int main(){                //  READ    int f;    scanf("%d",&f);    while(f--){        init();        build();        if(SPFA()) printf("NO\n");        else printf("YES\n");    }    return 0;}