結果

問題 No.1301 Strange Graph Shortest Path
ユーザー Kiri8128Kiri8128
提出日時 2020-11-27 22:09:01
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,189 bytes
コンパイル時間 385 ms
コンパイル使用メモリ 82,272 KB
実行使用メモリ 120,028 KB
最終ジャッジ日時 2024-09-13 01:00:22
合計ジャッジ時間 20,693 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 39 ms
53,688 KB
testcase_01 AC 40 ms
53,944 KB
testcase_02 WA -
testcase_03 AC 475 ms
108,716 KB
testcase_04 AC 677 ms
119,584 KB
testcase_05 AC 439 ms
111,680 KB
testcase_06 AC 616 ms
114,700 KB
testcase_07 AC 598 ms
113,156 KB
testcase_08 AC 432 ms
109,096 KB
testcase_09 AC 600 ms
113,384 KB
testcase_10 WA -
testcase_11 AC 615 ms
115,732 KB
testcase_12 AC 648 ms
116,840 KB
testcase_13 AC 596 ms
113,596 KB
testcase_14 AC 581 ms
112,652 KB
testcase_15 AC 536 ms
112,192 KB
testcase_16 AC 656 ms
120,028 KB
testcase_17 AC 562 ms
115,576 KB
testcase_18 AC 525 ms
111,960 KB
testcase_19 AC 628 ms
116,296 KB
testcase_20 AC 595 ms
116,372 KB
testcase_21 AC 552 ms
114,288 KB
testcase_22 AC 615 ms
117,268 KB
testcase_23 AC 545 ms
114,520 KB
testcase_24 AC 616 ms
116,496 KB
testcase_25 AC 638 ms
117,976 KB
testcase_26 AC 561 ms
114,760 KB
testcase_27 AC 610 ms
115,424 KB
testcase_28 AC 551 ms
111,108 KB
testcase_29 WA -
testcase_30 AC 671 ms
117,328 KB
testcase_31 AC 635 ms
118,024 KB
testcase_32 WA -
testcase_33 WA -
testcase_34 AC 607 ms
117,848 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = lambda: sys.stdin.readline().rstrip()
from heapq import heapify, heappush as hpush, heappop as hpop
N, M = map(int, input().split())
X = [[] for _ in range(N)]
for _ in range(M):
    a, b, c, d = map(int, input().split())
    X[a-1].append([b-1, c, d, -1])
    X[b-1].append([a-1, c, d, X[a-1][-1]])
    X[a-1][-1][-1] = X[b-1][-1]

def dijkstra(n, E, i0=0, tp=0):
    s, t = 0, n - 1
    kk = 18
    mm = (1 << kk) - 1
    h = [i0]
    D = [-1] * n
    done = [0] * n
    D[i0] = 0
    
    while h:
        x = hpop(h)
        d, i = x >> kk, x & mm
        if done[i]: continue
        done[i] = 1
        for j, w, _, _ in E[i]:
            nd = d + w
            if D[j] < 0 or D[j] > nd:
                if done[j] == 0:
                    hpush(h, (nd << kk) + j)
                    D[j] = nd
    if tp: return D[-1]
    i = t
    PT = [t]
    while i != s:
        for k, (j, w, _, _) in enumerate(E[i]):
            if D[i] == D[j] + w:
                E[i][k][1] = E[i][k][2]
                E[i][k][3][1] = E[i][k][3][2]
                i = j
                PT.append(i)
                break
    return D[-1]

print(dijkstra(N, X) + dijkstra(N, X, 0, 1))
0