abc 164 E - Two Currencies (python)

拡張ダイクストラで解く。総時間、頂点に加えて今持っている銀貨の数を追加して heap に入れる。時間を増やす要因が通過時間と通貨を交換する時間の二つ（疲れているのでダジャレみたいになっている）あるので、交換するか、移動するかで分けて考える。移動に必要な銀貨が足りないものは heap に入れなければok
ほんとは 1 から i までの最短時間を n回ダイクストラで求めたいのだが、それだと TLE したので、heap なので初めて頂点 i に到着した時間 == 1 から i までの最短時間とすることができるので、頂点に初めて到着するごとに、その頂点とかかった時間をリストに入れて、頂点順に並び替えて出力した。これで青diff ですか…

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from heapq import heappush, heappop

N,M,S = map(int,readline().split())
ABC = [list(map(int,readline().split())) for _ in range(M)]
m = map(int,read().split())
CD = list(zip(m,m))

graph = [[] for _ in range(N)]
for u,v,a,b in ABC:
    graph[u-1].append((v-1,a,b))
    graph[v-1].append((u-1,a,b))

def f():
  INF = 10 ** 18
  arrive = [False]*N # その頂点に到着したことがあるか
  ans = []
  qq = 2451
  dist = [[INF] * qq for _ in range(N)]
  dist[0][min(qq-1,S)] = 0
  q = [(0,min(qq-1,S),0)]
  while q:
      st,ss,v = heappop(q) # 総時間、銀貨、今いる頂点
      if dist[v][ss] < st:
        continue
      if not arrive[v]:
        arrive[v] = True
        ans.append((v,st)) # 初めて頂点 v に来たなら、その頂点と時間をリストにいれる
        if all(arrive):
          break
      c,d = CD[v]
      # 銀貨の購入
      if ss < qq-1:
          ns = min(ss + c, qq-1)
          nt = st + d
          if dist[v][ns] > nt:
              dist[v][ns] = nt
              heappush(q,(nt,ns,v)) # 銀貨を購入するだけで移動はしない
      # 移動
      for nex,g,tt in graph[v]: # 次の頂点、必要な銀貨、通過にかかる時間
          if ss-g < 0:
              continue
          dt = st + tt
          if dist[nex][ss-g] <= dt:
# heapに入れる前に最小値を更新しないと分かっているものは枝刈りしておくと若干早くなる
              continue
          dist[nex][ss-g] = dt
          heappush(q,(dt,ss-g,nex))
  return ans

ab = f()
from operator import itemgetter
ab = sorted(ab,key=itemgetter(0)) # 頂点順に並び替え
for i in range(1,N):
  print(ab[i][1])