ちょっと注意が必要な Bellman-Ford 法の典型題。昔の AtCoder はこういうのもあったのか...

問題概要

$N$ 頂点 $M$ 辺の重み付き有向グラフが与えられる。頂点 1 から頂点 N への最長路の長さを求めよ。無限に大きくできる場合は "inf" と出力せよ。

制約

$2 \le N \le 1000$
頂点 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;
}