結果

問題 No.3393 Move on Highway
コンテスト
ユーザー titia
提出日時 2025-11-28 22:07:26
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,487 ms / 3,000 ms
コード長 922 bytes
コンパイル時間 311 ms
コンパイル使用メモリ 82,056 KB
実行使用メモリ 142,940 KB
最終ジャッジ日時 2025-11-28 22:08:02
合計ジャッジ時間 31,121 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
input = sys.stdin.readline

from heapq import heappop,heappush

N,M,C=map(int,input().split())

E=[[] for i in range(N)]

for i in range(M):
    a,b,c=map(int,input().split())
    a-=1
    b-=1

    E[a].append((b,c))
    E[b].append((a,c))

D=[1<<63]*N
D[0]=0
Q=[(0,0)]

while Q:
    dis,ind=heappop(Q)

    if D[ind]!=dis:
        continue

    for to,length in E[ind]:
        if D[to]>D[ind]+length+C:
            D[to]=D[ind]+length+C
            heappush(Q,(D[to],to))

ANS=[D[-1]]*N

D2=[(1<<63,0)]*N
D2[N-1]=(0,0)
Q=[((0,0),N-1)]

while Q:
    (dis,m),ind=heappop(Q)

    if D2[ind]!=(dis,m):
        continue

    for to,length in E[ind]:
        m2=max(m,length)
        dis2=dis+m+length-m2+C
        
        if D2[to]>(dis2,m2):
            D2[to]=(dis2,m2)
            heappush(Q,(D2[to],to))

for i in range(1,N):
    x=D2[i][0]

    ANS[i]=min(ANS[i],x+D[i])

print("\n".join(map(str,ANS[1:])))
0