pythonで青くなるブログ

主に競プロのについての記事(日記的な)を書きます。現在atcoder水色,こどふぉ青色。python3使って、やってます。atcoder青くなりたい

ABC137 E Coins Respawn

内容

  • ABC137 E問題Coins Respawnをpythonで解きました。

問題

atcoder.jp

考えたこと

  • 問題見た感じ、辺のコストを(-cost+P)にして、負の辺がある最短経路問題じゃんと思った。
  • 負の重みの辺があるので、ダイクストラは使えなくて、 ベルマンフォード を使う。
  • startからgoalまでの間に 負閉路 が存在すれば、答えはなし(-1)

と思って、実装してみたが、追加のテストケースとやらにWAを出されてしまった。

嘘解法だったらしい

正解の解法

提出の解法

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N, M, P = map(int, input().split())

edges = []
for _ in range(M):
    a, b, c = map(int, input().split())
    edges.append([a-1, b-1, -c+P])


def bellnabFord(edges, src, N):
    inf = float('inf')
    dist = [inf for i in range(N)]
    dist[src] = 0

    for i in range(2*N):
        for s, d, c in edges:
            if s != inf and dist[d] > dist[s]+c:
                dist[d] = dist[s]+c
                if i >= N: #N回目以降の更新では-infに。(数字の大きさに影響されない)
                    dist[d] = -float('inf')

            if i == N-1:
                prev = dist[-1]
    return (prev, dist[-1])


prev, dist = bellnabFord(edges, 0, N)
if prev != dist:
    ans = -1
else:
    ans = max(0, -dist)
print(ans)

実装について

  • 初めは2N回更新をして、N~2Nの間にdist[N]の値が更新されたら負閉路と思っていたけど、そこがまずかったらしい
  • 上の記事を参考にして、N~2N回目の間で更新があった場合は、dist[i] = -infにすることで解決した。