結果

問題 No.1301 Strange Graph Shortest Path
ユーザー Kiri8128Kiri8128
提出日時 2020-11-27 22:09:01
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,189 bytes
コンパイル時間 429 ms
コンパイル使用メモリ 87,280 KB
実行使用メモリ 121,640 KB
最終ジャッジ日時 2023-10-10 21:43:23
合計ジャッジ時間 22,419 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 77 ms
71,304 KB
testcase_01 AC 77 ms
71,504 KB
testcase_02 WA -
testcase_03 AC 504 ms
110,096 KB
testcase_04 AC 721 ms
121,180 KB
testcase_05 AC 483 ms
113,536 KB
testcase_06 AC 657 ms
116,432 KB
testcase_07 AC 639 ms
115,172 KB
testcase_08 AC 475 ms
110,208 KB
testcase_09 AC 638 ms
115,352 KB
testcase_10 WA -
testcase_11 AC 664 ms
117,632 KB
testcase_12 AC 692 ms
118,000 KB
testcase_13 AC 639 ms
115,788 KB
testcase_14 AC 630 ms
114,712 KB
testcase_15 AC 592 ms
114,136 KB
testcase_16 AC 707 ms
121,640 KB
testcase_17 AC 617 ms
117,544 KB
testcase_18 AC 568 ms
113,100 KB
testcase_19 AC 674 ms
117,076 KB
testcase_20 AC 632 ms
117,828 KB
testcase_21 AC 591 ms
116,708 KB
testcase_22 AC 654 ms
119,224 KB
testcase_23 AC 579 ms
116,096 KB
testcase_24 AC 651 ms
117,696 KB
testcase_25 AC 675 ms
119,624 KB
testcase_26 AC 595 ms
115,536 KB
testcase_27 AC 644 ms
117,060 KB
testcase_28 AC 580 ms
112,972 KB
testcase_29 WA -
testcase_30 AC 708 ms
119,760 KB
testcase_31 AC 658 ms
119,632 KB
testcase_32 WA -
testcase_33 WA -
testcase_34 AC 631 ms
118,340 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