結果
問題 | No.1301 Strange Graph Shortest Path |
ユーザー | eijirou |
提出日時 | 2020-11-27 22:57:17 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,729 bytes |
コンパイル時間 | 390 ms |
コンパイル使用メモリ | 87,028 KB |
実行使用メモリ | 112,520 KB |
最終ジャッジ日時 | 2023-10-09 21:51:23 |
合計ジャッジ時間 | 18,752 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 68 ms
71,084 KB |
testcase_01 | AC | 69 ms
71,172 KB |
testcase_02 | WA | - |
testcase_03 | AC | 458 ms
102,844 KB |
testcase_04 | AC | 597 ms
112,328 KB |
testcase_05 | AC | 459 ms
103,496 KB |
testcase_06 | AC | 577 ms
108,808 KB |
testcase_07 | AC | 562 ms
107,524 KB |
testcase_08 | AC | 456 ms
103,228 KB |
testcase_09 | AC | 472 ms
106,164 KB |
testcase_10 | WA | - |
testcase_11 | AC | 517 ms
107,656 KB |
testcase_12 | AC | 486 ms
108,520 KB |
testcase_13 | AC | 453 ms
105,452 KB |
testcase_14 | AC | 585 ms
108,208 KB |
testcase_15 | AC | 406 ms
104,572 KB |
testcase_16 | AC | 546 ms
112,120 KB |
testcase_17 | AC | 494 ms
106,960 KB |
testcase_18 | AC | 510 ms
105,040 KB |
testcase_19 | AC | 425 ms
106,948 KB |
testcase_20 | AC | 490 ms
109,040 KB |
testcase_21 | AC | 479 ms
106,840 KB |
testcase_22 | AC | 540 ms
110,364 KB |
testcase_23 | AC | 424 ms
106,092 KB |
testcase_24 | AC | 580 ms
109,308 KB |
testcase_25 | AC | 549 ms
110,264 KB |
testcase_26 | AC | 509 ms
107,376 KB |
testcase_27 | AC | 434 ms
106,832 KB |
testcase_28 | AC | 415 ms
103,444 KB |
testcase_29 | WA | - |
testcase_30 | AC | 505 ms
109,632 KB |
testcase_31 | AC | 529 ms
110,428 KB |
testcase_32 | WA | - |
testcase_33 | WA | - |
testcase_34 | AC | 599 ms
109,244 KB |
ソースコード
from heapq import heappush, heappop from sys import stdin input = stdin.readline inf = 1 << 60 def main(): n, m = map(int, input().split()) edges = [[] for _ in range(n)] for _ in range(m): u, v, c, d = map(int, input().split()) edges[u-1].append([v-1, c, d]) edges[v-1].append([u-1, c, d]) for i in range(n): edges[i].sort(key=lambda x: x[0]) # dijkstra dist = [inf] * n dist[0] = 0 prev = [-1] * n heap = [] heappush(heap, (0, 0)) while heap: cost, u = heappop(heap) if u == n-1: break if dist[u] < cost: continue for v, c, d in edges[u]: if cost + c < dist[v]: dist[v] = cost + c prev[v] = u heappush(heap, (cost+c, v)) dist1 = dist[n-1] def binary_search(u, v): left = 0 right = len(edges[u]) - 1 while left < right: center = (left + right) // 2 if edges[u][center][0] < v: left = center + 1 else: right = center edges[u][left][1], edges[u][left][2] = edges[u][left][2], edges[u][left][1] u = n-1 while u > 0: v = prev[u] binary_search(u, v) binary_search(v, u) u = v # dijkstra dist = [inf] * n dist[0] = 0 heap = [] heappush(heap, (0, 0)) while heap: cost, u = heappop(heap) if u == n-1: break if dist[u] < cost: continue for v, c, d in edges[u]: if cost + c < dist[v]: dist[v] = cost + c heappush(heap, (cost+c, v)) print(dist1 + dist[n-1]) main()