結果

問題 No.3393 Move on Highway
コンテスト
ユーザー ああ
提出日時 2026-03-23 22:35:43
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 1,721 ms / 3,000 ms
コード長 757 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 141 ms
コンパイル使用メモリ 85,632 KB
実行使用メモリ 164,376 KB
最終ジャッジ日時 2026-03-23 22:36:23
合計ジャッジ時間 37,668 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import heapq
n,m,c=map(int,input().split())
v=[[] for i in range(n)]
for i in range(m):
  q,w,e=map(int,input().split())
  q-=1;w-=1
  v[q].append((w,e));v[w].append((q,e))
x=[];heapq.heappush(x,(0,0))
y=[1<<60]*n;y[0]=0
while x:
  q,w=heapq.heappop(x)
  if y[w]<q:
    continue
  for i,j in v[w]:
    if y[i]>q+j+c:
      y[i]=q+j+c
      heapq.heappush(x,(y[i],i))
a,b=[1<<60]*n,[1<<60]*n
a[-1]=0;b[-1]=0
x=[];heapq.heappush(x,(0,n-1,0))
while x:
  q,w,e=heapq.heappop(x)
  if a[w]<q and b[w]<q-e:
    continue
  for i,j in v[w]:
    if q+c+j-max(j,e)<b[i]:
      b[i]=q+c+j-max(j,e)
      heapq.heappush(x,(q+c+j,i,max(j,e)))
    if q+c+j<a[i]:
      a[i]=q+c+j
      heapq.heappush(x,(a[i],i,max(e,j)))
for i in range(1,n):
  print(min(y[-1],y[i]+b[i]))
0