結果

問題 No.1301 Strange Graph Shortest Path
コンテスト
ユーザー Kiri8128
提出日時 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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 28 WA * 5
権限があれば一括ダウンロードができます

ソースコード

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