結果
問題 |
No.807 umg tours
|
ユーザー |
👑 ![]() |
提出日時 | 2025-07-14 23:29:46 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,435 ms / 4,000 ms |
コード長 | 1,207 bytes |
コンパイル時間 | 240 ms |
コンパイル使用メモリ | 82,296 KB |
実行使用メモリ | 178,840 KB |
最終ジャッジ日時 | 2025-07-14 23:52:31 |
合計ジャッジ時間 | 16,192 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 26 |
ソースコード
import sys from sys import stdin #重み有グラフの最短経路問題 #隣接リストは[隣接点,コスト]で入っていること #負の重不可 import heapq def Dijkstra(lis,start): ret = [float("inf")] * len(lis) ret[start] = 0 end_flag = [False] * len(lis) end_num = 0 q = [(0,start)] while len(q) > 0: ncost,now = heapq.heappop(q) if end_flag[now]: continue end_flag[now] = True end_num += 1 if end_num == len(lis): break for nex,ecost in lis[now]: if ret[nex] > ncost + ecost: ret[nex] = ncost + ecost heapq.heappush(q , (ret[nex] , nex)) return ret N,M = map(int,stdin.readline().split()) lis = [ [] for i in range(2*N)] for i in range(N): lis[i].append( (i+N,0) ) for i in range(M): a,b,c = map(int,stdin.readline().split()) a -= 1 b -= 1 lis[a].append( (b,c) ) lis[b].append( (a,c) ) lis[a+N].append( (b+N,c) ) lis[b+N].append( (a+N,c) ) lis[a].append( (b+N,0) ) lis[b].append( (a+N,0) ) dlis = Dijkstra(lis,0) ans = [ dlis[i]+dlis[i+N] for i in range(N) ] print (*ans,sep="\n")