結果

問題 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))
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0