結果

問題 No.807 umg tours
ユーザー takeya_okinotakeya_okino
提出日時 2022-07-14 22:52:38
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
WA  
実行時間 -
コード長 1,234 bytes
コンパイル時間 335 ms
コンパイル使用メモリ 12,672 KB
実行使用メモリ 112,880 KB
最終ジャッジ日時 2024-06-26 07:39:42
合計ジャッジ時間 32,287 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 5 TLE * 1 WA * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

from heapq import heappop, heappush

def dijkstra(start, dist, path):
  candidate = [(0, start)]
 
  while candidate:
    cost, i = heappop(candidate)
    if cost > dist[i]: continue
 
    for c, j in path[i]:
      if cost+c >= dist[j]: continue
      dist[j] = cost+c
      heappush(candidate, (cost+c, j))

def dijkstra2(start, dist, path):
  candidate = [(0, start, 0)]
 
  while candidate:
    cost, i, k = heappop(candidate)
    if cost > dist[i]: continue
 
    for c, j in path[i]:
      if k == 0:
        if cost >= dist[j + n]: continue
        dist[j + n] = cost
        heappush(candidate, (cost, j, 1))
        if cost+c >= dist[j]: continue
        dist[j] = cost+c
        heappush(candidate, (cost+c, j, 0))
      else:
        if cost+c >= dist[j + n]: continue
        dist[j + n] = cost+c
        heappush(candidate, (cost+c, j, 1))
 
inf = 10**18+1
n, m = map(int, input().split(" "))

EDGES = [set() for _ in range(n)]

for _ in range(m):
  a, b, c = [int(x)-1 for x in input().split(" ")]
  c += 1
  EDGES[a].add((c, b))
  EDGES[b].add((c, a))
 
to_ = [inf]*n
to_[0] = 0
to2 = [inf]*(2 * n)
to2[0] = 0
to2[n] = 0
dijkstra(0, to_, EDGES)
dijkstra2(0, to2, EDGES)
 
for i in range(n):
  print(to_[i] + to2[i + n])
0