题目链接

Wormholes POJ - 3259

思路

$$ spfa 判断负环 $$

时间复杂度

$$ O(N(M + W)) $$

代码

#include <cstdio>
#include <vector>
#include <cstring>
#include <queue>

using namespace std;

const long long INF = 0x3f3f3f3f3f3f3f3fLL;

class SPFA {
public:
    typedef long long T;

    // .first = v
    // .second.first = w;
    // .second.second = next;
    vector<int> head;
    typedef pair<int, pair<T, int> > P;
    vector<P> e;
    int tot;
    vector<T> dist;
    vector<int> cnt;
    vector<bool> inque;


    inline void init(int cnt_n, int cnt_m) {
        head.resize(cnt_n + 5);
        dist.resize(cnt_n + 5);
        cnt.resize(cnt_n + 5);
        inque.resize(cnt_n + 5);

        fill(head.begin(), head.end(), -1);
        e.resize(cnt_m * 2 + 10);
        tot = 0;
    }

    inline void add_edge(int u, int v, T w) {
        e[tot] = make_pair(v, make_pair(w, head[u]));
        head[u] = tot++;
    }

    inline void add_edges(int u, int v, T w) {
        add_edge(u, v, w);
        add_edge(v, u, w);
    }


    bool gao(int s) {
        fill(dist.begin(), dist.end(), INF);
        fill(cnt.begin(), cnt.end(), 0);
        fill(inque.begin(), inque.end(), false);
        queue<int> que;// queue or stack
        dist[s] = 0;
        que.push(s);
        cnt[s] = 1;
        inque[s] = true;

        while (!que.empty()) {
            int u = que.front();
            inque[u] = false;
            que.pop();
            for (int i = head[u]; ~i; i = e[i].second.second) {
                int v = e[i].first;
                T w = e[i].second.first;
                if (dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    if (!inque[v]) {
                        if (++cnt[v] > (int)head.size()) {
                           return false; 
                        }
                        inque[v] = true;
                        que.push(v);
                    }
                }
            }
        }

        return true;
    }

};


int main() {
    SPFA spfa;
    int T;
    scanf("%d", &T);// don't forget &
    while (T--) {
        int n, m, w;
        scanf("%d%d%d", &n, &m, &w);// don't forget &
        spfa.init(n, m + w);
        int x, y, z;
        while (m--) {
            scanf("%d%d%d", &x, &y, &z);// don't forget &
            spfa.add_edges(x, y, z);
        }
        while (w--) {
            scanf("%d%d%d", &x, &y, &z);// don't forget &
            spfa.add_edge(x, y, -z);
        }
        if (!spfa.gao(1)) {
            puts("YES");
        } else {
            puts("NO");
        }
    }
    return 0;
}