AtCoder ABC 061 D - Score Attack (青色, 400 点)

Bellman-Ford 法を活用する典型問題ですが、少し注意が必要な問題ですね。

問題へのリンク

問題概要

頂点 辺の重み付き有向グラフが与えられます。

頂点 から頂点 へと至る最長路の長さを求めてください。

ただし、いくらでも長い路が存在する場合は inf と出力してください。

制約

• 
• 頂点 から頂点 へと至る経路は存在する

考えたこと

Bellman-Ford を単純に適用することで解ける問題ですが、負閉路検出部分については少し注意が必要です。次の点に注意する必要があります。

---

• 頂点 1 から到達できない負閉路がある場合
  • 存在しないものとして扱ってよい
  • Bellman-Ford 法の中でも検出されません
• 頂点 1 から到達できる負閉路は存在するが、そのいずれの負閉路からも頂点 N へと至ることができない
  • 存在しないものとして扱ってよい
  • ただし、Bellman-Ford 法によって検出されます

---

通常の Bellman-Ford 法における負閉路検出では、後者の負閉路に対して「負閉路あり」と判定してしまうことに注意しましょう。

具体的な解法

このような負閉路に対応する方法としては次のものが考えられます。

---

• 負閉路検出用の配列を用意する
• ベルマンフォードの 回目の反復で、最短路長が更新された頂点には inf フラグを立てる (負閉路上の頂点にはすべてフラグが立ちます)
• さらに追加で N 回の反復を行い、inf フラグを伝播していく

---

やりがちな嘘解法

次の方法は誤りです。

「 回反復し、頂点 がその期間に更新されたならば、inf と判定する」

一見ただしそうですが、次のような反例があります。これは本来は inf ですが、上記の嘘解法では inf になりません。

4 5
1 4 1000000000
1 2 0
2 3 1
3 2 0
3 4 -1000000000

コード

計算量は となります。

#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 main() {
    int N, M;
    cin >> N >> M;
    vector<vector<Edge>> G(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);
    vector<bool> negative(N, false);
    dist[0] = 0;
    for (int iter = 0; iter < N - 1; ++iter) {
        for (int v = 0; v < N; ++v) {
            if (dist[v] >= INF/2) continue;
            for (auto e : G[v]) {
                chmin(dist[e.first], dist[v] + e.second);
            }
        }
    }
    for (int iter = 0; iter < N; ++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)) {
                    negative[e.first] = true;
                }
                if (negative[v]) negative[e.first] = true;
            }
        }
    }
    if (!negative[N-1]) cout << -dist[N-1] << endl;
    else cout << "inf" << endl;
}