Problem:


Score : 500 points

Problem Statement

There are N cities numbered 1 to N, connected by M railroads.

You are now at City 1, with 10^{100} gold coins and S silver coins in your pocket.

The i-th railroad connects City U_i and City V_i bidirectionally, and a one-way trip costs A_i silver coins and takes B_i minutes.
You cannot use gold coins to pay the fare.

There is an exchange counter in each city. At the exchange counter in City i, you can get C_i silver coins for 1 gold coin.
The transaction takes D_i minutes for each gold coin you give.
You can exchange any number of gold coins at each exchange counter.

For each t=2, ..., N, find the minimum time needed to travel from City 1 to City t. You can ignore the time spent waiting for trains.

Constraints

2 \leq N \leq 50

N-1 \leq M \leq 100

0 \leq S \leq 10^9

1 \leq A_i \leq 50

1 \leq B_i,C_i,D_i \leq 10^9

1 \leq U_i < V_i \leq N

There is no pair i, j(i \neq j) such that (U_i,V_i)=(U_j,V_j).

Each city t=2,...,N can be reached from City 1 with some number of railroads.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M S
U_1 V_1 A_1 B_1
:
U_M V_M A_M B_M
C_1 D_1
:
C_N D_N

Output

For each t=2, ..., N in this order, print a line containing the minimum time needed to travel from City 1 to City t.

Sample Input 1

3 2 1
1 2 1 2
1 3 2 4
1 11
1 2
2 5

Sample Output 1

2
14

The railway network in this input is shown in the figure below.

In this figure, each city is labeled as follows:

The first line: the ID number i of the city (i for City i)

The second line: C_i / D_i

Similarly, each railroad is labeled as follows:

The first line: the ID number i of the railroad (i for the i-th railroad in input)

The second line: A_i / B_i

You can travel from City 1 to City 2 in 2 minutes, as follows:

Use the 1-st railroad to move from City 1 to City 2 in 2 minutes.

You can travel from City 1 to City 3 in 14 minutes, as follows:

Use the 1-st railroad to move from City 1 to City 2 in 2 minutes.

At the exchange counter in City 2, exchange 3 gold coins for 3 silver coins in 6 minutes.

Use the 1-st railroad to move from City 2 to City 1 in 2 minutes.

Use the 2-nd railroad to move from City 1 to City 3 in 4 minutes.

Sample Input 2

4 4 1
1 2 1 5
1 3 4 4
2 4 2 2
3 4 1 1
3 1
3 1
5 2
6 4

Sample Output 2

5
5
7

The railway network in this input is shown in the figure below:

You can travel from City 1 to City 4 in 7 minutes, as follows:

At the exchange counter in City 1, exchange 2 gold coins for 6 silver coins in 2 minutes.

Use the 2-nd railroad to move from City 1 to City 3 in 4 minutes.

Use the 4-th railroad to move from City 3 to City 4 in 1 minutes.

Sample Input 3

6 5 1
1 2 1 1
1 3 2 1
2 4 5 1
3 5 11 1
1 6 50 1
1 10000
1 3000
1 700
1 100
1 1
100 1

Sample Output 3

1
9003
14606
16510
16576

The railway network in this input is shown in the figure below:

You can travel from City 1 to City 6 in 16576 minutes, as follows:

Use the 1-st railroad to move from City 1 to City 2 in 1 minute.

At the exchange counter in City 2, exchange 3 gold coins for 3 silver coins in 9000 minutes.

Use the 1-st railroad to move from City 2 to City 1 in 1 minute.

Use the 2-nd railroad to move from City 1 to City 3 in 1 minute.

At the exchange counter in City 3, exchange 8 gold coins for 8 silver coins in 5600 minutes.

Use the 2-nd railroad to move from City 3 to City 1 in 1 minute.

Use the 1-st railroad to move from City 1 to City 2 in 1 minute.

Use the 3-rd railroad to move from City 2 to City 4 in 1 minute.

At the exchange counter in City 4, exchange 19 gold coins for 19 silver coins in 1900 minutes.

Use the 3-rd railroad to move from City 4 to City 2 in 1 minute.

Use the 1-st railroad to move from City 2 to City 1 in 1 minute.

Use the 2-nd railroad to move from City 1 to City 3 in 1 minute.

Use the 4-th railroad to move from City 3 to City 5 in 1 minute.

At the exchange counter in City 5, exchange 63 gold coins for 63 silver coins in 63 minutes.

Use the 4-th railroad to move from City 5 to City 3 in 1 minute.

Use the 2-nd railroad to move from City 3 to City 1 in 1 minute.

Use the 5-th railroad to move from City 1 to City 6 in 1 minute.

Sample Input 4

4 6 1000000000
1 2 50 1
1 3 50 5
1 4 50 7
2 3 50 2
2 4 50 4
3 4 50 3
10 2
4 4
5 5
7 7

Sample Output 4

1
3
5

The railway network in this input is shown in the figure below:

Sample Input 5

2 1 0
1 2 1 1
1 1000000000
1 1

Sample Output 5

1000000001

The railway network in this input is shown in the figure below:

You can travel from City 1 to City 2 in 1000000001 minutes, as follows:

At the exchange counter in City 1, exchange 1 gold coin for 1 silver coin in 1000000000 minutes.

Use the 1-st railroad to move from City 1 to City 2 in 1 minute.



Sample input:
3 2 1
1 2 1 2
1 3 2 4
1 11
1 2
2 5


Sample output:
2
14

Submission status: Accepted

Solution code:
import sys
from heapq import heappush, heappop
def input(): return sys.stdin.readline().strip()

"""
無向グラフでdpできるのが非直感的だが（というのも普通dpをするのはDAGに限るから）、
まず無向グラフは各辺に対して向きの違う有向辺が２本走っていると思えば一応有向グラフではある。

ダイクストラ自体はacyclicityは要請しないので実行可能だが、このとき各頂点への最短距離を小さい順に並べる。
    （例） S--->A--->B--->C--->D--->E
すると実は元のグラフからA--->SやC--->Bといった上の順番と逆行するような辺を除いてもダイクストラの結果は同じになる。
（というのも負辺は無いので逆向きの辺を使うと経路長が長くなるから）

そもそもダイクストラで最小値を取って更新をかけているのはまさに上のような間引いたグラフを構築しているわけで、これは
まさにDAGになっている。なのでこの上でdpを走らせることも可能。

そしてダイクストラとdpを同時に実行できる点が奇跡なのであって、本問のような一般グラフ上でのDAG生成＆dpを俗に
「拡張ダイクストラ」とも言うらしい。
"""

def main():
    N, M, S = map(int, input().split())
    MAX_S = 50 * N + 1
    repn = [[] for _ in range(N)]
    for _ in range(M):
        u, v, a, b = map(int, input().split())
        repn[u - 1].append((v - 1, a, b))
        repn[v - 1].append((u - 1, a, b))
    coin = []
    for _ in range(N):
        c, d = map(int, input().split())
        coin.append((c, d))

    """
    「最短路問題はダイクストラだが、実質それはdpと見れるらしい。」
    重要になるパラメーターは
        ・頂点　・お金　・時間
    なのでdp[v][s][x]が最初に思いつくが確実にTLE、
    ただし移動にかかるお金は制約が強いので
        dp[v][s] = (頂点vに手持ちs円でたどり着く最小の時間)
    とすればよい。
    このときお金sの状態数は上限50*(N-1)とすれば十分。
    (これだけあれば一切換金が不要なので)

    dpの遷移は「辺を移動」、「換金する」の２つあることに注意。
    この遷移を式にする際にダイクストラを用いる。
    """

    dp = [[float("inf")] * (MAX_S + 1) for _ in range(N)]
    S = min(S, MAX_S)
    q = []

    # heappushの再定義（x時間で頂点vにお金sで行けるかどうか）
    def push(x, v, s):
        if not (s < 0 or dp[v][s] <= x):
            dp[v][s] = x
            heappush(q, (x, v, s))
    
    # initialization
    push(0, 0, S)

    # dijkstra
    while q:
        x, v, s = heappop(q)
        if (dp[v][s] != x): continue # すでに別経路で同じ条件を探索済みの場合は除く。（必須ではないが高速化になる）
        # 両替するとき
        new_x = x + coin[v][1]
        new_s = min(s + coin[v][0], MAX_S)
        push(new_x, v, new_s)
        # 辺を移動するとき
        for u, a, b in repn[v]:
            push(x + b, u, s - a)
    
    # answer
    for v in range(1, N):
        ans = float("inf")
        for s in range(MAX_S):
            ans = min(ans, dp[v][s])
        print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N, M, S = map(int, input().split(" "))
adj = [ [] for _ in range(N) ] 
convert = []
for _ in range(M) :
    u, v, a, b = map(int, input().split(" "))
    adj[u-1].append( (v-1,a,b) )
    adj[v-1].append( (u-1,a,b) )

for _ in range(N) :
    c, d = map(int, input().split(" "))
    convert.append( (c, d) )  

import heapq 

limit = 2500
S = min(S, limit)
h = [ (0, 0, S) ] 
ans = [  [float('inf')]*(limit+1) for _ in range(N) ]

while h != [] :
    time_consumed, city, coin = heapq.heappop(h)
    if ans[city][coin] < time_consumed:
        continue
    ans[city][coin] = time_consumed
    
    if coin + convert[city][0] < limit and ans[city][coin + convert[city][0]] > time_consumed + convert[city][1] :
        ans[city][coin + convert[city][0]] = time_consumed + convert[city][1]
        heapq.heappush(h, (time_consumed + convert[city][1], city, coin+convert[city][0] ) )

    for v, a, b in adj[city] :
        if coin - a < 0 or ans[v][coin-a] <= time_consumed+b :
            continue
        ans[v][coin-a] = time_consumed+b
        heapq.heappush( h, (time_consumed+b, v, coin-a) )
    
for i in range(1, N) :
    print(min(ans[i]))

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.buffer.readline
from heapq import heappop,heappush
N,M,S=map(int,input().split())
graph=[[]for _ in range(N)]
for _ in range(M):
  u,v,a,b=map(int,input().split())
  graph[u-1].append((v-1,a,b))
  graph[v-1].append((u-1,a,b))
cd=[tuple(map(int,input().split())) for _ in range(N)]
INF=1e18
S=min(S,2500)
time=[[INF]*2501 for _ in range(N)]
q=[(0,0,S)]
while q:
  now_time,cur_city,cur_coin=heappop(q)
  for nxt_city,cost,dt in graph[cur_city]:
    if cur_coin>=cost and time[nxt_city][cur_coin-cost]>now_time+dt:
      time[nxt_city][cur_coin-cost]=now_time+dt
      heappush(q,(now_time+dt,nxt_city,cur_coin-cost))
  c,d=cd[cur_city]
  new_coin=min(2500,cur_coin+c)
  nxt_time=now_time+d
  if nxt_time<time[cur_city][new_coin]:
    time[cur_city][new_coin]=nxt_time
    heappush(q,(nxt_time,cur_city,new_coin))
for i in range(1,N):
  print(min(time[i]))

Submission status: Accepted

Solution code:
from heapq import heappop,heappush
import sys
input=sys.stdin.buffer.readline
N,M,S=map(int,input().split())
INF=10**18
Time=[[INF]*2501 for _ in range(N)]#[都市][お金]
graph=[[] for _ in range(N)]
S=min(S,2500)
for _ in range(M):
    u,v,a,b=map(int,input().split())
    graph[u-1].append((v-1,a,b))
    graph[v-1].append((u-1,a,b))

cd=[tuple(map(int,input().split())) for _ in range(N)]

hq=[(0,0,S)] #時間、都市、金
while hq:
    ct,cur_city,si=heappop(hq)
    for nxt_city,cost,t in graph[cur_city]:#都市、費用、所要時間
        if si>=cost:
            new_t=ct+t
            if new_t<Time[nxt_city][si-cost]:
              Time[nxt_city][si-cost]=new_t
              heappush(hq,(new_t,nxt_city,si-cost))
    c,d=cd[cur_city]
    v_new=min(si+c,2500)
    t_new=ct+d
    if t_new<Time[cur_city][v_new]:
      Time[cur_city][v_new]=t_new
      heappush(hq,(t_new,cur_city,v_new))
for i in range(1,N):
    print(min(Time[i]))

Submission status: Accepted

Solution code:
max_s = 2500

n,m,s = map(int, input().split())
s = min(s, max_s)
conv = lambda i,j : i*10000+j

G = [[] for i in range(conv(n-1, max_s)+1)]
for i in range(m):
    u,v,a,b = map(int, input().split())
    u,v = u-1, v-1
    for j in range(max_s+1):
        if j-a >= 0:
            G[conv(u,j)].append((conv(v,j-a), b))
            G[conv(v,j)].append((conv(u,j-a), b))

for i in range(n):
    c,d = map(int, input().split())
    for j in range(max_s+1):
        if j+c > max_s:
            break
        G[conv(i,j)].append((conv(i,j+c), d))

from heapq import heappush, heappop
def dijkstra(G, start):
    n = len(G)
    dist = [float("inf")]*n
    visited = set()
    heap = [(0, start)]

    while heap and len(visited) != n:
        d, cur = heappop(heap)
        if cur in visited:
            continue
        visited.add(cur)
        dist[cur] = d
        for to, cost in G[cur]:
            if to not in visited:
                heappush(heap, (d+cost, to))
    return dist

dist = dijkstra(G, conv(0, s))
for i in range(1,n):
    cost = min(dist[conv(i,0):conv(i,max_s)+1])
    print(cost)

Submission status: Accepted

Solution code:
N,M,S=map(int,input().split())
from heapq import heappop,heappush 

inf = float('inf')
cost=[[] for _ in range(N)]
exc=[]


for _ in range(M):
    u,v,a,b=map(int,input().split())
    u,v=u-1,v-1
    cost[u].append((v,a,b))
    cost[v].append((u,a,b))
for _ in range(N):
    c,d=map(int,input().split())
    exc.append((c,d))

S=min(S,2450)
di=[inf]*2451*N
di[S]=0
hq=[(0,S)] #時間,都市名*2451+銀貨

while hq:
    t,v=heappop(hq)
    u=v//2451 #都市名
    s=v%2451 #所持金
    if t>di[v]:
        continue

    for x,a,b in cost[u]:
        if s>=a:
            v_new=x*2451+s-a
            t_new=t+b
            if t_new<di[v_new]:
                di[v_new]=t_new
                heappush(hq,(t_new,v_new))
    
    c,d=exc[u]
    c=min(c,2450-s)
    v_new=v+c
    t_new=t+d
    if t_new<di[v_new]:
        di[v_new]=t_new
        heappush(hq,(t_new,v_new))

for i in range(1,N):
    m=min(di[i*2451:(i+1)*2451])
    print(m)

Submission status: Accepted

Solution code:
N,M,S=map(int,input().split())
from heapq import heappop,heappush 

inf = 10**18
cost=[[] for _ in range(N)]
exc=[]


for _ in range(M):
    u,v,a,b=map(int,input().split())
    u,v=u-1,v-1
    cost[u].append((v,a,b))
    cost[v].append((u,a,b))
for _ in range(N):
    c,d=map(int,input().split())
    exc.append((c,d))

di=[inf]*2451*N
if S>2450:
    S=2450
di[S]=0
hq=[(0,S)] #時間,都市名*2451+銀貨

while hq:
    t,v=heappop(hq)
    u=v//2451 #都市名
    s=v%2451 #所持金

    for x,a,b in cost[u]:
        if s>=a:
            v_new=x*2451+s-a
            t_new=t+b
            if t_new<di[v_new]:
                di[v_new]=t_new
                heappush(hq,(t_new,v_new))
    
    c,d=exc[u]
    if s+c>2450:
        c=2450-s
    v_new=v+c
    t_new=t+d
    if t_new<di[v_new]:
        di[v_new]=t_new
        heappush(hq,(t_new,v_new))

for i in range(1,N):
    m=di[i*2451]
    for j in range(1,2451):
        m=min(m,di[i*2451+j])
    print(m)

Submission status: Accepted

Solution code:
from heapq import heappop, heappush, heapify

def main():
    N, M, S = map(int, input().split())
    S = min(S, 2500)
    edge = [[] for _ in range(N)]
    for _ in range(M):
        U, V, A, B = map(int, input().split())
        U -= 1
        V -= 1
        edge[U].append((V, A, B))
        edge[V].append((U, A, B))
    exchange = []
    for _ in range(N):
        C, D = map(int, input().split())
        exchange.append((C,D))

    dp = [[float('inf')] * 2510 for _ in range(N)]
    dp[0][S] = 0

    q = [(0,0,S)]
    while q:
        dist, v, money = heappop(q)
        if dp[v][money] < dist:
            continue
        for nv, fare, cost in edge[v]:
            nm = money - fare
            if nm < 0:
                continue
            if dp[nv][nm] > dp[v][money] + cost:
                dp[nv][nm] = dp[v][money] + cost
                heappush(q, (dp[nv][nm], nv, nm))
        
        nm = min(money+exchange[v][0], 2500)
        if dp[v][nm] > dp[v][money] + exchange[v][1]:
            dp[v][nm] = dp[v][money] + exchange[v][1]
            heappush(q, (dp[v][nm], v, nm))

    for i in range(1,N):
        print(min(dp[i]))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N,M,S=map(int,input().split())
from heapq import heappop,heappush 

inf = float('inf')
cost=[[] for _ in range(N)]
exc=[]


for _ in range(M):
    u,v,a,b=map(int,input().split())
    u,v=u-1,v-1
    cost[u].append((v,a,b))
    cost[v].append((u,a,b))
for _ in range(N):
    c,d=map(int,input().split())
    exc.append((c,d))

di=[inf]*2451*N
if S>2450:
    S=2450
di[S]=0
hq=[(0,S)] #時間,都市名*2451+銀貨

while hq:
    t,v=heappop(hq)
    u=v//2451 #都市名
    s=v%2451 #所持金

    for x,a,b in cost[u]:
        if s>=a:
            v_new=x*2451+s-a
            t_new=t+b
            if t_new<di[v_new]:
                di[v_new]=t_new
                heappush(hq,(t_new,v_new))
    
    c,d=exc[u]
    if s+c>2450:
        c=2450-s
    v_new=v+c
    t_new=t+d
    if t_new<di[v_new]:
        di[v_new]=t_new
        heappush(hq,(t_new,v_new))

for i in range(1,N):
    m=di[i*2451]
    for j in range(1,2451):
        m=min(m,di[i*2451+j])
    print(m)

Submission status: Accepted

Solution code:
N,M,S=map(int,input().split())
from heapq import heappop,heappush 

inf = float('inf')
cost=[[] for _ in range(N)]
exc=[]


for _ in range(M):
    u,v,a,b=map(int,input().split())
    u,v=u-1,v-1
    cost[u].append((v,a,b))
    cost[v].append((u,a,b))
for _ in range(N):
    c,d=map(int,input().split())
    exc.append((c,d))

di=[inf]*2451*N
if S>2450:
    S=2450
di[S]=0
hq=[(0,S)] #時間,都市名*2451+銀貨

while hq:
    t,v=heappop(hq)
    if t>di[v]:
        continue
    u=v//2451 #都市名
    s=v%2451 #所持金

    for x,a,b in cost[u]:
        if s>=a:
            v_new=x*2451+s-a
            t_new=t+b
            if t_new<di[v_new]:
                di[v_new]=t_new
                heappush(hq,(t_new,v_new))
    
    c,d=exc[u]
    if s+c>2450:
        c=2450-s
    v_new=v+c
    t_new=t+d
    if t_new<di[v_new]:
        di[v_new]=t_new
        heappush(hq,(t_new,v_new))

for i in range(1,N):
    m=di[i*2451]
    for j in range(1,2451):
        m=min(m,di[i*2451+j])
    print(m)

Submission status: Accepted

Solution code:
INF=10**30
from heapq import heappush,heappop,heapify
def dijkstra(G,coin,s,n):
    que=[(0,[coin,s])]
    dist=[[INF]*n for i in range(2501)]
    dist[coin][s]=0
    while que:
        mincost,co=heappop(que)
        nowc,nowv=co[0],co[1]
        if(mincost>dist[nowc][nowv]):
            continue
        for v,c,x in G[nowc][nowv]:
            if(dist[nowc][nowv]+c<dist[x][v]):
                dist[x][v]=dist[nowc][nowv]+c
                heappush(que,(dist[x][v],[x,v]))
    return dist

N,M,S=map(int,input().split())
if(S>=2500):
    S=2500
G=[[[] for i in range(N)] for i in range(2501)]
for i in range(M):
    u,v,a,b=map(int,input().split())
    u,v=u-1,v-1
    for i in range(2501):
        if i-a>=0:
            G[i][u].append([v,b,i-a])
            G[i][v].append([u,b,i-a])
for i in range(N):
    c,d=map(int,input().split())
    for j in range(2500):
        if j+c<=2500:
            G[j][i].append([i,d,j+c])

dist=dijkstra(G,S,0,N)

for i in range(1,N):
    res=10**30
    for j in range(2501):
        res=min(res,dist[j][i])
    print(res)

Submission status: Accepted

Solution code:
# E - Two Currencies

import heapq

n, m, s = map(int, input().split())
adj = {u: [] for u in range(1, n+1)}
max_silver = 0
for i in range(m):
    u, v, a, b = map(int, input().split())
    adj[u].append((v, a, b)) # to, 料金, 時間
    adj[v].append((u, a, b)) # to, 料金, 時間
    max_silver += a # 全路線の料金の総和 (これ以上は不要)
exch = {}
for u in range(1, n+1):
    c, d = map(int, input().split())
    exch[u] = (c, d) # レート, 時間

s = min(s, max_silver) # max_silverまでで十分

# n <= 50, m <= 100, max_silver <= 5000

# (都市,所有銀貨)を頂点とする最短経路問題
# Dijkstra
dist = {(1, s): 0}  # 開始頂点のみ距離0
queue = [(0, 1, s)]
dmin = {1: 0} # dmin[u] = min(dist[(u, si)] for si)
nfin = 1      # 距離が決まった都市数

while len(queue) > 0:
    di, u, si = heapq.heappop(queue)
    # 用済みのデータ
    if (u, si) in dist and di > dist[(u, si)]:
        continue
    # 都市uの距離を保存
    if u not in dmin:
        dmin[u] = di
        nfin += 1
        if nfin >= n:  # 全都市の距離が決まった
            break
    # uから直接行ける各都市について
    for v, a, b in adj[u]:
        if si < a:  # 銀貨不足
            continue
        xsi = si - a
        if (v, xsi) not in dist or \
            dist[(v, xsi)] > di + b:
            dist[(v, xsi)] = di + b
            heapq.heappush(queue, (di + b, v, xsi))
    # 両替による遷移
    c, d = exch[u]
    xsi = min(si + c, max_silver)
    if (u, xsi) not in dist or \
        dist[(u, xsi)] > di + d:
        dist[(u, xsi)] = di + d
        heapq.heappush(queue, (di + d, u, xsi))

for u in range(2, n+1):
    print(dmin[u])

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

n, m, s = nm()
N = n * 3001
G = [list() for _ in range(N)]
for _ in range(m):
    u, v, a, b = nm()
    u -= 1; v -= 1
    for j in range(0, N, n):
        if v + j - a * n >= 0:
            G[u + j].append((v + j - a * n, b))
        if u + j - a * n >= 0:
            G[v + j].append((u + j - a * n, b))
for u in range(n):
    c, d = nm()
    for j in range(0, N, n):
        G[u + j].append((min(u + j + c * n, u + N - n), d))

import heapq as hq

def dijkstra(G, s, t=None):
    """
    G[v] = [(x1, c1), (x2, c2), ...]
    """
    dist = [-1]*len(G)
    dist[s] = 0
    q = [(0, s)]
    while q:
        d, v = hq.heappop(q)
        if d > dist[v]: continue
        for x, c in G[v]:
            if dist[x] < 0 or dist[x] > d + c:
                dist[x] = d + c
                hq.heappush(q, (d + c, x))
    if t is None:
        return dist
    else:
        return dist[t]

dist = dijkstra(G, min(s, 3000) * n)
for i in range(1, n):
    print(min(dist[i::n]))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    import queue
    mod=10**9+7
    N,M,S=MI()
    #各頂点，所持金が０〜N*50までなので，状態すうはN*(N*50+1)
    #頂点iでj枚ならi*(N*50+1)+j
    NN=N*50+1
    ##########################################
    import heapq
    class Dijkstra():
        """
        ・有向 / 無向は問わない(無向の場合は，逆向きの辺もたす)
        ・負のコストがない場合のみ
        ・計算量はO(E log|V|)　
        ・heapを使うことで頂点を走査する必要がなくなる（代わりに，距離更新したものは確定でなくともqueに入れておく）
        """
        
        #最短のpathをたす
        
        
        class Edge():
            #重み付き有向辺
            
            def __init__(self, _to, _cost):
                self.to =_to
                self.cost = _cost
        
        def __init__(self, V):
            #引数Vは頂点数
            self.G = [[] for _ in range(V)] #隣接リストG[u][i]が頂点uのi番目の辺
            self. _E = 0 #辺の数
            self._V = V #頂点数
        
        #proparty - 辺の数
        def E(self):
            return self._E
        
        #proparty - 頂点数
        def V(self):
            return self._V
        
        def add(self, _from, _to, _cost):
            #2頂点と辺のコストを追加
            self.G[_from].append(self.Edge(_to,_cost))
            self._E +=1
            
        def add2(self, _from, _to, _cost):
            #2頂点と辺のコスト（無向）を追加
            self.G[_from].append(self.Edge(_to, _cost))
            self.G[_to].append(self.Edge(_from, _cost))
            self._E +=2
            
        def shortest_path(self,s):#,g):
            #始点sから頂点iまでの最短経路長のリストを返す
            
            que = [] #priority queue
            d = [float("inf")] * self.V()
            prev = [None]*self.V() #prev[j]は，sからjへ最短経路で行くときのjの一つ前の場所
            d[s] = 0
            heapq.heappush(que,(0,s)) #始点の距離と頂点番号をヒープに追加
            
            while len(que)!=0:
                #キューに格納されてある中で一番コストが小さい頂点を取り出す
                cost,v = heapq.heappop(que)
                
                #キューに格納された最短経路長候補がdの距離よりも大きい場合に処理をスキップ
                if d[v] < cost:
                    continue
                    
                #頂点vに隣接する各頂点iに対して，vを経由した場合の距離を計算して，これがd[i]よりも小さい場合に更新
                for i in range(len(self.G[v])):
                    e = self.G[v][i] #vのi個目の隣接辺
                    if d[e.to] > d[v] + e.cost:
                        d[e.to] = d[v] + e.cost #更新
                        prev[e.to] = v
                        heapq.heappush(que,(d[e.to],e.to)) #queに新たな最短経路長候補を追加
            
            """#sからgまでの最短経路
            path = []
            pos = g #今いる場所，ゴールで初期化
            for _ in range(self.V()+1):
                path.append(pos)
                if pos == s:
                    break
                #print("pos:",format(pos))
                pos = prev[pos]
            path.reverse()
            #print(path)"""
                        
            return d#,path
    ########################
    djk=Dijkstra(N*NN)
    
    for i in range(M):
        u,v,a,b=MI()
        u-=1
        v-=1
        for j in range(a,NN):
            djk.add(u*NN+j,v*NN+j-a,b)
            djk.add(v*NN+j,u*NN+j-a,b)
    for i in range(N):
        c,d=MI()
        for j in range(0,NN-c,1):
            djk.add(i*NN+j,i*NN+j+c,d)
            
    dL=djk.shortest_path(min(S,NN-1))
    for i in range(1,N):
        ans=10**20
        for j in range(0,NN):
            ans=min(ans,dL[i*NN+j])
        print(ans)
        
        
    

main()

Submission status: Accepted

Solution code:
import heapq
import sys

def main():

    n,m,s = map(int,input().split())
    uvab = [list(map(int,input().split())) for _ in range(m)]
    cd = [list(map(int,input().split())) for _ in range(n)]

    edges = [[[] for _ in range(n)] for _ in range(2501)]

    for u,v,a,b in uvab:
        for i in range(a,2501):
            edges[i][u-1].append(((v-1, i-a), b))
            edges[i][v-1].append(((u-1, i-a), b))

    for i in range(n):
        c,d = cd[i]
        for j in range(2501):
            edges[j][i].append(((i, min(j+c, 2500)), d))

    def dijkstra(edges, c):
        hq = []
        d = [[10**20] * n for _ in range(c)]
        d[min(2500, s)][0] = 0
        heapq.heappush(hq, (0, (0, min(2500, s))))
        while hq:
            d1, p = heapq.heappop(hq)
            for p2, d2 in edges[p[1]][p[0]]:
                if d[p2[1]][p2[0]] == -1 or d[p2[1]][p2[0]] > d1 + d2:
                    d[p2[1]][p2[0]] = d1 + d2
                    heapq.heappush(hq, (d1+d2, p2))
        return d

    dis = dijkstra(edges, 2501)
    ans = [10**20]*n
    for i in range(2501):
        for j in range(n):
            ans[j] = min(ans[j], dis[i][j])

    for i in ans[1:]:
        print(i)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys;input=sys.stdin.readline
from heapq import *
def dijkstra(s,cost):
    d = [float("inf")] * NN
    used = [False] * NN
    d[s] = 0
    while True:
        v = -1
        for i in range(NN):
            if (not used[i]) and (v == -1):
                v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
            return d
        used[v] = True
        for j, c in cost[v]:
            d[j] = min(d[j],d[v]+c)

def dijkstra_heapq(s, cost):
    d = [float("inf")] * NN
    h = [(0, s)]
    d[s] = 0
    while h:
        vc, v = heappop(h)
#        print(h)
        if vc > d[v]:
            continue
        for j, c in cost[v]:
            if vc+c<d[j]:
                d[j] = vc+c
                heappush(h, (vc+c, j))
    return d

N,W,S = map(int,input().split())
V = 2500
NN = N*(V+1)

def enc(u, v):
    return u*NN + v

#print(NN)
cost = [[] for _ in range(NN)]
for i in range(W):
    x,y,z,u = map(int,input().split())
    x -= 1
    y -= 1
    for v in range(V+1):
        if v-z>=0:
            cost[x*(V+1)+v].append((y*(V+1)+v-z, u))
            cost[y*(V+1)+v].append((x*(V+1)+v-z, u))

for i in range(N):
    x, y = map(int, input().split())
    for v in range(V+1):
        cost[i*(V+1)+v].append((i*(V+1)+min(v+x, V), y))

S = min(V, S)
d = dijkstra_heapq(S,cost)
for i in range(1, N):
    print(min(d[i*(V+1):(i+1)*(V+1)]))

Submission status: Accepted

Solution code:
import sys


import heapq
class Dijkstra:
    INF = 10**18

    def __init__(self, N, Graph=[[-1]]):
        self.N = (N+1)
        self.dist = [self.INF] * (N+1)
        if Graph[0][0]!=-1: self.G = Graph
        else: self.G = [[] for _ in range(N+1)]

    def insert(self, From, To, Cost):
        self.G[From].append([To, Cost])

    def reset(self):
        for i in range(self.N): self.dist[i] = self.INF

    def dijkstra(self, st):
        self.reset()
        hq = [(0, st)]
        heapq.heapify(hq)
        while len(hq):
            tmp = heapq.heappop(hq)
            now, now_dist = tmp[1], tmp[0]
            if self.dist[now] <= now_dist: continue
            self.dist[now] = now_dist
            for to in self.G[now]:
                heapq.heappush(hq, (now_dist+to[1], to[0]))

def main():
    input=sys.stdin.readline
    n, m, s = map(int, input().split())
    MAX_MONEY = 2600
    dj = Dijkstra((n+1)*(MAX_MONEY+1))

    for i in range(m):
        a, b, c, d = map(int, input().split())
        a, b = a-1, b-1
        for j in range(c, MAX_MONEY):
            dj.insert(a*MAX_MONEY+j, b*MAX_MONEY+(j-c), d)
            dj.insert(b*MAX_MONEY+j, a*MAX_MONEY+(j-c), d)

    for i in range(n):
        a, b = map(int, input().split())
        for j in range(MAX_MONEY-a-1):
            dj.insert(i*MAX_MONEY+j, i*MAX_MONEY+(j+a), b)

    s = min(s, MAX_MONEY-1)
    dj.dijkstra(0*MAX_MONEY+s)

    for i in range(1, n):
        ans = 10**18
        for j in range(MAX_MONEY):ans = min(ans, dj.dist[i*MAX_MONEY + j])
        print(ans)

if __name__=="__main__":
  main()

Submission status: Accepted

Solution code:
import heapq
def main():
    N, M, S = map(int, input().split())
    money_max = 50*N
    S = min(S, money_max)
    dp = [[float("inf")]*(money_max+1) for _ in range(N)]
    dp[0][S] = 0
    G = [[] for _ in range(N)]
    exchange = [None]*N
    for _ in range(M):
        u, v, a, b = map(int, input().split())
        u, v = u-1, v-1
        G[u].append([v, a, b])
        G[v].append([u, a, b])
    for i in range(N):
        c, d = map(int, input().split())
        exchange[i] = [c, d]
    q = []
    heapq.heapify(q)
    heapq.heappush(q, [0, 0, S])
    while 0 < len(q):
        pre_time, idx, s = heapq.heappop(q)
        if dp[idx][s] < pre_time:
            continue
        ex = min(s + exchange[idx][0], money_max)
        if dp[idx][s] + exchange[idx][1] < dp[idx][ex]:
            dp[idx][ex] = dp[idx][s] + exchange[idx][1]
            heapq.heappush(q, [dp[idx][ex], idx, ex])
        for to, money, time in G[idx]:
            if money <= s:
                if dp[idx][s] + time < dp[to][s-money]:
                    dp[to][s-money] = dp[idx][s] + time
                    heapq.heappush(q, [dp[to][s-money], to, s-money])
    for i in range(1, N):
        print(min(dp[i]))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#!python3

from heapq import heappop, heappush


INF = 10 ** 18

# input
N, M, S = list(map(int, input().split()))
UVAB = [list(map(int, input().split())) for _ in range(M)]
CD = [list(map(int, input().split())) for _ in range(N)]


def solve(link):
    ans = {}
    lim = 50 * (N - 1)
    w = [[INF] * (lim + 1) for _ in range(N)]

    # (time, node, silver)
    hq = [(0, 0, min(S, lim))]
    while hq:
        t, v, s = heappop(hq)
        if t > w[v][s]:
            continue
        if v not in ans:
            ans[v] = t
            if len(ans) == N:
                break
        
        # buy
        if s < lim:
            c, d = CD[v]
            new_s = min(lim, s + c)
            new_t = t + d
            if new_t < w[v][new_s]:
                w[v][new_s] = new_t
                heappush(hq, (new_t, v, new_s))
        
        # move
        for u, a, b in link[v]:
            if s < a:
                continue
            new_s = s - a
            new_t = t + b
            if new_t < w[u][new_s]:
                w[u][new_s] = new_t
                heappush(hq, (new_t, u, new_s))
        
    return ans


def main():
    link = [[] for _ in range(N)]
    for u, v, a, b in UVAB:
        link[u - 1].append((v - 1, a, b))
        link[v - 1].append((u - 1, a, b))
    
    ans = solve(link)
    for i in range(1, N):
        print(ans[i])


if __name__ == "__main__":
    main()