ABC137 E Coins Respawn
内容
- ABC137 E問題Coins Respawnをpythonで解きました。
問題
考えたこと
- 問題見た感じ、辺のコストを(-cost+P)にして、負の辺がある最短経路問題じゃんと思った。
- 負の重みの辺があるので、ダイクストラは使えなくて、 ベルマンフォード を使う。
- startからgoalまでの間に 負閉路 が存在すれば、答えはなし(-1)
と思って、実装してみたが、追加のテストケースとやらにWAを出されてしまった。
嘘解法だったらしい
正解の解法
- この記事を読んで、なぜ嘘なのかがわかった。 sigma1113.hatenablog.com
提出の解法
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にすることで解決した。