結果

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

ソースコード

diff # 

from heapq import *
import sys

sys.setrecursionlimit(10**6)
int1 = lambda x: int(x)-1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.buffer.readline())
def MI(): return map(int, sys.stdin.buffer.readline().split())
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MI1(): return map(int1, sys.stdin.buffer.readline().split())
def LI1(): return list(map(int1, sys.stdin.buffer.readline().split()))
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]
def BI(): return sys.stdin.buffer.readline().rstrip()
def SI(): return sys.stdin.buffer.readline().rstrip().decode()
inf = 10**16
# md = 10 ** 9 + 7
md = 998244353

n,m=MI()
to=[[] for _ in range(n)]
uve={}
for e in range(m):
    u,v,c,d=MI()
    u,v=u-1,v-1
    to[u].append((e,v,c,d))
    to[v].append((e,u,c,d))
    uve[u,v]=uve[v,u]=e

ans=0
ot=[-1]*n
hp=[]
dd=[inf]*n
dd[0]=0
heappush(hp,(0,0))
while hp:
    dis,u=heappop(hp)
    if u==n-1:
        ans+=dis
        break
    if dis>dd[u]:continue
    for e,v,c,d in to[u]:
        nd=dis+c
        if nd>=dd[v]:continue
        dd[v]=nd
        ot[v]=u
        heappush(hp,(nd,v))

# print(ot)
# print(dd)
# print(ans)

use=[False]*m
u=n-1
while u:
    e=uve[u,ot[u]]
    use[e]=True
    u=ot[u]

hp=[]
dd=[inf]*n
dd[0]=0
heappush(hp,(0,0))
while hp:
    dis,u=heappop(hp)
    if u==n-1:
        ans+=dis
        break
    if dis>dd[u]:continue
    for e,v,c,d in to[u]:
        if use[e]:nd=dis+d
        else:nd=dis+c
        if nd>=dd[v]:continue
        dd[v]=nd
        heappush(hp,(nd,v))

# print(ot)
# print(dd)
print(ans)
0