两张图各有没有负环

一张是上一节那个有负权边的图，一张是 0→1:1、1→2:-1、2→1:-1（1 和 2 之间绕一圈是 -2）。运行下面这段程序：

#include <algorithm>
#include <iostream>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;

typedef long long ll;
const ll INF = 1000000000;                       // 走不到的点记这个值，输出时写成 -1
using Graph = vector<vector<pair<int, int>>>;    // g[u] 里放 (邻居 v, 边权 w)

// 七个点的无向图（和 Python 版同一组数据）：0-1:2 0-2:1 1-3:3 2-4:9 3-4:1 5-6:7
const vector<vector<int>> E7 = {{0, 1, 2}, {0, 2, 1}, {1, 3, 3}, {2, 4, 9}, {3, 4, 1}, {5, 6, 7}};
// 主连通块五个点、五条边（求最小生成树用）
const vector<vector<int>> E5 = {{0, 1, 2}, {0, 2, 1}, {1, 3, 3}, {2, 4, 9}, {3, 4, 1}};
// 有向负权反例：0→1:4 0→2:5 2→1:-3 1→3:1
const Graph NEG = {{{1, 4}, {2, 5}}, {{3, 1}}, {{1, -3}}, {}};
// 同一张图，只把 2→1 那条边改成 +3
const Graph POS = {{{1, 4}, {2, 5}}, {{3, 1}}, {{1, 3}}, {}};
// 有负环：0→1:1 1→2:-1 2→1:-1
const Graph CYC = {{{1, 1}}, {{2, -1}}, {{1, -1}}};

vector<ll> bellman(const Graph& g, int s) {
    int n = g.size();
    vector<ll> d(n, INF);
    d[s] = 0;
    for (int round = 0; round < n - 1; round++) {
        for (int u = 0; u < n; u++) {
            if (d[u] == INF) continue;
            for (auto [v, w] : g[u]) {
                if (d[u] + w < d[v]) d[v] = d[u] + w;
            }
        }
    }
    return d;
}

bool has_neg_cycle(const Graph& g, int s) {
    // 先松弛 n-1 轮，再多看一轮：还能松弛成功就说明有负环
    vector<ll> d = bellman(g, s);
    for (int u = 0; u < (int)g.size(); u++) {
        if (d[u] == INF) continue;
        for (auto [v, w] : g[u]) {
            if (d[u] + w < d[v]) return true;
        }
    }
    return false;
}

int main() {
    cout << boolalpha << has_neg_cycle(NEG, 0) << "/" << has_neg_cycle(CYC, 0) << endl;
}

（本题用 g++ -std=c++17 -O0 编译。）