2026-10-23
negative_cycle.cpp
#include <array>
#include <vector>
bool reaches_negative_cycle(int n, const std::vector<std::array<int, 3>>& edges) {
constexpr int inf = 1'000'000'000;
std::vector<int> dist(n, inf);
dist[0] = 0;
for (int round = 0; round < n; ++round) {
for (const auto& [from, to, w] : edges) {
if (dist[from] + w < dist[to]) {
if (round == n - 1) {
return true;
}
dist[to] = dist[from] + w;
}
}
}
return false;
}
reaches_negative_cycle は、頂点 0 から n - 1 のグラフについて、頂点 0 から辺をたどって行ける負の閉路があるかを調べる関数です。edges の各要素は「始点、終点、重み」の一方向の辺で、負の閉路とは、一周して元の頂点に戻る道のうち重みの合計が負のものをいいます。reaches_negative_cycle(4, {{0, 1, 5}, {2, 3, -1}, {3, 2, -1}}) はいま true を返します。頂点2と3を回る閉路には頂点 0 から行けないので、本来は false です。
Answer
Wrong
if (dist[from] + w < dist[to]) {
inf は「まだ届いていない」という印のつもりですが、この条件はそれを普通の数として扱っています。頂点2と3はどちらも inf のままなので、辺 2→3 では inf + (-1) が inf より小さくなり、dist[3] が inf - 1 に書き換わります。次の辺 3→2 で dist[2] が inf - 2 になり、周を重ねるたびに2つの値は下がり続けます。n - 1 周目にも下がるので、関数は頂点 0 から行けない閉路を負の閉路として報告します。
Right
if (dist[from] != inf && dist[from] + w < dist[to]) {
始点にまだ届いていない辺は緩和しません。頂点 0 から行けない頂点はずっと inf のままになり、そこから出る辺は最後の周でも条件を満たさないので、行けない閉路は報告されなくなります。頂点 0 から行ける閉路の判定は変わらず、{{0, 1, 5}, {1, 2, -1}, {2, 1, -1}} なら true を返します。