ABC137 E - Coins Respawn - あっとのTECH LOG

問題原文

問題要旨

頂点１から頂点 $N$ まで移動できることが保証される、 $N$ 頂点 $M$ 辺の有向グラフが与えられる。
このグラフ上で、頂点１から頂点 $N$ まで移動するゲームを考える。プレイヤーは１秒につき一回移動でき、各辺を通るごとに何度でも $C_i$ 点を得ることができる。最終的に頂点 $N$ にたどり着いたときの、（点数の総和）- （ $P$ × 秒数）がスコアになる。（スコアの最低値は０）
達成できるスコアの最大値を求めよ。またスコアを無限大に大きくできる場合には−１とせよ。

$1 \leq N \leq 2500$
$1 \leq M \leq 5000$

解法

１秒間につき１回移動できるので、各辺を通った時に得ることができる点数は、 $C_i - P$ 点としてよい。
またスコアが最大になるように移動するので、頂点１から頂点 $N$ までの最長経路を求めればよい。
これは、各辺の重みの正負を反対にした上で、最短経路問題を解けばいい。

今回は負の重みがある辺が混ざってくるので、ダイクストラ法でなくベルマンフォード法を使う。
ただし、頂点１から頂点 $N$ 上に存在しない負の閉路を検知してループを止めないよう気を付ける必要がある。
負の閉路の影響が頂点 $N$ まで伝播しうる場合、最大追加で $N$ 回ループを回せばその影が届く。よって、 $N$ 回目以降に最短距離が更新されるようなものについては、その距離を-∞としてしまってよい。（これを素直に更新後の値にすると、うまくいかない。あくまでも 負閉路の影響が頂点 $N$ に伝播するかどうか をチェックする。）

この点に関しては、以下の記事でとても丁寧にまとめられています。（大変勉強になりました、ありがとうございます）

sigma1113.hatenablog.com

実装

N, M, P = map(int, input().split())
Edges = []
for i in range(M):
    a, b, c = map(int, input().split())
    a, b = a - 1, b - 1
    Edges.append([a, b, -(c - P)])


dist = [float('inf')] * N
dist[0] = 0

for i in range(2 * N):
    for fr, to, cost in Edges:
        if dist[to] > dist[fr] + cost:
            dist[to] = dist[fr] + cost
            if i >= N:
                dist[to] = -float('inf')


print(max(0, -dist[N - 1]) if -dist[N - 1] != float('inf') else -1)

感想

最長経路は重みを正負逆転した上での最短経路 、というのはよく見る典型ですね。

コンテスト後に嘘を落とすhackケースが指摘され、話題になりました。
D - Score Attack も同様の点に注意しないと本来は落ちるので、気をつけましょう。
勉強になりました。