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 heapq

#dg = 10**7#ノード数より多く取る

n,m, S = map(int,input().split()) #n:頂点数　m:辺の数

edge = [[] for i in range(n)]
#edge[i] : iから出る道の[重み,行先]の配列


Cs=[]
Ds=[]
amax=0
for _ in range(m):
    u, v, a, b = map(int,input().split())
    edge[u-1].append([v-1,a,b])
    edge[v-1].append([u-1,a,b])#有向グラフの場合コメント
    amax=max(a,amax)

for _ in range(n):
    c, d = map(int,input().split())
    Cs.append(c)
    Ds.append(d)

dg=(n-1)*amax

def cut(S): 
    return min(S,dg)

S=cut(S)

def dijkstra(start):

    #dijkstra
    # d : minimum distance from s
    d = [[10**20]*(dg+1) for _ in range(n)]
    d[start][cut(S)] = 0
    edgelist = []

    heapq.heappush(edgelist,(Ds[0], 0, cut(S+Cs[0])))

    for e in edge[start]:
        if S-e[1]>=0:
            heapq.heappush(edgelist,(e[2],e[0],S-e[1]))

    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        t,ce,cs = minedge[0],minedge[1],minedge[2]
        #print(t,ce,cs)
        if  d[ce][cs]== 10**20:
            d[ce][cs] = t
            ns=cut(cs+Cs[ce])
            #print(ce,ns)
            if d[ce][ns]==10**20:
                #d[ce][ns]=t+Ds[ce]
                heapq.heappush(edgelist, (t+Ds[ce],ce,ns))

            for e in edge[ce]:
                if cs>=e[1]:
                    #print(e)
                    ne=e[0]
                    ns=cs-e[1]
                    if d[ne][ns]==10**20:
                        #print(ne)
                        heapq.heappush(edgelist, (t+e[2],ne,ns))
    return d

d=dijkstra(start=0)
for x in d[1:]:
    print(min(x))
#print(d)

Submission status: Accepted

Solution code:
import heapq

#dg = 10**7#ノード数より多く取る

n,m, S = map(int,input().split()) #n:頂点数　m:辺の数

edge = [[] for i in range(n)]
#edge[i] : iから出る道の[重み,行先]の配列


Cs=[]
Ds=[]
amax=0
for _ in range(m):
    u, v, a, b = map(int,input().split())
    edge[u-1].append([v-1,a,b])
    edge[v-1].append([u-1,a,b])#有向グラフの場合コメント
    amax=max(a,amax)

for _ in range(n):
    c, d = map(int,input().split())
    Cs.append(c)
    Ds.append(d)

dg=(n-1)*amax

def cut(S): 
    if S>dg:
        return dg
    else: return S

S=cut(S)

def dijkstra(start):

    #dijkstra
    # d : minimum distance from s
    d = [[10**20]*(dg+1) for _ in range(n)]
    d[start][cut(S)] = 0
    edgelist = []

    heapq.heappush(edgelist,(Ds[0], 0, cut(S+Cs[0])))

    for e in edge[start]:
        if S-e[1]>=0:
            heapq.heappush(edgelist,(e[2],e[0],S-e[1]))

    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        t,ce,cs = minedge[0],minedge[1],minedge[2]
        #print(t,ce,cs)
        if  d[ce][cs]== 10**20:
            d[ce][cs] = t
            ns=cut(cs+Cs[ce])
            #print(ce,ns)
            if d[ce][ns]==10**20:
                #d[ce][ns]=t+Ds[ce]
                heapq.heappush(edgelist, (t+Ds[ce],ce,ns))

            for e in edge[ce]:
                if cs>=e[1]:
                    #print(e)
                    ne=e[0]
                    ns=cs-e[1]
                    if d[ne][ns]==10**20:
                        #print(ne)
                        heapq.heappush(edgelist, (t+e[2],ne,ns))
    return d

d=dijkstra(start=0)
for x in d[1:]:
    print(min(x))
#print(d)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n, m, s = LI()
s = min(s, 2500)
uvab = [LI() for _ in range(m)]
cd = [LI() for _ in range(n)]
dp = [[inf]*(2500+1) for _ in range(n+1)]
dp[0][s] = 0
edges = [[] for _ in range(n)]
exchange = [[c,d] for c,d in cd]
for u,v,a,b in uvab:
    edges[u-1].append((v-1, a, b))
    edges[v-1].append((u-1, a, b))
for i, (c,d) in enumerate(cd):
    edges[i].append((i, -c, d))

h = [(0, 0, s)]
while h:
    dist, u, coin = heappop(h)
    if dp[u][coin] < dist:
        continue
    for v, a, b in edges[u]:
        if 2500 >= coin-a >= 0:
            if dp[u][coin] + b < dp[v][coin-a]:
                dp[v][coin-a] = dp[u][coin] + b
                heappush(h,(dp[v][coin-a], v, coin-a))

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

Submission status: Accepted

Solution code:
import heapq
n, m, s = map(int, input().split())
s = min(s, 2499)
UV = [[] for _ in range(n)]
for i in range(m):
    u, v, a, b = map(int, input().split())
    u -= 1
    v -= 1
    UV[u].append((v, a, b))
    UV[v].append((u, a, b))
CD = [tuple(map(int, input().split()))for _ in range(n)]
MAXS = 2500
NV = MAXS*n
edges = [[] for _ in range(NV)]


def to_v(i, j):
    return MAXS*i+j

for i, (c, d) in enumerate(CD):
    for j in range(MAXS-c):
        edges[to_v(i, j)].append((d, to_v(i, j)+c))

for i in range(n):
    for i2, a, b in UV[i]:
        for j in range(MAXS-a):
            edges[to_v(i, a+j)].append((b, to_v(i2, j)))


def dijkstra(init_v):
    next_v = [(0, init_v)]
    INF = 10**18
    dist = [INF]*NV
    dist[init_v] = 0
    while next_v:
        d, v = heapq.heappop(next_v)
        if dist[v] < d:
            continue
        for d, v2 in edges[v]:
            if dist[v2] <= dist[v]+d:
                continue
            dist[v2] = dist[v]+d
            heapq.heappush(next_v, (dist[v2], v2))
    return dist


INF = 10**18
dist = dijkstra(s)
for i in range(1, n):
    ans = INF
    for j in range(MAXS):
        ans = min(ans, dist[to_v(i, j)])
    print(ans)

Submission status: Accepted

Solution code:
def main():
    import heapq
    
    def dijkstra(graph,start,cd,s):
        dist = [[float("inf")]*2505 for _ in range(n)]
        q = []
        dist[start][s] = 0
        heapq.heappush(q, (0,start,s))
        
        while q:
            cost, cur_node,coin = heapq.heappop(q)
            
            if dist[cur_node][coin] < cost:
                continue
            
            for nex_node,nex_cost,nex_time  in graph[cur_node]:
                if coin >= nex_cost and dist[nex_node][coin-nex_cost] > cost+nex_time:
                    dist[nex_node][coin-nex_cost] = cost+nex_time
                    heapq.heappush(q, (cost+nex_time,nex_node,coin-nex_cost))
            if dist[cur_node][min(2500,coin+cd[cur_node][0])] > cost+cd[cur_node][1]:
                 dist[cur_node][min(2500,coin+cd[cur_node][0])] = cost+cd[cur_node][1]
                 heapq.heappush(q,(cost+cd[cur_node][1],cur_node,min(2500,coin+cd[cur_node][0])))
                    
        for i in dist[1:]:
            print(min(i))
    n,m,s = map(int,input().split())
    E = [[] for i in range(n)]
    la = []
    for i in range(m):
        u,v,a,b = map(int,input().split())
        u -= 1
        v-= 1
        la.append(a)
        E[u].append((v,a,b))
        E[v].append((u,a,b))

    cd = [list(map(int,input().split())) for i in range(n)]

    dijkstra(E,0,cd,min(s,2500))
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import heapq
n, m, s = map(int, input().split())
s = min(s, 2499)
UV = [[] for _ in range(n)]
A_cost = []
B_dist = []
for i in range(m):
    u, v, a, b = map(int, input().split())
    u -= 1
    v -= 1
    UV[u].append((v, i))
    UV[v].append((u, i))
    A_cost.append(a)
    B_dist.append(b)

C_income = []
D_dist = []
for _ in range(n):
    c, d = map(int, input().split())
    C_income.append(c)
    D_dist.append(d)

NV = 2500*n
edges = [[] for _ in range(NV)]

for i in range(n):
    c = C_income[i]
    d = D_dist[i]
    for j in range(2500-c):
        edges[2500*i+j].append((d, 2500*i+j+c))

for i in range(n):
    for j, k in UV[i]:
        a = A_cost[k]
        b = B_dist[k]
        for x in range(2500-a):
            edges[2500*i+x+a].append((b, 2500*j+x))


def dijkstra(init_v):
    next_v = [(0, init_v)]
    INF = 10**18
    dist = [INF]*(NV)
    dist[init_v] = 0
    while next_v:
        d, v = heapq.heappop(next_v)
        if dist[v] < d:
            continue
        for d, v2 in edges[v]:
            if dist[v2] <= dist[v]+d:
                continue
            dist[v2] = dist[v]+d
            heapq.heappush(next_v, (dist[v2], v2))
    return dist


INF = 10**18
dist = dijkstra(s)
for i in range(1, n):
    ans = INF
    for j in range(2500):
        ans = min(ans, dist[2500*i+j])
    print(ans)

Submission status: Accepted

Solution code:
import sys,heapq
input = sys.stdin.buffer.readline

n,m,s = map(int,input().split())
if s >= 2500:
    s = 2499

dg = 2500
INF = 10**15

dist = [INF]*(n*dg)

edge = [[] for i in range(n)]
a = [0]*m
b = [0]*m

for i in range(m):
    u,v,aa,bb = map(int,input().split())
    a[i] = aa
    b[i] = bb
    edge[u-1].append( (i,v-1))
    edge[v-1].append( (i,u-1) )


c = [0]*n
d = [0]*n

for i in range(n):
    cc,dd = map(int,input().split())
    c[i] = cc
    d[i] = dd

tank = [(0,s)]
nonused = [True]*(n*dg)


while tank:
    tim,fr = heapq.heappop(tank)
    if dist[fr] != INF:
        continue
    dist[fr] = tim
    pos,mon = divmod(fr,dg)

    for idx,go in edge[pos]:
        if mon >= a[idx] and dist[go*dg + mon-a[idx]] == INF:
            heapq.heappush(tank,(tim + b[idx] ,go*dg + mon-a[idx] ))
            
    if mon + c[pos] < dg and dist[fr + c[pos]] == INF:
        heapq.heappush(tank,(tim + d[pos] ,fr + c[pos] ))
    elif mon + c[pos] >= dg and dist[pos*dg + dg-1] == INF:
        heapq.heappush(tank,(tim + d[pos] ,pos*dg + dg-1 ))

for i in range(1,n):
    res = INF
    for j in range(dg):
        if dist[i*dg+j] < res:
            res = dist[i*dg+j]
    print(res)

Submission status: Accepted

Solution code:
import sys,heapq
input = sys.stdin.buffer.readline

n,m,s = map(int,input().split())
if s >= 2500:
    s = 2499

dg = 2500
INF = 10**15

dist = [INF]*(n*dg)

edge = [[] for i in range(n)]
a = [0]*m
b = [0]*m

for i in range(m):
    u,v,aa,bb = map(int,input().split())
    a[i] = aa
    b[i] = bb
    edge[u-1].append( (i,v-1))
    edge[v-1].append( (i,u-1) )


c = [0]*n
d = [0]*n

for i in range(n):
    cc,dd = map(int,input().split())
    c[i] = cc
    d[i] = dd

tank = [(0,s)]
nonused = [True]*(n*dg)


while tank:
    tim,fr = heapq.heappop(tank)
    if dist[fr] != INF:
        continue
    dist[fr] = tim
    pos,mon = divmod(fr,dg)

    for idx,go in edge[pos]:
        if mon >= a[idx] and dist[go*dg + mon-a[idx]] == INF:
            heapq.heappush(tank,(tim + b[idx] ,go*dg + mon-a[idx] ))
    if mon + c[pos] < dg and dist[fr + c[pos]] == INF:
        heapq.heappush(tank,(tim + d[pos] ,fr + c[pos] ))

for i in range(1,n):
    res = INF
    for j in range(dg):
        if dist[i*dg+j] < res:
            res = dist[i*dg+j]
    print(res)

Submission status: Accepted

Solution code:
from heapq import *
N, M, S = tuple(map(int, input().split()))
graph = [[] for _ in range(N)]
Max = 0
for i in range(M):
	U, V, A, B = tuple(map(int, input().split()))
	Max = max(Max, A)
	U -= 1
	V -= 1
	graph[U] += [(V, A, B)]
	graph[V] += [(U, A, B)]
Max *= (N - 1)
for i in range(N):
	C, D = tuple(map(int, input().split()))
	graph[i] += [(i, -C, D)]
costs = [[2**64 for _ in range(Max + 1)] for _ in range(N)]
que = [(0, 0, S)]
while que:
	(cost_sum, node, coins) = heappop(que)
	for to, pay, cost in graph[node]:
		if coins >= pay and cost_sum + cost < costs[to][min(Max, coins - pay)]:
			costs[to][min(Max, coins - pay)] = cost_sum + cost
			heappush(que, (cost_sum + cost, to, min(Max, coins - pay)))
for i in range(1, N):
	print(min(costs[i]))

Submission status: Accepted

Solution code:
ic=lambda i,c:i+c*50
n,m,s=map(int,input().split())
edge=[[]for _ in range(125100)]
for _ in range(m):
  u,v,a,b=map(int,input().split())
  u-=1
  v-=1
  for i in range(a,2501):
    edge[ic(u,i)].append((ic(v,i-a),b))
    edge[ic(v,i)].append((ic(u,i-a),b))
for i in range(n):
  c,d=map(int,input().split())
  for j in range(c,2501):
    edge[ic(i,j-c)].append((ic(i,j),d))
from heapq import heappop,heappush
def dijkstra(s,n,edge):
  inf=10**20
  ans=[inf]*n
  ans[s]=0
  h=[[0,s]]
  while h:
    c,v=heappop(h)
    if ans[v]<c:continue
    for u,t in edge[v]:
      if c+t<ans[u]:
        ans[u]=c+t
        heappush(h,[c+t,u])
  return ans
d=dijkstra(ic(0,min(2500,s)),125100,edge)
ans=[0]+[10**20]*(n-1)
for i in range(1,n):
  for j in range(2501):ans[i]=min(ans[i],d[ic(i,j)])
print(*ans[1:])

Submission status: Accepted

Solution code:
import heapq
inf = 10**20
h = 2500
n, m, s = map(int, input().split())
s = min(h-1, s)
# A[i][j]=iからjへのコスト
A = [[inf for j in range(n)] for i in range(n)]
# B[i][j]=iからjへの時間
B = [[inf for j in range(n)] for i in range(n)]
for _ in range(m):
    u, v, a, b = map(int, input().split())
    A[u-1][v-1] = a
    A[v-1][u-1] = a
    B[u-1][v-1] = b
    B[v-1][u-1] = b
CD = [tuple(map(int, input().split())) for i in range(n)]
C = [c for c, d in CD]
D = [d for c, d in CD]
# G[i,x][j,y]=状態(i,x)から(j,y)に変わるのにかかる時間
G = {(i, x): {} for i in range(n) for x in range(h)}
for i in range(n):
    for j in range(n):
        for x in range(h):
            if i == j:
                G[i, x][i, x] = 0
                if x-1 >= 0:
                    G[i, x][i, x-1] = 0
                if x+C[i] < h:
                    G[i, x][i, x+C[i]] = D[i]
            elif x >= A[i][j]:
                G[i, x][j, x-A[i][j]] = B[i][j]
# T[i,x]=状態(0,s)から(i,x)にかかる時間
T = {(i, x): inf for i in range(n) for x in range(h)}
T[0, s] = 0
Q = [(0, (0, s))]
heapq.heapify(Q)
while Q:
    _, (i, x) = heapq.heappop(Q)
    for j, y in G[i, x].keys():
        if T[i, x]+G[i, x][j, y] < T[j, y]:
            T[j, y] = T[i, x] + G[i, x][j, y]
            heapq.heappush(Q, (T[j, y], (j, y)))
for i in range(1, n):
    print(T[i, 0])

Submission status: Accepted

Solution code:
import sys
from heapq import heapify, heappop, heappush

def solve():
    input = sys.stdin.readline
    N, M, S = map(int, input().split())
    Edge = [[] for _ in range(N)] #time, nextnode, cost
    maxCost = 0
    for _ in range(M):
        u, v, a, b = map(int, input().split())
        Edge[u-1].append((b, v-1, a))
        Edge[v-1].append((b, u-1, a))
        maxCost = max(a, maxCost)
    exchange = [None] * N #c枚, Dmin
    for i in range(N): exchange[i] = [int(c) for c in input().split()]
    maxCost *= N

    minTime = [[10 ** 20 for _ in range(maxCost + 1)] for i in range(N)]
    q = []
    heapify(q)
    heappush(q, (0, 0, S)) #time, node, money
    while q:
        cT, cN, cM = heappop(q)
        if minTime[cN][min(maxCost, cM)] == 10 ** 20:
            minTime[cN][min(maxCost, cM)] = cT
            if cM < maxCost: heappush(q, (cT + exchange[cN][1], cN, cM + exchange[cN][0]))
            for addTime, nextNode, payCost in Edge[cN]:
                if cM >= payCost: heappush(q, (cT + addTime, nextNode, cM - payCost))
    
    for i in range(1, N): print(min(minTime[i]))

    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
from heapq import heapify, heappush, heappop
from heapq import _heapify_max, _heappop_max

def _heappush_max(heap, item):
    heap.append(item)
    heapq._siftdown_max(heap, 0, len(heap)-1)

"""
method:
    heapify(x): ヒープに変換
    heappush(heap, item): itemをheapにpush
    heappop(heap): heapから最小値を取得 空の場合はIndexError
note:
    max heapにする場合は、prefix: _ とsuffix: _maxをつければ良い
"""


def main():
    n, m, s = map(int, input().split())
    edge = [[] for i in range(n)]
    cl, dl = [None]*n, [None]*n
    sa = 0
    for i in range(m):
        u, v, a, b = map(int, input().split())
        u -= 1
        v -= 1
        edge[u].append((v, b, a))
        edge[v].append((u, b, a))
        sa += a
    for i in range(n):
        c, d = map(int, input().split())
        cl[i] = c
        dl[i] = d
    dijkstra(n, s, edge, cl, dl)
        
        
    
def dijkstra(n, coin, edges, cl, dl):
    coin_max = 5000
    start = 0
    coin = min(coin, coin_max)
    d = [[10**15]*(coin_max+1) for _ in range(n)]
    d[start][coin] = 0
    priority_queue = []
    heappush(priority_queue, (0, start, coin))
    while priority_queue:
        cost_i, i, coin_i = heappop(priority_queue)
        if d[i][coin_i] < cost_i:
            continue
        supplied_coin = coin_i + cl[i]
        if supplied_coin <= coin_max and cost_i + dl[i] < d[i][supplied_coin]:
            d[i][supplied_coin] = cost_i + dl[i]
            heappush(priority_queue, (cost_i + dl[i], i, supplied_coin))
        for _to, _cost, _coin in edges[i]:
            ci = coin_i-_coin
            if coin_i >= _coin and d[_to][ci] > cost_i + _cost:
                d[_to][ci] = cost_i + _cost
                heappush(priority_queue, (cost_i + _cost, _to, ci))
    for i in d[1:]:
        print(min(i))
    
        

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix


def idx(node, silver):
    silver = min(silver, SILVER_MAX)
    return node * (SILVER_MAX + 1) + silver


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)]

A_MAX = 50
SILVER_MAX = A_MAX * (n - 1)
N = (SILVER_MAX + 1) * n

U = []
V = []
C = []

# go through the road
for u, v, a, b in uvab:
    u -= 1
    v -= 1
    for silver in range(SILVER_MAX + 1):
        U.append(idx(u, silver + a))
        V.append(idx(v, silver))
        C.append(b)

        U.append(idx(v, silver + a))
        V.append(idx(u, silver))
        C.append(b)

# exchange gold to silver
for node, (c, d) in enumerate(cd):
    for silver in range(SILVER_MAX + 1):
        U.append(idx(node, silver))
        V.append(idx(node, silver + c))
        C.append(d)

# throw away silver
for node in range(n):
    for silver in range(SILVER_MAX):
        U.append(idx(node, silver + 1))
        V.append(idx(node, silver))
        C.append(0)

g = csr_matrix((C, (U, V)), shape=(N, N))
start = idx(0, s)
dist = dijkstra(g, indices=start).astype(int)
ans = dist[idx(1, 0)::SILVER_MAX+1]
print(*ans, sep="\n")

Submission status: Accepted

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

n, m, s = map(int,input().split())
A = [list(map(int,input().split())) for i in range(m)]
C = [list(map(int,input().split())) for i in range(n)]

for i in range(m):
    for j in range(2):
        A[i][j] -= 1

ma = max([A[i][2] for i in range(m)])
mc = ma * n + 3
vv = n * mc
M = [[] for i in range(vv)]

# print(ma,mc,vv)

for i in range(n):
    for j in range(mc-1):
        p0 = i * mc + j
        p1 = i * mc + min(mc-1, j+C[i][0])
        d = C[i][1]
        M[p0].append([p1, d])

# print(M)

for i in range(n):
    for j in range(1, mc):
        p0 = i * mc + j
        p1 = i * mc + j-1
        d = 0
        M[p0].append([p1, d])

# print(M)
# print("")


for i in range(m):
    for j in range(mc):
        p0 = A[i][0] * mc + j
        p1 = A[i][1] * mc + j-A[i][2]
        d = A[i][3]
        if j-A[i][2] >= 0:
            M[p0].append([p1, d])

        p0 = A[i][1] * mc + j
        p1 = A[i][0] * mc + j-A[i][2]
        d = A[i][3]
        if j-A[i][2] >= 0:
            M[p0].append([p1, d])

# print(M)

import heapq

st = min(s, mc-1)
nn = n
n = len(M)
D = [float("inf")] * n  # 頂点0からの距離
# P = [-1] * n  # 頂点0からの最短距離において、そこの直前の頂点(経路復元に利用)
D[st] = 0
V = [0] * n  # その頂点のD[i]が最短距離と確定したら1
Q = []  # 優先度付きキュー
for v in range(n):
    heapq.heappush(Q, [D[v], v])

le = len(Q)
while le > 0:
    q = heapq.heappop(Q)
    u = q[1]
    du = q[0]
    if V[u] == 0:
        V[u] = 1
        le -= 1
        for i in range(len(M[u])):
            v = M[u][i][0]
            luv = M[u][i][1]
            if V[v] == 0:
                alt = du + luv
                if D[v] > alt:
                    D[v] = alt
                    # P[v] = u
                    heapq.heappush(Q, [alt, v])

# print(D)

for i in range(1, nn):
    print(min(D[i*mc : (i+1)*mc]))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 # 998244353
input=lambda:sys.stdin.readline().rstrip()
from heapq import heappop, heappush
def resolve():
    n, m, s = map(int,input().split())
    S = 0
    E = [[] for _ in range(n)]
    for _ in range(m):
        u, v, a, b = map(int,input().split()) # a : cost silver
        u -= 1; v -= 1
        S += a
        E[u].append((v, -a, b))
        E[v].append((u, -a, b))
    for v in range(n):
        c, d = map(int,input().split())
        E[v].append((v, c, d))

    # Dijkstra with heap
    dist = [[INF] * (S + 1) for _ in range(n)]
    s = min(s, S)
    dist[0][s] = 0
    heap = [(0, 0, s)] # dist, vertex, silver
    while heap:
        d, v, s = heappop(heap)
        if dist[v][s] < d:
            continue
        for nv, ds, dd in E[v]:
            ns = s + ds
            if not (0 <= ns <= S):
                continue
            if dist[nv][ns] > dist[v][s] + dd:
                dist[nv][ns] = dist[v][s] + dd
                heappush(heap, (dist[nv][ns], nv, ns))

    # output
    for v in range(1, n):
        print(min(dist[v][s] for s in range(S + 1)))
resolve()

Submission status: Accepted

Solution code:
import sys
import heapq

input = sys.stdin.readline

NCOSTS = 2501
TIME_MAX = 10 ** 15

N, M, S = map(int, input().split())
adj = [[] for _ in range(N * NCOSTS)]
fare_adj = [[NCOSTS] * N for _ in range(N)]
time_adj = [[TIME_MAX] * N for _ in range(N)]
fare_max = 0


def node(city, silvers):
    return silvers * N + city


for i in range(M):
    u, v, a, b = map(int, input().split())
    u -= 1
    v -= 1
    for j in range(a, NCOSTS):
        adj[node(u, j)].append((node(v, j - a), b))
        adj[node(v, j)].append((node(u, j - a), b))

for i in range(N):
    # g-s rate, waiting duration
    c, d = map(int, input().split())
    for j in range(NCOSTS - c):
        adj[node(i, j)].append((node(i, j + c), d))


mintime = [TIME_MAX for _ in range(N * NCOSTS)]


def search():
    q = [(0, node(0, min(S, NCOSTS - 1)))]
    while q:
        t, node1 = heapq.heappop(q)
        if t > mintime[node1]:
            continue
        for node2, cost in adj[node1]:
            ntime = t + cost
            if mintime[node2] > ntime:
                mintime[node2] = ntime
                heapq.heappush(q, (ntime, node2))


search()
for i in range(1, N):
    print(min(mintime[node(i, j)] for j in range(NCOSTS)))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 # 998244353
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n, m, s = map(int,input().split())
    E = [None] * m
    S = 0
    for i in range(m):
        u, v, a, b = map(int,input().split())
        S += a
        E[i] = (u - 1, v - 1, -a, b)

    exchange = [tuple(map(int,input().split())) for _ in range(n)]
    dp = [[INF] * (S + 1) for _ in range(n)]
    dp[0][min(s, S)] = 0

    for _ in range(2 * n - 3):
        # 先に両替を済ませる
        for v in range(n):
            for s in range(S + 1):
                ds, dt = exchange[v]
                dp[v][min(s + ds, S)] = min(dp[v][min(s + ds, S)], dp[v][s] + dt)
        # 移動する
        for u, v, ds, dt in E:
            for s in range(S + 1):
                ns = s + ds
                if ns < 0:
                    continue
                dp[u][ns] = min(dp[u][ns], dp[v][s] + dt)
                dp[v][ns] = min(dp[v][ns], dp[u][s] + dt)

    for v in range(1, n):
        print(min(dp[v][j] for j in range(S + 1)))
resolve()

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

infi = 10 ** 20
n, m, s = map(int, input().split())

s = min(s, 2500)

edges = [[] for _ in range(51 * 2501 + 1)]
# edge:1-50, max silver=0-2500

for _ in range(m):
    u, v, a, b = map(int, input().split())
    for i in range(a, 2501):
        edges[v + 50 * i].append((b, u + 50 * (i - a)))
        edges[u + 50 * i].append((b, v + 50 * (i - a)))


for edge_num in range(1, n + 1):
    c, d = map(int, input().split())
    # c枚, d分
    for i in range(2501):
        # 点edge_num+ i * 50のところに
        if edge_num + (i + c) * 50 <= 51 * 2501:
            edges[edge_num + i * 50].append((d, edge_num + min((i + c), 2500) * 50))
start = 1 + 50 * s


def dijkstra(edges, start):
    time = [infi] * (51 * 2501 + 1)
    used = [False] * (51 * 2501 + 1)
    time[start] = 0
    edgelist = []
    heappush(edgelist, (0, start))
    while edgelist:
        nowtime, nowedge = heappop(edgelist)
        if used[nowedge] is True:
            continue
        used[nowedge] = True
        time[nowedge] = nowtime
        for vt, v in edges[nowedge]:
            if used[v] is True:
                continue
            newtime = nowtime + vt
            heappush(edgelist, (newtime, v))
    return time


time = dijkstra(edges, start)

ans = [infi] * (51)
for i in range(1, 51 * 2501 + 1):
    temp = time[i]
    a = i % 50
    if a == 0:
        a += 50
    ans[a] = min(temp, ans[a])

print(*ans[2 : (n + 1)], sep="\n")

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

infi = 10 ** 20
n, m, s = map(int, input().split())

s = min(s, 2500)

edges = [[] for _ in range(51 * 2501 + 1)]
# edge:1-50, max silver=0-2500

for _ in range(m):
    u, v, a, b = map(int, input().split())
    for i in range(a, 2501):
        edges[v + 50 * i].append((b, u + 50 * (i - a)))
        edges[u + 50 * i].append((b, v + 50 * (i - a)))


for edge_num in range(1, n + 1):
    c, d = map(int, input().split())
    # c枚, d分
    for i in range(2501):
        # 点edge_num+ i * 50のところに
        if edge_num + (i + c) * 50 <= 51 * 2501:
            edges[edge_num + i * 50].append((d, edge_num + min((i + c), 2500) * 50))
start = 1 + 50 * s


def dijkstra(edges, start):
    time = [infi] * (51 * 2501 + 1)
    used = [False] * (51 * 2501 + 1)
    # time[i][j] 頂点i, 銀貨jのときの時間
    time[start] = 0
    edgelist = []
    heappush(edgelist, (0, start))
    while edgelist:
        nowtime, nowedge = heappop(edgelist)
        if used[nowedge] is True:
            continue
        used[nowedge] = True
        time[nowedge] = nowtime
        for vt, v in edges[nowedge]:
            if used[v] is True:
                continue
            newtime = nowtime + vt
            heappush(edgelist, (newtime, v))
    return time


time = dijkstra(edges, start)

ans = [infi] * (51)
for i in range(1, 51 * 2501 + 1):
    temp = time[i]
    a = i % 50
    if a == 0:
        a += 50
    ans[a] = min(temp, ans[a])

print(*ans[2 : (n + 1)], sep="\n")