結果
問題 | No.1301 Strange Graph Shortest Path |
ユーザー | 👑 rin204 |
提出日時 | 2022-11-02 16:16:46 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 880 bytes |
コンパイル時間 | 278 ms |
コンパイル使用メモリ | 87,208 KB |
実行使用メモリ | 101,820 KB |
最終ジャッジ日時 | 2023-09-24 05:18:07 |
合計ジャッジ時間 | 22,053 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 72 ms
71,288 KB |
testcase_01 | AC | 70 ms
71,504 KB |
testcase_02 | WA | - |
testcase_03 | AC | 359 ms
91,568 KB |
testcase_04 | AC | 518 ms
100,760 KB |
testcase_05 | AC | 323 ms
91,720 KB |
testcase_06 | AC | 469 ms
98,008 KB |
testcase_07 | AC | 429 ms
95,560 KB |
testcase_08 | AC | 391 ms
91,872 KB |
testcase_09 | AC | 476 ms
98,112 KB |
testcase_10 | WA | - |
testcase_11 | AC | 489 ms
98,140 KB |
testcase_12 | AC | 526 ms
98,768 KB |
testcase_13 | AC | 460 ms
95,152 KB |
testcase_14 | AC | 480 ms
96,788 KB |
testcase_15 | AC | 453 ms
96,312 KB |
testcase_16 | AC | 518 ms
101,448 KB |
testcase_17 | AC | 438 ms
95,244 KB |
testcase_18 | AC | 401 ms
93,452 KB |
testcase_19 | AC | 492 ms
98,952 KB |
testcase_20 | AC | 486 ms
100,148 KB |
testcase_21 | AC | 452 ms
96,064 KB |
testcase_22 | AC | 487 ms
100,744 KB |
testcase_23 | AC | 442 ms
95,712 KB |
testcase_24 | AC | 490 ms
100,128 KB |
testcase_25 | AC | 515 ms
100,428 KB |
testcase_26 | AC | 454 ms
96,708 KB |
testcase_27 | AC | 506 ms
97,976 KB |
testcase_28 | AC | 379 ms
91,788 KB |
testcase_29 | WA | - |
testcase_30 | AC | 523 ms
99,672 KB |
testcase_31 | AC | 495 ms
100,484 KB |
testcase_32 | WA | - |
testcase_33 | WA | - |
testcase_34 | AC | 419 ms
97,744 KB |
ソースコード
from heapq import * n, m = map(int, input().split()) C = [0] * m D = [0] * m edges = [[] for _ in range(n)] for i in range(m): u, v, C[i], D[i] = map(int, input().split()) u -= 1 v -= 1 edges[u].append((v, i)) edges[v].append((u, i)) def dijkstra(): dist = [1 << 60] * n dist[0] = 0 bV = [-1] * n bE = [-1] * n hq = [0] while hq: tmp = heappop(hq) d = tmp // n pos = tmp - n * d if d > dist[pos]: continue for npos, i in edges[pos]: nd = d + C[i] if nd < dist[npos]: dist[npos] = nd bV[npos] = pos bE[npos] = i heappush(hq, nd * n + npos) p = n - 1 while p != 0: i = bE[p] C[i] = D[i] p = bV[p] return dist[-1] ans = dijkstra() + dijkstra() print(ans)