結果
問題 | No.807 umg tours |
ユーザー |
![]() |
提出日時 | 2021-12-01 22:59:42 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,516 bytes |
コンパイル時間 | 146 ms |
コンパイル使用メモリ | 82,152 KB |
実行使用メモリ | 182,172 KB |
最終ジャッジ日時 | 2024-07-05 00:49:34 |
合計ジャッジ時間 | 25,037 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 4 WA * 20 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'), 0] for _ in range(N)]#普通のダイクストラdef dijkstra():D[0] = 0q = []heapq.heappush(q, [0, 0])while len(q) > 0:# ヒープから取り出し_, u = heapq.heappop(q)for i in E[u]:if D[i[0]] > D[u] + i[1]:# 頂点までのコストが更新できれば更新してヒープに登録D[i[0]] = D[u] + i[1]heapq.heappush(q, [D[u] + i[1], i[0]])return D#コスト-最大値の最小を取っていくダイクストラdef dijkstra2():D2[0][0] = 0q = []heapq.heappush(q, [0, 0]) #コスト、頂点while len(q) > 0:# ヒープから取り出し_, u = heapq.heappop(q)for i in E[u]:if D2[i[0]][1] > i[1]:if D2[i[0]][0] > D2[u][0] + i[1]:D2[i[0]][0] = D2[u][0] + i[1]heapq.heappush(q, [D2[i[0]][0], i[0]])else:if D2[i[0]][0] > D2[u][0] + D2[u][1]:D2[i[0]][0] = D2[u][0] + D2[u][1]D2[i[0]][1] = i[1]heapq.heappush(q, [D2[i[0]][0], i[0]])return D2dijkstra()dijkstra2()ans = [0] * Nfor i in range(N):print(D[i] + D2[i][0])