poj 3259 spfa 虫洞问题判到点1时候有环

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <utility>
#include <climits>
#include <algorithm>
using namespace std;
const int N = 5501;
int n, m, q;
vector< pair<int, int> > g[N+10];
long long dist[N+10];
bool inQue[N+10];
int cnt[N+10];
queue<int> Q;
bool spfa(int src) {
    for(int i = 0; i <= n; ++i) {
        dist[i] = INT_MAX;
    }
    dist[src] = 0;
    memset(cnt, 0, sizeof(cnt));
    memset(inQue, false, sizeof(inQue));
    while(!Q.empty()) Q.pop();
    Q.push(src);
    inQue[src] = true;
    while(!Q.empty()) {
        int u = Q.front(); Q.pop();
        for(int i = 0; i < g[u].size(); ++i) {
            int to = g[u][i].first;
            if(dist[u] + g[u][i].second < dist[to]) {
                dist[to] = dist[u] + g[u][i].second;
                cnt[to]++;
                if(cnt[to] >= n) return false;
                if(!inQue[to]) {
                    inQue[to] = true;
                    Q.push(to);
                }
            }
        }
        inQue[u] = false;
    }
    return true;
}
int main() {
    int T, i, u, v, w;
    cin >> T;
    while(T--) {
        cin >> n >> m >> q;
        for(i = 0; i <= n; i++) {
            g[i].clear();
        }
        pair <int,int> foo;
        for(i = 0; i < m; i++) {
            scanf("%d%d%d", &u, &v, &w);
            foo = make_pair(v, w);
            g[u].push_back(foo);
            foo = make_pair(u, w);
            g[v].push_back(foo); // two way!
        }
        for(i = 0; i < q; i++) {
            scanf("%d%d%d", &u, &v, &w);
            foo = make_pair(v, -w);
            g[u].push_back(foo);
        }
        if(spfa(1)) {
            printf("NO");
        }
        else printf("YES");
        printf("\n");
    }
    return 0;
}