Submission #47799948

---

Source Code Expand

#ABC164E Two Currencies

from sortedcontainers import SortedSet,SortedList

#入力受取
N,M,S=map(int,input().split()); G=[[] for _ in range(N)]
for _ in range(M):
    u,v,a,b=map(int,input().split())
    G[u-1].append((v-1,a,b));G[v-1].append((u-1,a,b))
H=[tuple(map(int,input().split())) for _ in range(N)]

#DP[i][s]: 地点iに銀貨s枚を持って到達する最短時間
DP=[[10**18]*2501 for _ in range(N)]

#sortedcontainersを用いたDijkstra法を行う  もちろん不利
Q=SortedSet([(0,0,min(S,2500))])  #経過時間, 現在地, 残銀貨
while Q:
    time,now,money=Q.pop(0)
    if DP[now][money]<time: continue
    DP[now][money]=time

    #両替を行う遷移
    rate,cost=H[now]
    if DP[now][min(2500,money+rate)]>time+cost:
        DP[now][min(2500,money+rate)]=time+cost
        Q.add((time+cost,now,min(2500,money+rate)))

    #次の目的地に移動する遷移
    for next,need,cost in G[now]:
        if money<need: continue  #おかねがたりません
        if DP[next][money-need]>time+cost:
            DP[next][money-need]=time+cost
            Q.add((time+cost,next,money-need))

#答えを出力
for i in range(1,N): print(min(DP[i]))

Submission Info

Judge Result