結果
問題 | No.807 umg tours |
ユーザー |
![]() |
提出日時 | 2019-03-22 22:13:00 |
言語 | PyPy3 (7.3.15) |
結果 |
MLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 861 bytes |
コンパイル時間 | 732 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 850,672 KB |
最終ジャッジ日時 | 2024-11-23 19:02:38 |
合計ジャッジ時間 | 18,861 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 25 MLE * 1 |
ソースコード
import sys input = sys.stdin.readline N,M=map(int,input().split()) E=[list(map(int,input().split())) for i in range(M)] EDGE=[[] for i in range(N+1)] for x,y,c in E: EDGE[x].append([y,c]) EDGE[y].append([x,c]) MIN=[float("inf")]*(N+1) MIN2=[float("inf")]*(N+1) MIN[1]=0 MIN2[1]=0 from collections import deque QUE=deque([[1,0,0]]) while QUE: town,dist,maxdist=QUE.popleft() for to,cost in EDGE[town]: Flag=0 if maxdist>cost: maxdist_town=maxdist else: maxdist_town=cost if MIN[to]>dist+cost: MIN[to]=dist+cost Flag=1 if MIN2[to]>dist+cost-maxdist_town: MIN2[to]=dist+cost-maxdist_town Flag=1 if Flag: QUE.append([to,dist+cost,maxdist_town]) for i in range(1,N+1): print(MIN[i]+MIN2[i])