結果
問題 | No.807 umg tours |
ユーザー |
|
提出日時 | 2023-09-05 15:00:33 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 875 bytes |
コンパイル時間 | 458 ms |
コンパイル使用メモリ | 82,432 KB |
実行使用メモリ | 212,608 KB |
最終ジャッジ日時 | 2024-06-23 10:37:27 |
合計ジャッジ時間 | 18,214 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 24 TLE * 1 -- * 1 |
ソースコード
import sysfrom collections import dequeinput = sys.stdin.readlineN, M = map(int, input().split())ABC = [list(map(int, input().split())) for _ in range(M)]G = [[] for _ in range(N)]for i in range(M):a, b, c = ABC[i]a -= 1b -= 1G[a].append([b, c])G[b].append([a, c])dist = [[float('inf')]*2 for _ in range(N)]dist[0][0] = 0que = deque([(0, 0)])while que:now, isused = que.popleft()for nxt, d in G[now]:if dist[nxt][isused] <= dist[now][isused]:continueif dist[nxt][isused] > dist[now][isused] + d:dist[nxt][isused] = dist[now][isused] + dque.append((nxt, isused))if isused == 0 and dist[nxt][1] > dist[now][0]:dist[nxt][1] = dist[now][0]que.append((nxt, 1))print(0)for i in range(1, N):print(dist[i][0] + dist[i][1])