結果
問題 | No.1301 Strange Graph Shortest Path |
ユーザー | zkou |
提出日時 | 2020-11-04 22:41:53 |
言語 | PyPy3 (7.3.15) |
結果 |
RE
|
実行時間 | - |
コード長 | 1,325 bytes |
コンパイル時間 | 343 ms |
コンパイル使用メモリ | 82,584 KB |
実行使用メモリ | 130,152 KB |
最終ジャッジ日時 | 2024-09-13 00:36:35 |
合計ジャッジ時間 | 12,433 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 39 ms
53,264 KB |
testcase_01 | AC | 37 ms
53,412 KB |
testcase_02 | RE | - |
testcase_03 | RE | - |
testcase_04 | RE | - |
testcase_05 | RE | - |
testcase_06 | RE | - |
testcase_07 | RE | - |
testcase_08 | RE | - |
testcase_09 | RE | - |
testcase_10 | RE | - |
testcase_11 | RE | - |
testcase_12 | RE | - |
testcase_13 | RE | - |
testcase_14 | RE | - |
testcase_15 | RE | - |
testcase_16 | RE | - |
testcase_17 | RE | - |
testcase_18 | RE | - |
testcase_19 | RE | - |
testcase_20 | RE | - |
testcase_21 | RE | - |
testcase_22 | RE | - |
testcase_23 | RE | - |
testcase_24 | RE | - |
testcase_25 | RE | - |
testcase_26 | RE | - |
testcase_27 | RE | - |
testcase_28 | RE | - |
testcase_29 | RE | - |
testcase_30 | RE | - |
testcase_31 | RE | - |
testcase_32 | WA | - |
testcase_33 | WA | - |
testcase_34 | AC | 545 ms
125,620 KB |
ソースコード
import sys from heapq import * input = sys.stdin.readline INF = 1001001001 mask32 = (1 << 32) - 1 N, M = map(int, input().split()) adj = [dict() for _ in range(N)] uv2d = dict() for _ in range(M): u, v, c, d = map(int, input().split()) u -= 1 v -= 1 adj[u][v] = adj[v][u] = c uv2d[(u, v)] = uv2d[(v, u)] = d # pq が持つのは、(コスト << 32) + 頂点 # dijkstra 1回目 pq = [0] dp = [INF] * N dp[0] = 0 parent = [-1] * N while pq: t = heappop(pq) cost = t >> 32 v = t & mask32 if cost > dp[v]: continue for nv, dist in adj[v].items(): if dp[nv] > dp[v] + dist: dp[nv] = dp[v] + dist parent[nv] = v heappush(pq, (dp[nv] << 32) + nv) first_cost = dp[N - 1] v = N - 1 while v != 0: p = parent[v] adj[v][p] = adj[p][v] = uv2d[(v, p)] v = p # pq が持つのは、(コスト << 32) + 頂点 # dijkstra 2回目 pq = [N - 1] dp = [INF] * N dp[N - 1] = 0 # parent = [-1] * N while pq: t = heappop(pq) cost = t >> 32 v = t & mask32 if cost > dp[v]: continue for nv, dist in adj[v].items(): if dp[nv] > dp[v] + dist: dp[nv] = dp[v] + dist # parent[nv] = v heappush(pq, (dp[nv] << 32) + nv) second_cost = dp[0] print(first_cost + second_cost)