結果
問題 | No.807 umg tours |
ユーザー | silversmith |
提出日時 | 2019-04-05 06:08:39 |
言語 | PyPy3 (7.3.15) |
結果 |
MLE
|
実行時間 | - |
コード長 | 1,083 bytes |
コンパイル時間 | 1,061 ms |
コンパイル使用メモリ | 86,668 KB |
実行使用メモリ | 819,544 KB |
最終ジャッジ日時 | 2023-08-28 22:39:11 |
合計ジャッジ時間 | 10,228 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 120 ms
77,588 KB |
testcase_01 | AC | 132 ms
78,144 KB |
testcase_02 | AC | 139 ms
77,932 KB |
testcase_03 | AC | 133 ms
77,948 KB |
testcase_04 | AC | 121 ms
77,680 KB |
testcase_05 | AC | 116 ms
77,760 KB |
testcase_06 | AC | 139 ms
78,356 KB |
testcase_07 | AC | 125 ms
78,040 KB |
testcase_08 | AC | 85 ms
71,492 KB |
testcase_09 | AC | 82 ms
71,120 KB |
testcase_10 | AC | 83 ms
71,252 KB |
testcase_11 | MLE | - |
testcase_12 | -- | - |
testcase_13 | -- | - |
testcase_14 | -- | - |
testcase_15 | -- | - |
testcase_16 | -- | - |
testcase_17 | -- | - |
testcase_18 | -- | - |
testcase_19 | -- | - |
testcase_20 | -- | - |
testcase_21 | -- | - |
testcase_22 | -- | - |
testcase_23 | -- | - |
testcase_24 | -- | - |
testcase_25 | -- | - |
ソースコード
import os import sys import heapq N, M = map(int, input().split(' ')) e={} for i in range(N): for j in range(N): e[(i,j)] = sys.maxsize for i in range(M): v1, v2, cost = [int(x) for x in input().split(' ')] e[(v1 -1, v2 -1)] = cost e[(v2 -1, v1 -1)] = cost d = [sys.maxsize] * N d_exe = [sys.maxsize] * N d[0] = 0 d_exe[0] = 0 h = [] for i in range(N): heapq.heappush(h, (d[i],i)) while len(h) > 0: p = heapq.heappop(h) for idx, (_, i) in enumerate(h): if e[(p[1], i)] < sys.maxsize: alt = p[0] + e[(p[1], i)] if d[i] < alt : continue d[i] = alt h[idx] = (alt, i) heapq.heapify(h) h = [] for i in range(N): heapq.heappush(h, (d_exe[i],i)) while len(h) > 0: p = heapq.heappop(h) for idx, (_, i) in enumerate(h): if e[(p[1], i)] < sys.maxsize: alt = min(p[0] + e[(p[1], i)], d[p[1]]) if d_exe[i] < alt : continue d_exe[i] = alt h[idx] = (alt, i) heapq.heapify(h) for i in range(N): print(d[i] + d_exe[i])