結果
問題 | No.807 umg tours |
ユーザー |
![]() |
提出日時 | 2020-11-22 10:53:11 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 3,593 ms / 4,000 ms |
コード長 | 1,515 bytes |
コンパイル時間 | 449 ms |
コンパイル使用メモリ | 82,728 KB |
実行使用メモリ | 343,756 KB |
最終ジャッジ日時 | 2024-07-23 16:22:32 |
合計ジャッジ時間 | 35,168 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 26 |
ソースコード
import sys,collections,heapqdef MI(): return map(int,sys.stdin.readline().rstrip().split())class Dijkstra:def __init__(self):self.e = collections.defaultdict(list)def add(self, u, v, d, directed=False):if directed is False: # 無向グラフの場合self.e[u].append([v, d])self.e[v].append([u, d])else: # 有向グラフの場合self.e[u].append([v, d])def delete(self, u, v):self.e[u] = [_ for _ in self.e[u] if _[0] != v]self.e[v] = [_ for _ in self.e[v] if _[0] != u]def search(self, s): # sから各頂点までの最短距離d = collections.defaultdict(lambda: float('inf'))d[s] = 0q = []heapq.heappush(q, (0, s))v = collections.defaultdict(bool)while len(q):k, u = heapq.heappop(q)if v[u]:continuev[u] = Truefor uv, ud in self.e[u]:if v[uv]:continuevd = k + udif d[uv] > vd:d[uv] = vdheapq.heappush(q, (vd, uv))return dN,M = MI()Di = Dijkstra()for _ in range(M):a,b,c = MI()Di.add((a,0),(b,0),c,directed=False)Di.add((a,1),(b,1),c,directed=False)Di.add((a,0),(b,1),0,directed=True)Di.add((b,0),(a,1),0,directed=True)dist = Di.search((1,0))for i in range(1,N+1):print(dist[(i,0)]+dist[(i,1)] if i != 1 else 0)