ABC137 E Coins Respawn
Diff 1740.
ABC061-D Score Attackの強化版.
頂点
$ A_i
から
$ B_i
にコスト
$ P - C_i
の辺を張り, 2度ベルマンフォード法を行った後最終的な距離に-1をかけることで答えを求めることができる.
通常の負閉路検出では正しく判定できないことに注意(関係ない負閉路まで考えてしまう).
実装例:
https://atcoder.jp/contests/abc137/submissions/18991752