結果
問題 | No.807 umg tours |
ユーザー |
|
提出日時 | 2019-11-13 20:46:13 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,888 ms / 4,000 ms |
コード長 | 1,233 bytes |
コンパイル時間 | 241 ms |
コンパイル使用メモリ | 82,196 KB |
実行使用メモリ | 158,232 KB |
最終ジャッジ日時 | 2024-11-23 19:45:42 |
合計ジャッジ時間 | 19,934 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 26 |
ソースコード
from heapq import heappop, heappushN, M = map(int, input().split())INF = float('inf')isOnePath = [False] * Nedges = [[] for _ in range(N)]for _ in range(M):A, B, C = map(int, input().split())A -= 1B -= 1edges[A].append((B, C))edges[B].append((A, C))minDist = [[INF] * N for _ in range(2)]que = [(0, (0, 0))]while que:dist, (now, height) = heappop(que)if minDist[height][now] <= dist:continueminDist[height][now] = distif height == 0:for to, cost in edges[now]:if minDist[0][to] > dist + cost:heappush(que, (dist + cost, (to, 0)))if minDist[1][to] > dist:heappush(que, (dist, (to, 1)))else:for to, cost in edges[now]:if minDist[1][to] > dist + cost:heappush(que, (dist + cost, (to, 1)))reverseDist = [INF] * Nque = [(0, 0)]while que:dist, now = heappop(que)if reverseDist[now] <= dist:continuereverseDist[now] = distfor to, cost in edges[now]:if reverseDist[to] > dist + cost:heappush(que, (dist + cost, to))print(0)for i in range(1, N):ans = minDist[1][i] + reverseDist[i]print(ans)