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:
# ABC 164 E 草案
import sys
sys.setrecursionlimit(10**6)

n,m,s= map(int, input().split())
g= [list(map(int, input().split())) for i in range(m)]
# 両替所
c= [list(map(int, input().split())) for i in range(n)]

x=2501
# 作るグラフ (辺*所有銀貨,必要時間)
gg=[[] for i in range(n*x)]
for i in range(n):
    for j in range(x-1):
        # 金貨を銀貨に交換
        y=j+c[i][0]
        if y>=x-1:
            y=x-1
        gg[i*x+j].append((i*x+y,c[i][1]))


for i in range(1,x):
    for u,v,a,b in g:
        u-=1
        v-=1
        # 銀貨足りる時移動できる
        if i-a>=0:
            gg[v*x+i].append((u*x+i-a,b))
            gg[u*x+i].append((v*x+i-a,b))




#ダイクストラ法
from heapq import heappush, heappop

def dijkstra(edges, size, source):
    # edge=探索するグラフ
    # size=グラフの点の数
    # source=スタート点
    distance = [float('inf')] * size
    distance[source] = 0
    visited = [False] * size
    pq = []
    heappush(pq, (0, source))
    while pq:
        dist_v, v = heappop(pq)
        visited[v] = True
        for u, weight in edges[v]:
            if not visited[u]:
                new_dist = dist_v + weight
                if distance[u] > new_dist:
                    distance[u] = new_dist
                    heappush(pq, (new_dist, u))
    return distance
s=min(s,2500)
ans=dijkstra(gg,n*x,s)

for i in range(1, n):
    print(min(ans[x * i:x * (i + 1)]))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import heapq
INF = 10**20

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)]
#%%
def ic(i,c):
    # i番目の都市で，所持金cの頂点
    return i+c*50


MAX_S = 0
for _,_,a,_ in UVAB:
    MAX_S = max(MAX_S, a)
MAX_S *= N
S = min(S, MAX_S)
MAX_N = ic(N-1, MAX_S) + 1
edge = [[] for _ in range(MAX_N)]

for u,v,a,b in UVAB:
    # 所持金c -> c-aに辺を張る    
    for c in range(a,MAX_S+1):
        edge[ic(u-1,c)].append([ic(v-1,c-a),b])
        edge[ic(v-1,c)].append([ic(u-1,c-a),b])

for i in range(N):
    # 各頂点に所持金 c -> c+Ciの辺を張る
    ci = CD[i][0]
    di = CD[i][1]
    for c in range(MAX_S):
        edge[ic(i,c)].append([ic(i,min(c+ci,MAX_S)),di])



def dijkstra(S, N, Edge):
    # S: start vertex
    # N: number of vertices
    # Edge: adjacent list [node, cost]
    
    INF = 10**20
    dist = [INF]*N
    dist[S] = 0
    que = [[0, S]]
    heapq.heapify(que)
    
    while que:
        c, v = heapq.heappop(que)
        if dist[v] < c: continue

        for nv, nc in Edge[v]:
            if c+nc < dist[nv]:
                dist[nv] = c+nc
                heapq.heappush(que, [c+nc, nv])
    
    return dist

dist = dijkstra(ic(0, S), MAX_N, edge)
for i in range(1,N):
    ans = INF
    for c in range(MAX_S):
        ans = min(ans, dist[ic(i,c)])
    print(ans)

Submission status: Accepted

Solution code:
import heapq

N, M, S = map(int, input().strip().split())

graph = [[] for _ in range(N)]
for _ in range(M):
	u, v, A, B = map(int, input().strip().split())
	u -= 1
	v -= 1
	graph[u].append((v, A, B))
	graph[v].append((u, A, B))

exchanges = []
for _ in range(N):
	C, D = map(int, input().strip().split())
	exchanges.append((C, D))

queue = [(0, 0, S)]
max_fare = 2500

state_table = [[None] * (max_fare + 1) for i in range(N)]

reached = [False] * N
reached_count = 0

while queue:
#	print(len(queue))
	time, cur, money = heapq.heappop(queue)
	if not reached[cur]:
		reached[cur] = True
		reached_count += 1
		if reached_count >= N:
			break
	count, d_time = exchanges[cur]
	for n, A, B in graph[cur]:
		n_money = money - A
		n_time = time + B
		if n_money >= 0:
			states = state_table[n]
			if n_money > max_fare:
				n_money = max_fare
			if states[n_money] == None or states[n_money] > n_time:
				states[n_money] = n_time
				heapq.heappush(queue, (n_time, n, n_money))

	states = state_table[cur]
	money += count
	time += d_time
	if money >= 0:
		if money > max_fare:
			money = max_fare
		if states[money] == None or states[money] > time:
			states[money] = time
			heapq.heappush(queue, (time, cur, money))

#for i in range(N):
#	print(i, state_table[i])

for i in range(1, N):
	states = state_table[i]
	minimum = None
	for t in states:
		if t != None and (minimum == None or minimum > t):
			minimum = t
	print(minimum)

Submission status: Accepted

Solution code:
from heapq import *
n,m,s=map(int,input().split())
c=[0]*n
d=[0]*n
g=[[]for i in range(n)]

for i in range(m):
    u,v,a,b=map(int,input().split())
    u-=1
    v-=1
    g[u].append((v,a,b))
    g[v].append((u,a,b))
for i in range(n):
    c[i],d[i]=map(int,input().split())

flag=0 #if this == (1<<n)-1 then finish roop
lasttime=[[10**15]*2501 for i in range(n)]
lasttime[0][min(2500,s)]=0
mintimes=[10**15]*n
hp=[(0,min(2500,s),0)]#(time,silver,node)

while flag!=((1<<n)-1):
    time,silver,node = heappop(hp)
    flag=flag|(1<<node)
    mintimes[node]=min(mintimes[node],time)

    for atnode,costmoney,costtime in g[node]:
        nexttime,nextsilver=time+costtime,silver-costmoney
        if costmoney<=silver and lasttime[atnode][nextsilver]>nexttime:
            heappush(hp,(nexttime,nextsilver,atnode))
            lasttime[atnode][nextsilver]=min(lasttime[atnode][nextsilver],nexttime)

    nexttime,nextsilver=time+d[node],min(silver+c[node],2500)
    if silver!=2500 and lasttime[node][nextsilver]>nexttime:
        heappush(hp,(nexttime,min(silver+c[node],2500),node))
        lasttime[node][nextsilver]=min(lasttime[node][nextsilver],nexttime)
        
print(*mintimes[1:],sep="\n")

Submission status: Accepted

Solution code:
from heapq import heappop, heappush
import sys

sys.setrecursionlimit(10 ** 7)

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

N, M, S = map(int, input().split())
S = min(2500, S)

# INPUT
PATH = [[] for _ in range(N + 1)]
CHANGES = [None] * (N + 1)

for _ in range(M):
    U, V, A, B = map(int, input().split())
    PATH[U].append((V, A, B))
    PATH[V].append((U, A, B))

for i in range(N):
    C, D = map(int, input().split())
    CHANGES[i + 1] = (C, D)

Q = []
INF = float("inf")
TIME = [[INF] * 2501 for _ in range(N + 1)]
USED = [[False] * 2501 for _ in range(N + 1)]

Q.append((0, 1, S))
TIME[1][S] = 0

while Q:
    t, u, g = heappop(Q)

    # そこで銀貨を増やす
    # 2500枚未満の場合
    if g < 2500:
        c, d = CHANGES[u]
        ng = min(g + c, 2500)
        nt = t + d

        if nt < TIME[u][ng]:
            TIME[u][ng] = nt
            heappush(Q, (nt, u, ng))

    # 次の頂点に進む
    for v, a, b in PATH[u]:
        if g < a:
            continue

        ng = g - a
        nt = t + b
        if nt < TIME[v][ng]:
            TIME[v][ng] = nt
            heappush(Q, (nt, v, ng))

ANS = [min(x) for x in TIME[2:]]
print("\n".join(map(str, ANS)))

Submission status: Accepted

Solution code:
import heapq
import sys
def dijkstra(e,dist,s,used):
  q=[]
  heapq.heappush(q,(0,0,s))
  while q:
    d,x,m=heapq.heappop(q)
    if not used[x][m]:
      continue
    dist[x][m]=d
    used[x][m]=False
    for cost,newx,silver in e[x][m]:
      if used[newx][silver]:
        heapq.heappush(q,(dist[x][m]+cost,newx,silver))
  return dist
def main():
  input=sys.stdin.readline
  n,m,s=map(int,input().split())
  if s>2500:
    s=2500
  edge=[[[] for i in range(2501)] for _ in range(n)]
  for _ in range(m):
    u,v,a,b=map(int,input().split())
    u-=1
    v-=1
    for j in range(a,2501):
        edge[u][j].append((b,v,j-a))
        edge[v][j].append((b,u,j-a))
  for i in range(n):
    c,d=map(int,input().split())
    for j in range(2501-c):
        edge[i][j].append((d,i,j+c))
  dist=[[10**18]*2501 for _ in range(n)]
  used=[[True]*2501 for _ in range(n)]
  dist=dijkstra(edge,dist,s,used)
  #print(edge)
  #print(dist)
  for i in range(1,n):
    print(min(dist[i]))
if __name__=="__main__":
  main()

Submission status: Accepted

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

def dijkstra_heap(s):
  d=[float("inf")]*n
  used=[True]*n 
  d[s]=0
  used[s]=False
  edgelist=[]
  for e in edge[s]:
    heapq.heappush(edgelist,e)
  while len(edgelist):
    minedge=heapq.heappop(edgelist)
    if not used[minedge[1]]:
      continue
    v=minedge[1]
    d[v]=minedge[0]
    used[v]=False
    for e in edge[v]:
      if used[e[1]]:
        heapq.heappush(edgelist,[e[0]+d[v],e[1]])
  return d

N,m,s=map(int,input().split())
L=[list(map(int,input().split())) for i in range(m)]
L2=[list(map(int,input().split())) for i in range(N)]
n=N*(50*(N-1)+1)
edge=[[] for i in range(n)]
for i in range(m):
  for j in range(50*(N-1)+1):
    if j>=L[i][2]:
      edge[L[i][0]-1+N*j].append([L[i][3],L[i][1]-1+N*(j-L[i][2])])
      edge[L[i][1]-1+N*j].append([L[i][3],L[i][0]-1+N*(j-L[i][2])])
for i in range(N):
  for j in range(50*(N-1)):
    edge[i+N*j].append([L2[i][1],i+N*min(50*(N-1),j+L2[i][0])])
ans=[[] for i in range(N)]
D=dijkstra_heap(min(50*(N-1),s)*N)
for i in range(len(D)):
  ans[i%N].append(D[i])
for i in range(1,N):
  print(min(ans[i]))

Submission status: Accepted

Solution code:
import heapq
def dijkstra_heap(s):
  d=[float("inf")]*n
  used=[True]*n 
  d[s]=0
  used[s]=False
  edgelist=[]
  for e in edge[s]:
    heapq.heappush(edgelist,e)
  while len(edgelist):
    minedge=heapq.heappop(edgelist)
    if not used[minedge[1]]:
      continue
    v=minedge[1]
    d[v]=minedge[0]
    used[v]=False
    for e in edge[v]:
      if used[e[1]]:
        heapq.heappush(edgelist,[e[0]+d[v],e[1]])
  return d

N,m,s=map(int,input().split())
L=[list(map(int,input().split())) for i in range(m)]
L2=[list(map(int,input().split())) for i in range(N)]
n=N*(50*(N-1)+1)
edge=[[] for i in range(n)]
for i in range(m):
  for j in range(50*(N-1)+1):
    if j>=L[i][2]:
      edge[L[i][0]-1+N*j].append([L[i][3],L[i][1]-1+N*(j-L[i][2])])
      edge[L[i][1]-1+N*j].append([L[i][3],L[i][0]-1+N*(j-L[i][2])])
for i in range(N):
  for j in range(50*(N-1)):
    edge[i+N*j].append([L2[i][1],i+N*min(50*(N-1),j+L2[i][0])])
ans=[[] for i in range(N)]
D=dijkstra_heap(min(50*(N-1),s)*N)
for i in range(len(D)):
  ans[i%N].append(D[i])
for i in range(1,N):
  print(min(ans[i]))

Submission status: Accepted

Solution code:
from scipy.sparse import*
(n,m,s,*D),*t=[map(int,t.split())for t in open(0)]
x=51
r=range(0,x**3,x)
for u,v,a,b in t[:m]:
 for i in r:D+=i+a*x+u,i+v,b,i+a*x+v,i+u,b
i=0
for c,d in t[m:]:
 i+=1
 for j in r:D+=j+i,j+c*x+i,d
d=csgraph.dijkstra(csr_matrix((D[2::3],(D[::3],D[1::3])),[j*2]*2),1,min(j,s*x)+1)
for i in range(2,n+1):print(int(min(d[i::x])))

Submission status: Accepted

Solution code:
from scipy.sparse import*
(n,m,s,*D),*t=[map(int,t.split())for t in open(0)]
x=51
r=range(0,x**3,x)
for u,v,a,b in t[:m]:
 for i in r:D+=i+a*x+u,i+v,b,i+a*x+v,i+u,b
i=0
for c,d in t[m:]:
 i+=1
 for j in r:D+=j+i,j+c*x+i,d
d=csgraph.dijkstra(csr_matrix((D[2::3],(D[::3],D[1::3])),[j*2]*2),1,min(x*x,s)*x+1)
for i in range(2,n+1):print(int(min(d[i::x])))

Submission status: Accepted

Solution code:
from scipy.sparse import*
(n,m,s,*D),*t=[map(int,t.split())for t in open(0)]
x=51
r=range(0,x**3,x)
for u,v,a,b in t[:m]:
 for i in r:D+=i+a*x+u,i+v,b,i+a*x+v,i+u,b
i=0
for c,d in t[m:]:
 i+=1
 for j in r:D+=j+i,j+c*x+i,d
d=csgraph.dijkstra(csr_matrix((D[2::3],(D[::3],D[1::3])),[8**6]*2),1,min(x*x,s)*x+1)
for i in range(2,n+1):print(int(min(d[i::x])))

Submission status: Accepted

Solution code:
from scipy.sparse import*
(n,m,s,*D),*t=[map(int,t.split())for t in open(0)]
x=51
r=range(x*x)
for u,v,a,b in t[:m]:
 for i in r:k=(i+a)*x;D+=k+u,i*x+v,b,k+v,i*x+u,b
i=0
for c,d in t[m:]:
 i+=1
 for j in r:D+=j*x+i,(j+c)*x+i,d
d=csgraph.dijkstra(csr_matrix((D[2::3],(D[::3],D[1::3])),[8**6]*2),1,min(j,s)*x+1)
for i in range(2,n+1):print(int(min(d[i::x])))

Submission status: Accepted

Solution code:
from scipy.sparse import*
(n,m,s,*D),*t=[map(int,t.split())for t in open(0)]
R,C=[],[]
x=51
r=range(x*x)
for u,v,a,b in t[:m]:
 for i in r:k=(i+a)*x;R+=k+u,k+v;C+=i*x+v,i*x+u;D+=b,b
i=0
for c,d in t[m:]:
 i+=1
 for j in r:R+=j*x+i,;C+=(j+c)*x+i,;D+=d,
d=csgraph.dijkstra(csr_matrix((D,(R,C)),[8**6]*2),1,min(j,s)*x+1)
for i in range(2,n+1):print(int(min(d[i::x])))

Submission status: Accepted

Solution code:
from scipy.sparse import*
(n,m,s,*D),*t=[map(int,t.split())for t in open(0)]
R,C=[],[]
r=range(2501)
for u,v,a,b in t[:m]:
 for i in r:k=(i+a)*51;R+=k+u,k+v;C+=i*51+v,i*51+u;D+=b,b
i=0
for c,d in t[m:]:
 i+=1
 for j in r:R+=j*51+i,;C+=(j+c)*51+i,;D+=d,
d=csgraph.dijkstra(csr_matrix((D,(R,C)),[8**6]*2),1,min(j,s)*51+1)
for i in range(2,n+1):print(int(min(d[i::51])))

Submission status: Accepted

Solution code:
from scipy.sparse import*
(n,m,s,*D),*t=[map(int,t.split())for t in open(0)]
R,C=[],[]
r=range(2501)
for u,v,a,b in t[:m]:
 for i in r:k=(i+a)*51;R+=k+u,k+v;C+=i*51+v,i*51+u;D+=b,b
i=0
for c,d in t[m:]:
 i+=1
 for j in r:R+=j*51+i,;C+=(j+c)*51+i,;D+=d,
d=csgraph.dijkstra(csr_matrix((D,(R,C)),[8**6]*2),1,min(2500,s)*51+1)
for i in range(2,n+1):print(int(min(d[i::51])))

Submission status: Accepted

Solution code:
from scipy.sparse import*
(n,m,s,*D),*t=[map(int,t.split())for t in open(0)]
R,C=[],[]
r=range(2501)
for u,v,a,b in t[:m]:
 for i in r:k=(i+a)*51;R+=k+u,k+v;C+=i*51+v,i*51+u;D+=b,b
for i,(c,d)in enumerate(t[m:],1):
 for j in r:R+=j*51+i,;C+=(j+c)*51+i,;D+=d,
d=csgraph.dijkstra(csr_matrix((D,(R,C)),[8**6]*2),1,min(2500,s)*51+1)
for i in range(2,n+1):print(int(min(d[i::51])))

Submission status: Accepted

Solution code:
from scipy.sparse import*
(n,m,s,*D),*t=[map(int,t.split())for t in open(0)]
R,C=[],[]
r=range(2501)
for u,v,a,b in t[:m]:
    for i in r:
        R+=(i+a)*51+u,(i+a)*51+v
        C+=i*51+v,i*51+u
        D+=b,b
for i,(c,d)in enumerate(t[m:],1):
    for j in r:
        R+=j*51+i,
        C+=(j+c)*51+i,
        D+=d,
d=csgraph.dijkstra(csr_matrix((D,(R,C)),[8**6]*2),1,min(2500,s)*51+1)
for i in range(2,n+1):print(int(min(d[i::51])))

Submission status: Accepted

Solution code:
from scipy.sparse import*
(n,m,s,*D),*t=[map(int,t.split())for t in open(0)]
R,C=[],[]
for u,v,a,b in t[:m]:
    for i in range(2501):
        R+=(i+a)*51+u,(i+a)*51+v
        C+=i*51+v,i*51+u
        D+=b,b
for i,(c,d)in enumerate(t[m:],1):
    for j in range(2501):
        R+=j*51+i,
        C+=(j+c)*51+i,
        D+=d,
d=csgraph.dijkstra(csr_matrix((D,(R,C)),[8**6]*2),1,min(2500,s)*51+1)
for i in range(2,n+1):print(int(min(d[i::51])))

Submission status: Accepted

Solution code:
from scipy.sparse import*
(n,m,s,*D),*t=[map(int,t.split())for t in open(0)]
R,C=[],[]
for u,v,a,b in t[:m]:
    for i in range(2501-a):
        R+=(i+a)*51+u,(i+a)*51+v
        C+=i*51+v,i*51+u
        D+=b,b
for i,(c,d)in enumerate(t[m:],1):
    for j in range(2501-c):
        R+=j*51+i,
        C+=(j+c)*51+i,
        D+=d,
d=csgraph.dijkstra(csr_matrix((D,(R,C)),[8**6]*2),1,min(2500,s)*51+1)
for i in range(2,n+1):print(int(min(d[i::51])))

Submission status: Accepted

Solution code:
def main():
    from heapq import heappush,heappop
    (n,m,s),*t=[map(int,r.split())for r in open(0)]
    e=[[]for _ in range(8**6)]
    for u,v,a,b in t[:m]:
        for i in range(2501-a):
            e[(i+a)*51+u]+=(b,i*51+v),
            e[(i+a)*51+v]+=(b,i*51+u),
    for i,(c,d)in enumerate(t[m:],1):
        for j in range(2501-c):
            e[j*51+i]+=(d,(j+c)*51+i),
    x=[10**18]*8**6
    f=[1]*8**6
    q=[(0,min(2500,s)*51+1)]
    while q:
        c,v=heappop(q)
        if f[v]<1:continue
        x[v],f[v]=c,0
        for p,w in e[v]:
            if f[w]:heappush(q,(c+p,w))
    for i in range(2,n+1):print(min(x[i::51]))
main()

Submission status: Accepted

Solution code:
from heapq import*
(n,m,s),*t=[map(int,t.split())for t in open(0)]
*e,=eval('[],'*8**6)
for u,v,a,b in t[:m]:
    for i in range(2501-a):
        e[(i+a)*51+u]+=(b,i*51+v),
        e[(i+a)*51+v]+=(b,i*51+u),
for i,(c,d)in enumerate(t[m:],1):
    for j in range(2501-c):
        e[j*51+i]+=(d,(j+c)*51+i),
d=[10**18]*8**6
f=[1]*8**6
q=[(0,min(2500,s)*51+1)]
while q:
    c,v=heappop(q)
    if f[v]<1:continue
    d[v],f[v]=c,0
    for p,w in e[v]:
        if f[w]:heappush(q,(c+p,w))
for i in range(2,n+1):print(min(d[i::51]))

Submission status: Accepted

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

def solve(N: int, M: int, S: int, U: "List[int]", V: "List[int]", A: "List[int]", B: "List[int]", C: "List[int]", D: "List[int]"):
    from collections import namedtuple
    from heapq import heappush, heappop
    MAX_COIN = sum(A)
    State = namedtuple('State', 'cost city coin')
    Edge = namedtuple('Edge', 'to fee cost')
    edges = [[] for _ in range(N+1)]
    for u, v, a, b in zip(U, V, A, B):
        edges[u].append(Edge(v, a, b))
        edges[v].append(Edge(u, a, b))
    for i, (c, d) in enumerate(zip(C, D), 1):
        edges[i].append(Edge(i, -c, d))
    hq = [State(0, 1, min(S, MAX_COIN))]
    min_costs = [[None] * (MAX_COIN+1) for _ in range(N+1)]
    while hq:
        s = heappop(hq)
        if min_costs[s.city][s.coin]:
            continue
        min_costs[s.city][s.coin] = s.cost
        for edge in edges[s.city]:
            if edge.fee > s.coin:
                continue
            ns = State(s.cost+edge.cost, edge.to, s.coin-edge.fee)
            if ns.coin > MAX_COIN or min_costs[ns.city][ns.coin]:
                continue
            heappush(hq, ns)
    return [min(filter(lambda x:x, c)) for c in min_costs[2:]]
        

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    S = int(next(tokens))  # type: int
    U = [int()] * (M)  # type: "List[int]"
    V = [int()] * (M)  # type: "List[int]"
    A = [int()] * (M)  # type: "List[int]"
    B = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        U[i] = int(next(tokens))
        V[i] = int(next(tokens))
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    C = [int()] * (N)  # type: "List[int]"
    D = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        C[i] = int(next(tokens))
        D[i] = int(next(tokens))
    print(*solve(N, M, S, U, V, A, B, C, D), sep='\n')

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from scipy.sparse import*
n,m,s,*t=map(int,open(0).read().split())
row,col,dat=[],[],[]
for u,v,a,b in zip(*[iter(t[:m*4])]*4):
    for i in range(2501-a):
        row+=(i+a)*51+u,(i+a)*51+v
        col+=i*51+v,i*51+u
        dat+=b,b
for i,(c,d)in enumerate(zip(*[iter(t[m*4:])]*2),1):
    for j in range(2501-c):
        row+=j*51+i,
        col+=(j+c)*51+i,
        dat+=d,
d=csgraph.dijkstra(csr_matrix((dat,(row,col)),[8**6]*2),1,min(2500,s)*51+1)
for i in range(2,n+1):print(int(d[i::51].min()))

Submission status: Accepted

Solution code:
import sys,bisect,string,math,time,functools,random
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
def Golf():*a,=map(int,open(0))
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            a,b,c=(inp+[1])[:3]
            org_inp.append(inp)
        else:
            #index=0
            a,b,c=(list(ls[i])+[1])[:3]
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0}):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0}) # sample usage
    mp=[1]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[1]+[mp_def[j] for j in s]+[1]
    mp+=[1]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)];rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
input=lambda: sys.stdin.readline().rstrip()

class Comb:
    def __init__(self,n,mo=10**9+7):
        self.fac=[0]*(n+1)
        self.inv=[1]*(n+1)
        self.fac[0]=1
        self.fact(n)
        for i in range(1,n+1):
            self.fac[i]=i*self.fac[i-1]%mo
            self.inv[n]*=i
            self.inv[n]%=mo
        self.inv[n]=pow(self.inv[n],mo-2,mo)
        for i in range(1,n):
            self.inv[n-i]=self.inv[n-i+1]*(n-i+1)%mo
        return
    
    def fact(self,n):
        return self.fac[n]
        
    def invf(self,n):
        return self.inv[n]

    def comb(self,x,y):
        if y<0 or y>x:
            return 0
        return self.fac[x]*self.inv[x-y]*self.inv[y]%mo

show_flg=False
show_flg=True

class Tree:
    def __init__(self,inp_size=None,init=True):
        if init:
            self.stdin(inp_size)
        return

    def stdin(self,inp_size=None):
        if inp_size==None:
            self.size=int(input())
        else:
            self.size=inp_size
        self.edges,_=GI(self.size,self.size-1)
        return
    
    def listin(self,ls):
        self.size=len(ls)+1
        self.edges,_=GI(self.size,self.size-1,ls)
        return

    def __str__(self):
        return  str(self.edges)

    def dfs(self,x,func=lambda prv,nx,dist:prv+dist,root_v=0):
        q=deque()
        q.append(x)
        v=[-1]*self.size
        v[x]=root_v
        while q:
            c=q.pop()
            for nb,d in self.edges[c]:
                if v[nb]==-1:
                    q.append(nb)
                    v[nb]=func(v[c],nb,d)
        return v

    def EulerTour(self,x,func=lambda prv,nx,dist:prv+dist,root_v=0):
        q=deque()
        q.append((-1,x))
        v=[None]*self.size
        v[x]=root_v
        et=[]
        while q:
            cb,ce=q.pop()
            et.append(ce)
            for nb,d in self.edges[ce]:
                if v[nb]==None:
                    q.append((nb,ce))
                    q.append((ce,nb))
                    v[nb]=func(v[ce],nb,d)
        vid=[[-1,-1]for i in range(self.size)]
        for i,j in enumerate(et):
            if vid[j][0]==-1:
                vid[j][0]=i
            else:
                vid[j][1]=i
        return v,et,vid
    
    def LCA_init(self,depth,et):
        self.st=SegTree(self.size*2-1,func=min,ide=inf)
        for i,j in enumerate(et):
            self.st.update(i,j)
        self.LCA_init_stat==True
        return
    
    def LCA(self,root,x,y):
        if self.LCA_init_stat==False:
            depth,et,vid=self.EulerTour(root)
            self.LCA_init(depth,et)
        return self.st.query(x,y+1)


def dijkstra(edge,st):
    # edge=[[(v_to,dist_to_v),...],[],...]
    # initialize: def: d=dist(st,i), prev=[previous vertex in minimum path], q[]
    n=len(edge)
    d=[(0 if st==i else inf) for i in range(n)]
    prev=[0]*n
    q=[(j,i) for i,j in enumerate(d)]
    heapify(q)
    v=[False]*n
    # calc
    while q:
        dist,cur=heappop(q)
        if v[cur]:
            continue
        v[cur]=True
        for dst,dist in edge[cur]:
            alt=d[cur]+dist
            if alt<d[dst]:
                d[dst]=alt
                prev[dst]=cur
                heappush(q,(alt,dst))
    return d,prev

n,m,s=LI()
t_ls=[]
k=1+n*50
s=min(k-1,s)
for i in range(m):
    u,v,a,b=LI()
    u-=1
    v-=1
    for j in range(a,k):
        t_ls+=[(u*k+j,v*k+j-a,b)]
        t_ls+=[(v*k+j,u*k+j-a,b)]

for i in range(n):
    c,d=LI()
    for j in range(k):
        t_ls+=[(i*k+j,i*k+min(j+c,k-1),d)]

gt,_=GI(n*k,len(t_ls),ls=t_ls,Directed=True,index=0)
dist_t,_=dijkstra(gt,0*k+s)

for i in range(1,n):
    print(min(dist_t[i*k:-~i*k]))