結果
問題 | No.807 umg tours |
ユーザー |
|
提出日時 | 2023-09-05 14:53:34 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 861 bytes |
コンパイル時間 | 485 ms |
コンパイル使用メモリ | 82,172 KB |
実行使用メモリ | 173,208 KB |
最終ジャッジ日時 | 2024-06-23 10:31:16 |
合計ジャッジ時間 | 19,944 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 24 TLE * 1 -- * 1 |
ソースコード
from collections import dequeN, 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))for i in range(N):if i == 0:print(0)else:print(sum(dist[i]))