Coins Respawn [AtCoder Beginner Contest 137 E]

https://atcoder.jp/contests/abc137/tasks/abc137_e

前提知識

• ベルマンフォード

解説

https://atcoder.jp/contests/abc137/submissions/6895110

1回移動すると、辺についているコストが足されて、P分引かれるので、辺のコストをC[i]-Pに変換しておこう。
すると、この問題は頂点1から頂点Nへの最大経路問題となる。
P引かれているので負の辺が存在する可能性があるのだが、この時点でベルマンフォードで解くしかなさそうな雰囲気がする。
計算量もO(NM)で問題ないので、これで解けばよさそうだ。
無限にスコアが増える可能性があるが、これはベルマンフォードをもう一回してスコアが増えれば無限に増えるので、-1と答える。

…とやるとWA。

https://twitter.com/c_Ry0ta/status/1160196135467618304

3 4 0  
1 2 1  
2 2 1  
2 3 1  
1 3 100000  

このようにむっちゃ回さないと最大値が増えないパターンもある。
これで落ちる場合は、ベルマンフォードの実装が間違っている場合である。
これは、経路上に正のサイクルが存在する場合の判定を端折るとこういうパターンを見逃すことになる。
本物のベルマンフォード同様に正のサイクルを検知した段階で-1と返すようにしよう。

int N, M, P;
vector<pair<int, int>> E[2500];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M >> P;

    BellmanFordMax bf(N);

    rep(i, 0, M) {
        int a, b, c; cin >> a >> b >> c;
        a--; b--;
        bf.add(a, b, c - P);
    }

    ll ans = bf.solve(0)[N - 1];

    if (ans == infl) ans = -1;
    else if (ans < 0) ans = 0;

    cout << ans << endl;
}