五级题目AC

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

const int MAXN = 505; const int INF = 0x3f3f3f3f;

struct Edge {

int to, w;

};

vector graph[MAXN]; int dist[MAXN], cnt[MAXN]; bool inQueue[MAXN];

bool spfa(int n, int start) {

memset(dist, 0x3f, sizeof(dist));
memset(cnt, 0, sizeof(cnt));
memset(inQueue, false, sizeof(inQueue));

queue<int> q;
dist[start] = 0;
q.push(start);
inQueue[start] = true;
cnt[start] = 1;

while (!q.empty()) {
    int u = q.front(); q.pop();
    inQueue[u] = false;

    for (const Edge& e : graph[u]) {
        int v = e.to, w = e.w;
        if (dist[u] + w < dist[v]) {
            dist[v] = dist[u] + w;
            if (!inQueue[v]) {
                q.push(v);
                inQueue[v] = true;
                cnt[v]++;
                if (cnt[v] >= n) return true; // 存在负环
            }
        }
    }
}
return false;

}

int main() {

int F;
cin >> F;
while (F--) {
    int N, M, W;
    cin >> N >> M >> W;

    // 清空图
    for (int i = 1; i <= N; i++) {
        graph[i].clear();
    }

    // 读小路（无向边）
    for (int i = 0; i < M; i++) {
        int S, E, T;
        cin >> S >> E >> T;
        graph[S].push_back({E, T});
        graph[E].push_back({S, T});
    }

    // 读虫洞（有向负边）
    for (int i = 0; i < W; i++) {
        int S, E, T;
        cin >> S >> E >> T;
        graph[S].push_back({E, -T});
    }

    // 从每个点开始检查负环（因为图可能不连通）
    bool hasNegativeCycle = false;
    for (int i = 1; i <= N; i++) {
        if (spfa(N, i)) {
            hasNegativeCycle = true;
            break;
        }
    }

    cout << (hasNegativeCycle ? "YES" : "NO") << endl;
}
return 0;

}