結果
問題 | No.807 umg tours |
ユーザー |
|
提出日時 | 2023-09-05 16:09:54 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 2,859 ms / 4,000 ms |
コード長 | 926 bytes |
コンパイル時間 | 443 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 198,524 KB |
最終ジャッジ日時 | 2024-06-23 11:40:41 |
合計ジャッジ時間 | 25,976 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 26 |
ソースコード
import sysfrom heapq import heappop, heappushinput = sys.stdin.readlineN, M = map(int, input().split())ABC = [list(map(int, input().split())) for _ in range(M)]G = [[] for _ in range(N)]for i in range(M):a, b, c = ABC[i]a -= 1b -= 1G[a].append([b, c])G[b].append([a, c])dist = [[float('inf')]*2 for _ in range(N)]dist[0][0] = 0# dijkstraque = []heappush(que, (0, 0, 0))while que:cost, now, used = heappop(que)if dist[now][used] < cost:continuefor nxt, d in G[now]:new_cost = dist[now][used] + dif dist[nxt][used] > new_cost:dist[nxt][used] = new_costheappush(que, (new_cost, nxt, used))if used == 0 and dist[nxt][1] > dist[now][0]:dist[nxt][1] = dist[now][0]heappush(que, (dist[nxt][1], nxt, 1))print(0)for i in range(1, N):print(dist[i][0] + dist[i][1])