結果
問題 | No.807 umg tours |
ユーザー |
![]() |
提出日時 | 2024-09-03 03:01:48 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 3,197 ms / 4,000 ms |
コード長 | 875 bytes |
コンパイル時間 | 654 ms |
コンパイル使用メモリ | 82,292 KB |
実行使用メモリ | 173,664 KB |
最終ジャッジ日時 | 2024-12-15 19:39:27 |
合計ジャッジ時間 | 30,620 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 26 |
ソースコード
from collections import defaultdictfrom heapq import heappush, heappopINF = 1 << 60N, M = map(int, input().split())adj = defaultdict(list)for _ in range(M):a, b, c = map(int, input().split())a -= 1b -= 1adj[a].append((b, c))adj[b].append((a, c))dists = [[INF] * 2 for _ in range(N)]q = [(0, 0, 0)] # (距離, チケット使用回数, 頂点)while q:d, cnt, v = heappop(q)if dists[v][cnt] <= d: continuedists[v][cnt] = d# チケットを使うif cnt == 0:for to, _ in adj[v]:if dists[to][1] <= d: continueheappush(q, (d, 1, to))# チケットを使わないfor to, cost in adj[v]:if dists[to][cnt] <= d+cost: continueheappush(q, (d+cost, cnt, to))dists[0][0] = dists[0][1] = 0for i in range(N):ans = dists[i][0] + dists[i][1]print(ans)