Author: lllyouo
Date: 2025-04-02
tag: 负环
link: https://www.acwing.com/problem/content/906/

问题描述

link

分析

略

参考代码

#include <bits/stdc++.h>
using namespace std;

const int N = 510, M = 5210, INF = 0x3f3f3f3f;
int h[N], e[M], w[M], ne[M], idx;
int vis[N], dist[N], cnt[N];
int n, m, q;

void init() {
    memset(dist, 0, sizeof dist);
    memset(cnt, 0, sizeof cnt);
    memset(vis, 0, sizeof vis);
    memset(h, -1, sizeof h);
    idx= 0;
}

void add(int a, int b, int c) {
    e[idx] = b;
    w[idx] = c;
    ne[idx] = h[a];
    h[a] = idx++;
}

bool spfa() {  
    queue<int> q;
    
    for (int i = 1; i <= n; i++) {
        q.push(i);
        vis[i] = 1;
    }

    while (!q.empty()) {
        int k = q.front();
        q.pop();
        vis[k] = 0;

        for (int i = h[k]; i != -1; i = ne[i]) {
            int j = e[i];
            if (dist[j] > dist[k] + w[i]) {
                dist[j] = dist[k] + w[i];
                cnt[j] = cnt[k] + 1;
                
                if (cnt[j] >= n) return true;
                if (!vis[j]) {
                    q.push(j);
                    vis[j] = 1;
                }
            }
        }
    }

    return false;
}

int main() {
    int T; cin >> T;
    while (T--) {
        init();
        cin >> n >> m >> q;
        for (int i = 1; i <= m; i++) {
            int a, b, c; cin >> a >> b >> c;
            add(a, b, c); add(b, a, c);
        }
        for (int i = 1; i <= q; i++) {
            int a, b, c; cin >> a >> b >> c;
            add(a, b, -c);
        }
        
        if (spfa()) puts("YES");
        else puts("NO");
    }
    
    return 0;
}