結果
問題 | No.807 umg tours |
ユーザー |
![]() |
提出日時 | 2021-12-02 20:12:57 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,229 bytes |
コンパイル時間 | 216 ms |
コンパイル使用メモリ | 82,560 KB |
実行使用メモリ | 171,480 KB |
最終ジャッジ日時 | 2024-07-05 02:04:14 |
合計ジャッジ時間 | 22,550 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 24 TLE * 1 -- * 1 |
ソースコード
N,M = map(int,input().split())ABC = [list(map(int,input().split())) for _ in range(M)]E = [[] for _ in range(N)]for a,b,c in ABC:E[a-1].append([b-1,c])E[b-1].append([a-1,c])import heapqD = [float('inf')] * ND2 = [float('inf')] * N#普通のダイクストラdef dijkstra():D[0] = 0q = []heapq.heappush(q, [0, 0])while len(q) > 0:# ヒープから取り出し_, u = heapq.heappop(q)for i in E[u]:a,b = iif D[a] > D[u] + b:# 頂点までのコストが更新できれば更新してヒープに登録D[a] = D[u] + bheapq.heappush(q, [D[a], a])return D#コスト-最大値の最小を取っていくダイクストラdef dijkstra2():D2[0] = 0q = []heapq.heappush(q, [0, 0]) #コスト、頂点while len(q) > 0:# ヒープから取り出し_, u = heapq.heappop(q)for i in E[u]:a,b = itmp = min(D[u],D2[u] + b)if D2[a] > tmp:D2[a] = tmpheapq.heappush(q, [D2[a], a])return D2dijkstra()dijkstra2()ans = [0] * Nfor i in range(N):print(D[i] + D2[i])