結果

問題 No.807 umg tours
ユーザー takeya_okinotakeya_okino
提出日時 2022-07-14 22:52:38
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
WA  
実行時間 -
コード長 1,234 bytes
コンパイル時間 335 ms
コンパイル使用メモリ 12,672 KB
実行使用メモリ 112,880 KB
最終ジャッジ日時 2024-06-26 07:39:42
合計ジャッジ時間 32,287 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 AC 36 ms
11,008 KB
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 AC 36 ms
11,136 KB
testcase_07 WA -
testcase_08 AC 31 ms
11,008 KB
testcase_09 AC 32 ms
11,008 KB
testcase_10 AC 32 ms
10,880 KB
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 TLE -
testcase_25 -- -
権限があれば一括ダウンロードができます

ソースコード

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