洛谷 P2850 [USACO06DEC] Wormholes G

// 洛谷 P2850 [USACO06DEC] Wormholes G —— ★ 这一版就能 AC
//
// ★★★ 问的是「从**某块**田地出发……在初始离开时间之前回到起点」——
//     也就是「**这张图里有没有负环**」，和出发点无关。
//     ⇒ 所有点 dist 初值 0、全部入队（等价于加一个连向所有点、边长 0 的超级源点）。
//
// ⚠ 这一行正是[隔壁 P3385](/sol/p3385/) 的**错法**：那道题问的是「从 1 出发能到达的负环」。
//    同一段代码，两道题各占一头。
//
// 读边两条规则，别搞混：
//   · M 条**路径**：双向，耗时 T ≥ 0     ⇒ 存两遍
//   · W 个**虫洞**：单向，把时间拨回 T   ⇒ 存一条 −T 的边，**只存一遍**

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int F;
    cin >> F;
    while (F--) {
        int n, m, w;
        cin >> n >> m >> w;
        vector<vector<pair<int, int>>> g(n + 1);
        for (int i = 0; i < m; i++) {
            int s, e, t;
            cin >> s >> e >> t;
            g[s].push_back({e, t});
            g[e].push_back({s, t});          // 双向路径
        }
        for (int i = 0; i < w; i++) {
            int s, e, t;
            cin >> s >> e >> t;
            g[s].push_back({e, -t});         // 单向虫洞，只存一遍
        }

        vector<int> dist(n + 1, 0), cnt(n + 1, 0);   // ★ 所有点初值 0
        vector<char> inq(n + 1, 1);
        queue<int> q;
        for (int i = 1; i <= n; i++) q.push(i);      // ★ 全部入队
        bool neg = false;
        while (!q.empty() && !neg) {
            int u = q.front();
            q.pop();
            inq[u] = 0;
            for (auto [v, ww] : g[u])
                if (dist[u] + ww < dist[v]) {
                    dist[v] = dist[u] + ww;
                    cnt[v] = cnt[u] + 1;
                    if (cnt[v] >= n) { neg = true; break; }
                    if (!inq[v]) { inq[v] = 1; q.push(v); }
                }
        }
        cout << (neg ? "YES" : "NO") << "\n";
    }
    return 0;
}

// ✗ 错法①：只从 1 号田地出发 —— ★★★ 这一页的主线
//
// 它是[隔壁 P3385](/sol/p3385/) 的**正解**：那道题问的是「从顶点 1 出发能到达的负环」。
// 而这道题问的是「从**某块**田地出发」⇒ 全图。
// ⇒ 图一旦不连通，1 号点那一块之外的负环它就看不见。

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int F;
    cin >> F;
    while (F--) {
        int n, m, w;
        cin >> n >> m >> w;
        vector<vector<pair<int, int>>> g(n + 1);
        for (int i = 0; i < m; i++) {
            int s, e, t;
            cin >> s >> e >> t;
            g[s].push_back({e, t});
            g[e].push_back({s, t});
        }
        for (int i = 0; i < w; i++) {
            int s, e, t;
            cin >> s >> e >> t;
            g[s].push_back({e, -t});
        }
        vector<int> dist(n + 1, INF), cnt(n + 1, 0);
        vector<char> inq(n + 1, 0);
        queue<int> q;
        dist[1] = 0; inq[1] = 1; q.push(1);          // ✗ 只有 1 号点
        bool neg = false;
        while (!q.empty() && !neg) {
            int u = q.front(); q.pop(); inq[u] = 0;
            for (auto [v, ww] : g[u])
                if (dist[u] + ww < dist[v]) {
                    dist[v] = dist[u] + ww;
                    cnt[v] = cnt[u] + 1;
                    if (cnt[v] >= n) { neg = true; break; }
                    if (!inq[v]) { inq[v] = 1; q.push(v); }
                }
        }
        cout << (neg ? "YES" : "NO") << "\n";
    }
    return 0;
}

// ✗ 错法②：虫洞也存成双向
//
// 「虫洞的特性非常特殊 —— 它是一个**单向**通道」。存成双向的话，
// `s → e → s` 绕一圈是 `−2T < 0`，**它自己就是一个负环** ⇒ 只要有虫洞就无脑 YES。
//
// ★ 和[隔壁 P3385](/sol/p3385/) 那个「一律存双向」是同一个形状的错，
//   只是那道题由**边权的正负号**决定，这道题由**它排在输入的哪一段**决定。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int F;
    cin >> F;
    while (F--) {
        int n, m, w;
        cin >> n >> m >> w;
        vector<vector<pair<int, int>>> g(n + 1);
        for (int i = 0; i < m; i++) {
            int s, e, t;
            cin >> s >> e >> t;
            g[s].push_back({e, t});
            g[e].push_back({s, t});
        }
        for (int i = 0; i < w; i++) {
            int s, e, t;
            cin >> s >> e >> t;
            g[s].push_back({e, -t});
            g[e].push_back({s, -t});                 // ✗ 虫洞不是双向的
        }
        vector<int> dist(n + 1, 0), cnt(n + 1, 0);
        vector<char> inq(n + 1, 1);
        queue<int> q;
        for (int i = 1; i <= n; i++) q.push(i);
        bool neg = false;
        while (!q.empty() && !neg) {
            int u = q.front(); q.pop(); inq[u] = 0;
            for (auto [v, ww] : g[u])
                if (dist[u] + ww < dist[v]) {
                    dist[v] = dist[u] + ww;
                    cnt[v] = cnt[u] + 1;
                    if (cnt[v] >= n) { neg = true; break; }
                    if (!inq[v]) { inq[v] = 1; q.push(v); }
                }
        }
        cout << (neg ? "YES" : "NO") << "\n";
    }
    return 0;
}

// ✗ 错法③：双向路径只存一遍
//
// 反过来的那一半：`M` 条路径是**双向**的，只存一遍会让图凭空少一半边。
// ⚠ 它的方向是可判的：边少了 ⇒ 环也只会更少 ⇒ **答案恒 ≤ 正解**（不会把 NO 说成 YES）。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int F;
    cin >> F;
    while (F--) {
        int n, m, w;
        cin >> n >> m >> w;
        vector<vector<pair<int, int>>> g(n + 1);
        for (int i = 0; i < m; i++) {
            int s, e, t;
            cin >> s >> e >> t;
            g[s].push_back({e, t});                  // ✗ 少了反着那一行
        }
        for (int i = 0; i < w; i++) {
            int s, e, t;
            cin >> s >> e >> t;
            g[s].push_back({e, -t});
        }
        vector<int> dist(n + 1, 0), cnt(n + 1, 0);
        vector<char> inq(n + 1, 1);
        queue<int> q;
        for (int i = 1; i <= n; i++) q.push(i);
        bool neg = false;
        while (!q.empty() && !neg) {
            int u = q.front(); q.pop(); inq[u] = 0;
            for (auto [v, ww] : g[u])
                if (dist[u] + ww < dist[v]) {
                    dist[v] = dist[u] + ww;
                    cnt[v] = cnt[u] + 1;
                    if (cnt[v] >= n) { neg = true; break; }
                    if (!inq[v]) { inq[v] = 1; q.push(v); }
                }
        }
        cout << (neg ? "YES" : "NO") << "\n";
    }
    return 0;
}