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

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

問題へのリンク

問題概要

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

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

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

制約

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

考えたこと

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

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

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

いくつかの方法

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

• 負閉路検出用の配列を用意しておいて、N 回目の更新で更新された箇所にフラグを立てて、そこから到達できるところすべてにフラグを立てていく
  • これによって、負閉路による影響を受けるところをすべて求めることができる
• N 回目の更新で更新された箇所に -INF を入れておいて、さらに追加で N 回伝播する

やりがちな嘘解法

次の方法は誤りです。

「ループを 2N 回回しておいて、頂点 N がその間に更新されたならば、inf と判定する」

一見ただしそうですが、次のような反例があります。

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;
}