結果
問題 | No.807 umg tours |
ユーザー |
👑 ![]() |
提出日時 | 2021-03-02 18:20:58 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,406 ms / 4,000 ms |
コード長 | 699 bytes |
コンパイル時間 | 251 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 166,512 KB |
最終ジャッジ日時 | 2024-10-03 01:54:13 |
合計ジャッジ時間 | 16,534 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 26 |
ソースコード
import sys from heapq import heapify,heappop,heappush input=sys.stdin.readline write=sys.stdout.write N,M=map(int,input().split()) E=[[] for _ in range(2*N+1)] for _ in range(M): a,b,c=map(int,input().split()) E[a].append((b,c)) E[a].append((b+N,c)) E[a+N].append((b+N,c)) E[b].append((a,c)) E[b].append((a+N,c)) E[b+N].append((a+N,c)) inf=float("inf") T=[inf]*(2*N+1) T[1]=T[N+1]=0 Q=[(0,1),(0,N+1)] while Q: d,x=heappop(Q) if T[x]<d: continue for y,c in E[x]: if x<=N and N<y: c=0 if T[y]>d+c: T[y]=d+c heappush(Q,(d+c,y)) X=[T[x]+T[x+N] for x in range(1,N+1)] write("\n".join(map(str,X)))