結果

問題 No.1301 Strange Graph Shortest Path
ユーザー tktk_snsn
提出日時 2020-11-27 22:53:55
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,264 bytes
コンパイル時間 575 ms
コンパイル使用メモリ 82,132 KB
実行使用メモリ 101,612 KB
最終ジャッジ日時 2024-07-26 20:09:05
合計ジャッジ時間 23,389 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 28 WA * 5
権限があれば一括ダウンロードができます

ソースコード

diff # 

import heapq
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)
U = 10 ** 5
inf = 10**18

n, m = map(int, input().split())
edge = [[] for _ in range(n)]
cost = dict()
for _ in range(m):
    a, b, c, d = map(int, input().split())
    a -= 1
    b -= 1
    if a > b:
        a, b = b, a
    edge[a].append(b)
    edge[b].append(a)
    cost[a * U + b] = (c, d)

dist = [inf] * n
prev = [-1] * n
dist[0] = 0
que = [(0, 0)]
while que:
    ds, s = heapq.heappop(que)
    if dist[s] < ds:
        continue
    for t in edge[s]:
        a, b = min(s, t), max(s, t)
        dt = cost[a * U + b][0]
        if dist[t] > ds + dt:
            dist[t] = ds + dt
            prev[t] = s
            heapq.heappush(que, (ds + dt, t))
ans = dist[n - 1]
s = n - 1
while prev[s] != -1:
    t = prev[s]
    a, b = min(s, t), max(s, t)
    c, d = cost[a * U + b]
    cost[a * U + b] = (d, -1)
    s = t


dist = [inf] * n
dist[n - 1] = 0
que = [(0, n - 1)]
while que:
    ds, s = heapq.heappop(que)
    if dist[s] < ds:
        continue
    for t in edge[s]:
        a, b = min(s, t), max(s, t)
        dt = cost[a * U + b][0]
        if dist[t] > ds + dt:
            dist[t] = ds + dt
            heapq.heappush(que, (ds + dt, t))

ans += dist[0]
print(ans)
0