ちょっと注意が必要な Bellman-Ford 法の典型題。昔の AtCoder はこういうのもあったのか...
問題概要
頂点
辺の重み付き有向グラフが与えられる。頂点 1 から頂点 N への最長路の長さを求めよ。無限に大きくできる場合は "inf" と出力せよ。
制約
- 頂点 1 から頂点 N へと至る経路は存在する
考えたこと
Bellman-Ford やるだけ...なのだが、負閉路検出部分について少し注意が必要で、
- 頂点 1 から到達できない負閉路: 当然無視 (Bellman-Ford でも検出しない)
- 頂点 1 から到達できる負閉路であっても、その閉路から頂点 N へと至ることができない: 検出されるけど無視しなければならない
通常の Bellman-Ford 法における負閉路検出は、後者の負閉路に対して「負閉路あり」と判定してしまうことに注意。で、ここで非常にやりがちな嘘があるので注意。。。
いくつかの方法
負閉路検出用の配列を用意しておいて、N 回目の更新で更新された箇所にフラグを立てて、そこから到達できるところすべてにフラグを立てることで、負閉路による影響を受けるところをすべて求めることができる (editorial)
N 回目の更新で更新された箇所に -INF を入れておいて、さらに追加で N 回伝播する (わかりやすい)
やりがちな嘘
- ループを 2N 回回しておいて、頂点 N がその間に更新されたら、「1 から N まで至る経路中に回せる負閉路あり」
と判定すればよさそうに思えた。が、これには反例がある
5 6 1 2 -1 2 3 -1 3 4 -1 4 2 -1 2 5 -1 1 5 -10000000
コード
#include <iostream> #include <vector> using namespace std; bool chmin(long long &a, long long b) { if (a > b) {a = b; return true;} return false;} const long long INF = 1LL<<60; using Edge = pair<int, long long>; int N, M; vector<vector<Edge> > G; int main() { cin >> N >> M; G.clear(); G.resize(N); for (int i = 0; i < M; ++i) { int a, b; long long w; cin >> a >> b >> w; --a, --b; G[a].push_back(Edge(b, -w)); } vector<long long> dist(N, INF); bool negative = false; dist[0] = 0; for (int iter = 0; iter <= N*2; ++iter) { for (int v = 0; v < N; ++v) { if (dist[v] >= INF/2) continue; for (auto e : G[v]) { if (chmin(dist[e.first], dist[v] + e.second)) { if (e.first == N-1 && iter == N*2) negative = true; } } } } if (!negative) cout << -dist[N-1] << endl; else cout << "inf" << endl; }