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 heappop, heappush

n, m, ss = map(int, input().split())
lines = sys.stdin.readlines()
links = [set() for _ in range(n)]
aaa = []
for line in lines[:m]:
    u, v, a, b = map(int, line.split())
    u -= 1
    v -= 1
    links[u].add((v, a, b))
    links[v].add((u, a, b))
    aaa.append(a)

exchanges = []
for line in lines[m:]:
    c, d = map(int, line.split())
    exchanges.append((c, d))

req = sum(sorted(aaa, reverse=True)[:n - 1])
INF = 10 ** 18
ans = [INF] * n
ans_silver = [-1] * n

q = [(0, ss, 0)]  # (time, silver, city)
visited = set()
fixed = 0
while q:
    t, s, v = heappop(q)
    if (s, v) in visited or ans_silver[v] >= s:
        continue
    visited.add((s, v))
    if ans[v] == INF:
        ans[v] = t
        ans_silver[v] = s
        fixed += 1
        if fixed == n:
            break

    for u, a, b in links[v]:
        if s < a:
            continue
        ns = s - a
        nt = t + b
        if (ns, u) in visited or ans_silver[u] >= ns:
            continue
        heappush(q, (nt, ns, u))

    c, d = exchanges[v]
    ns = s + c
    if ns <= req and (ns, v) not in visited:
        heappush(q, (t + d, ns, v))

print('\n'.join(map(str, ans[1:])))

Submission status: Accepted

Solution code:
n, m, s = map(int,input().split())
adj = [[] for i in range(n)]
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 i in range(n):
    c, d = map(int,input().split())
    adj[i].append((i,c,d))

out = [-1] * n
count = 0

LARGE = 50 * n

done = dict()
from heapq import *
q = []
if s > LARGE:
    s = LARGE
heappush(q, (0, 0, s))

while q:
    time, loc, curr = heappop(q)
    if out[loc] == -1:
        out[loc] = time
        count += 1
        if count == n:
            break
    for nex, cost, timeD in adj[loc]:
        currNex = curr + cost
        timeNex = time + timeD
        if currNex > LARGE:
            currNex = LARGE
        if currNex < 0:
            continue
        if (nex, currNex) not in done or timeNex < done[(nex, currNex)]:
            done[(nex, currNex)] = timeNex
            heappush(q, (timeNex, nex, currNex))
print(*out[1:], sep = '\n')

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from heapq import heappush, heappop

N, M, S = map(int, input().split())
STATE = 50 * N + 1
vec = [[] for _ in range(STATE * N)]
for _ in range(M) :
  U, V, A, B = map(int, input().split())
  U -= 1
  V -= 1
  for silver in range(A, STATE) :
    vec[STATE * U + silver].append((STATE * V + silver - A, B))
    vec[STATE * V + silver].append((STATE * U + silver - A, B))
  
for i in range(N) :
  C, D = map(int, input().split())
  for silver in range(STATE - C) :
    vec[STATE * i + silver].append((STATE * i + silver + C, D))

dist = [float('inf')] * (STATE * N)

S = min(S, STATE - 1)
dist[S] = 0
q = [(0, S)]
while q :
  cc, cur = heappop(q)
  for nex, nc in vec[cur] :
    if dist[nex] <= cc + nc :
      continue
    dist[nex] = cc + nc
    heappush(q, (cc + nc, nex))

for i in range(1, N) :
  print(min(dist[STATE * i:STATE * (i + 1)]))

Submission status: Accepted

Solution code:
import sys
range = xrange
input = raw_input

M = 2501
inf = 3 * 10**18

inp = [int(x) for x in sys.stdin.read().split()]; ii = 0
n = inp[ii]; ii += 1
m = inp[ii]; ii += 1
s = inp[ii]; ii += 1

s = min(M - 1, s)

coupl = [[] for _ in range(n)]
V = []
A = []
B = []
for _ in range(m):
    u = inp[ii] - 1; ii += 1
    v = inp[ii] - 1; ii += 1
    coupl[u].append(2 * _)
    coupl[v].append(2 * _ + 1)
    V.append(v)
    V.append(u)

    A.append(inp[ii]); ii += 1
    B.append(inp[ii]); ii += 1

C = inp[ii + 0: ii + 2 * n: 2]
D = inp[ii + 1: ii + 2 * n: 2]
ii += n

import heapq
DP = [inf] * (n * M)
found = [0] * (n * M)
DP[s] = 0

#heapq.cmp_lt = 
queue = [(0,s)]
while queue:
    _,ind = heapq.heappop(queue)
    if found[ind]:
        continue
    found[ind] = 1
    node,money = divmod(ind, M)
    for eind in coupl[node]:
        v = V[eind]
        ind2 = ind - A[eind >> 1] + M*(v - node)
        if money >= A[eind >> 1] and not found[ind2]:
            val = DP[ind] + B[eind >> 1]
            if DP[ind2] > val:
                DP[ind2] = val
                heapq.heappush(queue, (val, ind2))

    ind2 = ind - money + min(M - 1, C[node] + money)
    val = DP[ind] + D[node]
    if DP[ind2] > val:
        DP[ind2] = val
        heapq.heappush(queue, (val, ind2))

ans = []
for node in range(1, n):
    ans.append(min(DP[node * M + m] for m in range(M)))
print '\n'.join(str(x) for x in ans)

Submission status: Accepted

Solution code:

"""

銀貨の枚数,時間で最小値を計算推移？
Sがでかいなら普通に最小距離　おｋ

Sが小さい時
島をcostmax+1個に分ける
→dijkstraで解ける

"""
from collections import deque
N,M,S = map(int,input().split())

lis = [ [] for i in range(N) ]
costsum = 0

for i in range(M):

    U,V,A,B = map(int,input().split())
    U -= 1
    V -= 1

    lis[U].append([V,A,B])
    lis[V].append([U,A,B])

    costsum += A

CD = []
for i in range(N):
    c,d = map(int,input().split())
    CD.append([c,d])

if S >= costsum:

    q = deque([0])
    dis = [float("inf")] * N
    dis[0] = 0

    while len(q) > 0:
        now = q.popleft()
        for i in range(len(lis[now])):
            nex,a,b = lis[now][i]

            if dis[nex] > dis[now] + b:
                dis[nex] = dis[now] + b
                q.append(nex)

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

else:

    import heapq

    dis = [ [float("inf")] * (costsum+1) for i in range(N) ]
    able = [ [True]  * (costsum+1) for i in range(N) ]
    end = 0
    q = [[0,0,S]]
    dis[0][S] = 0

    while len(q) > 0:
        
        if end == (costsum+1)*N:
            break

        ncost,nv,ns = heapq.heappop(q)
        if not able[nv][ns]:
            continue
        able[nv][ns] = False
        end += 1

        for i in range(len(lis[nv])):

            nex,a,b = lis[nv][i]

            if ns >= a and dis[nex][ns-a] > dis[nv][ns] + b:
                dis[nex][ns-a] = dis[nv][ns] + b
                heapq.heappush(q,[dis[nex][ns-a] , nex , ns-a])

        pl = 1
        C,D = CD[nv]
        if ns+C<=costsum and dis[nv][ns+pl*C] > dis[nv][ns] + D:
            dis[nv][ns+pl*C] = dis[nv][ns] + D
            heapq.heappush(q, [dis[nv][ns+pl*C],nv,ns+pl*C])

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

Submission status: Accepted

Solution code:
def main():
    from collections import deque

    import sys
    input = sys.stdin.readline

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

    S = min(S, 50 * 50) #これ以上の枚数はいらない

    G = [[] for _ in range(N + 1)]

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

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

    MAX = 10 ** 18
    DP = [[MAX] * (50 * 50 + 1) for _ in range(N + 1)]

    # print (G)
    # print (CD)

    #初期位置のコストを0にする
    for s in range(S + 1):
        DP[1][s] = 0
    for s in range(S + 1, 50 * 50 + 1):
        DP[1][s] = DP[1][max(0, s - CD[0][0])] + CD[0][1]

    que = deque()
    que.append(1)

    while que:
        tmp = que.popleft()
        for v, a, b in G[tmp]:
            flag = False
            for i in range(50 * 49 + 1):
                if DP[v][i] > DP[tmp][i + a] + b:
                    flag = True
                    DP[v][i] = DP[tmp][i + a] + b
            c = CD[v - 1][0]
            d = CD[v - 1][1]
            if flag:
                for i in range(50 * 50 + 1):
                    DP[v][i] = min(DP[v][i], DP[v][max(0, i - c)] + d)
                que.append(v)

    for i in range(2, N + 1):
        print (DP[i][0])

    # print ()            
                
    # for tmp in DP[1:]:
    #     print (tmp[:10])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict as dd
input = sys.stdin.readline
N, M, S = map(int, input().split())
e = dd(list)
for _ in range(M):
  u, v, a, b = map(int, input().split())
  u -= 1
  v -= 1
  for x in range(a, 2501):
    e[N * x + u].append((N * (x - a) + v, b))
    e[N * x + v].append((N * (x - a) + u, b))
for i in range(N):
  c, d = map(int, input().split())
  for x in range(2501):
    e[N * x + i].append((N * min(2500, x + c) + i, d))
import heapq
class dijkstra:
  def __init__(self, n, e):
    self.e = e
    self.n = n
  def path(self, s, t):
    d = [float("inf")] * (self.n + 1)
    vis = set()
    d[s] = 0
    h = [s]
    while len(h):
      v = heapq.heappop(h)
      v1 = v % (10 ** 6)
      v0 = v // (10 ** 6)
      if v1 in vis: continue
      vis.add(v1)
      for p in self.e[v1]:
        #print(p)
        d[p[0]] = min(d[p[0]], d[v1] + p[1])
        if p[0] in vis: continue
        heapq.heappush(h, d[p[0]] * (10 ** 6) + p[0])
    return d
#print(len(e))
dij = dijkstra(2501 * N, e)
p = dij.path(min(S, 2500) * N, 0)
for i in range(1, N):
  res = float("inf")
  for j in range(2501):
    res = min(res, p[i + N * j])
  print(res)

Submission status: Accepted

Solution code:
#設定
import sys
input = sys.stdin.buffer.readline

#ライブラリインポート
from collections import defaultdict
from heapq import heappop, heappush

con = 10 ** 9 + 7
INF = float('inf')

#入力受け取り
def getlist():
	return list(map(int, input().split()))

class Graph(object):
	def __init__(self):
		self.graph = defaultdict(list)

	def __len__(self):
		return len(self.graph)

	def add_edge(self, a, b, w):
		self.graph[a].append((b, w))

	def get_nodes(self):
		return self.graph.keys()

class Dijkstra(object):
	def __init__(self, graph, s):
		self.g = graph.graph
		self.dist = defaultdict(lambda: INF)
		self.dist[s] = 0
		self.Q = []
		heappush(self.Q, (self.dist[s], s))

		while self.Q:
			dist_u, u = heappop(self.Q)
			if self.dist[u] < dist_u:
				continue
			for v, w in self.g[u]:
				alt = dist_u + w
				if self.dist[v] > alt:
					self.dist[v] = alt
					heappush(self.Q, (alt, v))


#処理内容
def main():
	N, M, S = getlist()
	G = Graph()
	#グラフ構築
	for _ in range(M):
		U, V, A, B = getlist()
		for i in range(2500 - A + 1):
			G.add_edge(U * (10 ** 5) + 2500 - i, V * (10 ** 5) + 2500 - A - i, B)
			G.add_edge(V * (10 ** 5) + 2500 - i, U * (10 ** 5) + 2500 - A - i, B)

	for i in range(N):
		#i + 1が都市番号
		C, D = getlist()
		for j in range(2500):
			G.add_edge((i + 1) * (10 ** 5) + j, (i + 1) * (10 ** 5) + min(j + C, 2500), D)

	#ダイクストラ
	D = Dijkstra(G, 10 ** 5 + min(2500, S))

	for i in range(2, N + 1):
		ans = INF
		for j in range(2501):
			ans = min(D.dist[i * (10 ** 5) + j], ans)
		print(ans)
	




if __name__ == '__main__':
	main()

Submission status: Accepted

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

N,M,S=map(int,input().split())
E=[[] for i in range(N+1)]
for i in range(M):
    u,v,a,b=map(int,input().split())
    E[u].append((v,a,b))
    E[v].append((u,a,b))

C=[(0,0)]+[tuple(map(int,input().split())) for i in range(N)]
DP=[[1<<60]*5001 for i in range(51)]

import heapq

Q=[(0,min(S,5000),1)]
DP[1][min(S,5000)]=0

while Q:
    time,money,town = heapq.heappop(Q)

    for to,pmoney,ptime in E[town]:
        if money>=pmoney and DP[to][money-pmoney]>time+ptime:
            DP[to][money-pmoney]=time+ptime
            heapq.heappush(Q,(time+ptime,money-pmoney,to))
            
    if DP[town][min(money+C[town][0],5000)]>time+C[town][1]:
        DP[town][min(money+C[town][0],5000)]=time+C[town][1]
        heapq.heappush(Q,(time+C[town][1],min(money+C[town][0],5000),town))
        
for i in range(2,N+1):
    print(min(DP[i]))

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

n,m,s = [int(i) for i in readline().split()]
g = [[] for _ in range(n)]
for i in range(m):
    u,v,a,b = [int(i) for i in readline().split()]
    u -= 1
    v -= 1
    g[u].append((v,a,b))
    g[v].append((u,a,b))


cd = [int(i) for i in read().split()]
c = cd[::2]
d = cd[1::2]


from heapq import *
INF = 1<<61
M = 2500
if s >= M: s = M-1
dist = [[INF]*M for _ in range(n)] #startからの最短距離
dist[0][s] = 0
q = [(0,s,0)] #(そこまでの距離、銀の枚数、点)

while q:
    dv,num,v = heappop(q)
    if dist[v][num] < dv: continue
    if num+c[v] < M and dv+d[v] < dist[v][num+c[v]]:
        dist[v][num+c[v]] = dv + d[v]
        heappush(q, (dv + d[v], num+c[v] ,v))
    for to,a,b in g[v]:
        if num >= a and dv + b < dist[to][num-a]:
            dist[to][num-a] = dv + b
            heappush(q, (dv + b, num-a ,to))
    #print(q)

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

#print(c)
#print(d)
#print(dist)

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<<60]*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] > 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
from collections import defaultdict
from heapq import *

def dijkstra(sta):
    dist = [10**18]*(N*2510)
    dist[sta] = 0
    pq = []
    heappush(pq, (dist[sta], sta))
    
    while pq:
        d, v = heappop(pq)
        
        if dist[v]<d:
            continue
        
        for nv, w in G[v]:
            if dist[nv]>dist[v]+w:
                dist[nv] = dist[v]+w
                heappush(pq, (dist[nv], nv))
    
    return dist

N, M, S = map(int, input().split())
serial = [[0]*2510 for _ in range(N)]
c = 0

for i in range(N):
    for j in range(2510):
        serial[i][j] = c
        c += 1

G = [[] for _ in range(N*2510)]

for _ in range(M):
    u, v, a, b = map(int, input().split())
    u -= 1
    v -= 1
    
    for i in range(a, 2510):
        G[serial[u][i]].append((serial[v][i-a], b))
        G[serial[v][i]].append((serial[u][i-a], b))

for i in range(N):
    c, d = map(int, input().split())
    
    for j in range(2510):
        if j+c<2510:
            G[serial[i][j]].append((serial[i][j+c], d))

dist = dijkstra(serial[0][min(S, 2509)])

for i in range(1, N):
    ans_i = 10**18
    
    for j in range(2510):
        ans_i = min(ans_i, dist[serial[i][j]])
    
    print(ans_i)

Submission status: Accepted

Solution code:
#(i,j)...i都市でj枚の銀貨を持てる最小時間(j<=2500)
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: Runtime Error

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, M, S = mapint()
graph = [{} for _ in range(N)]
for _ in range(M):
    u, v, a, t = mapint()
    graph[u-1][v-1] = (a, t)
    graph[v-1][u-1] = (a, t)

change = [list(mapint()) for _ in range(N)]
from heapq import heappop, heappush
# time, silver, vertex
Q = [(0, S, 0)]
dist = [[10**18]*2501 for _ in range(N)]
dist[0][S] = 0

while Q:
    t, s, v = heappop(Q)
    rate, change_time = change[v]
    if s<2500 and dist[v][min(2500, s+rate)]>t+change_time:
        dist[v][min(2500, s+rate)] = t+change_time
        heappush(Q, (t+change_time, min(2500, s+rate), v))
    for nx in graph[v].keys():
        nx_s, nx_t = graph[v][nx]
        if nx_s<=s and dist[nx][s-nx_s]>t+nx_t:
            dist[nx][s-nx_s] = t+nx_t
            heappush(Q, (t+nx_t, s-nx_s, nx))
for i in range(1, N):
    print(min(dist[i]))

Submission status: Runtime Error

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

def dijkstra(s,n):
    hq = [(0, s)]
    heapq.heapify(hq) # リストを優先度付きキューに変換
    cost = [float('inf')] * n # 行ったことのないところはinf
    cost[s] = 0 # 開始地点は0
    while hq:
        c, v = heapq.heappop(hq)
        if c > cost[v]: # コストが現在のコストよりも高ければスルー
            continue
        for d, u in e[v]:
            tmp = d + cost[v]
            if tmp < cost[u]:
                cost[u] = tmp
                heapq.heappush(hq, (tmp, u))
    return cost


e = [[] for _ in range(1000*(n+1))]
for i in range(n):
    c,d=cd[i]
    for j in range(250):
        e[1000*i+j].append((d,1000*i+min(j+c,250)))
    
for i in range(m):
    u,v,a,b=uvab[i]
    u,v = u-1, v-1
    for j in range(250):
        if j-a>=0:
            e[1000*v+j].append((b,1000*u+j-a))
            e[1000*u+j].append((b,1000*v+j-a))
# print(e)
lst=dijkstra(s,1000*(n+1))
# print(lst)
for i in range(1,n):
    ans=float('inf')
    for j in range(250):
        ans=min(ans,lst[1000*i+j])
    print(ans)

Submission status: Runtime Error

Solution code:
import heapq

N, M, S = map(int, input().split())
Cost = [[[-1, -1] for _ in range(N)] for _ in range(N)]
Change = [[0]*2 for _ in range(N)]
A_m = 0
for i in range(M):
    u, v, a, b = map(int, input().split())
    A_m = max(A_m, a)
    Cost[u-1][v-1][0] = a
    Cost[u-1][v-1][1] = b
    Cost[v-1][u-1][0] = a
    Cost[v-1][u-1][1] = b
for i in range(N):
    c, d = map(int, input().split())
    Change[i][0] = c
    Change[i][1] = d
if S > 2500:
    S = 2500

def dijkstra(N, start, Cost, Change):
    minHeap = []
    used = [[10**12]*(A_m*N + 1) for _ in range(N)]
    used[start][S] = 0
    heapq.heappush(minHeap, (0, S, start))
    while minHeap:
        (c, hold, current) = heapq.heappop(minHeap)
        for road in range(N):
            if Cost[current][road][0] != -1:
                if hold >= Cost[current][road][0]:
                    if used[road][hold - Cost[current][road][0]] > c + Cost[current][road][1]:
                        used[road][hold - Cost[current][road][0]] = c + Cost[current][road][1]
                        heapq.heappush(minHeap, (c + Cost[current][road][1], hold - Cost[current][road][0], road))
        if hold + Change[current][0] <= A_m*N:
            if used[current][hold + Change[current][0]] > c + Change[current][1]:
                heapq.heappush(minHeap, (c + Change[current][1], hold + Change[current][0], current))
    return used

T = dijkstra(N, 0, Cost, Change)
for i in T[1:]:
    print(min(i))

Submission status: Runtime Error

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools, bisect
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def S(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]

alphabets = "abcdefghijklmnopqrstuvwxyz"
ALPHABETS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"

sys.setrecursionlimit(1000000)
dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
MOD = 1000000007
INF = float("inf")

def main():
    N, M, S = LI()
    UVAB = LIR(M)
    CD = LIR(N)

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

    dist = [[INF] * 2500 for _ in range(N)]
    heap = [(0, 0, min(2500, S))]

    while heap:
        cost, u, s = heappop(heap)
        c, d = CD[u]
        dist[u][s] = cost

        if s + c < 2500 and dist[u][s + c] > cost + d:
            heappush(heap, (cost + d, u, s + c))
        for v, a, b in edge[u]:
            if s - a >= 0 and dist[v][s - a] > cost + b:
                heappush(heap, (cost + b, v, s - a))

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

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import heapq
def dijkstra_heap(N,S,edge):
  d = [[float('inf')]*5001 for _ in range(N)] #始点0から各頂点への最短距離
  used = [[False]*5001 for _ in range(N)]
  d[0][S] = 0
  used[0][S] = True
  edgelist = []
  #edgelist : [(0,S)からの暫定(未確定)最短時間,頂点,銀貨の枚数]のリスト
  #edge[s] : sから出る枝の[重み,頂点,銀貨の枚数]のリスト
  for w,v,sil in edge[0]:
    if S+sil>=0:
      heapq.heappush(edgelist,[w,v,S+sil]) #sの隣の点は枝の重さがそのまま暫定最短距離となる
  while len(edgelist):
    #まだ使われてない頂点の中から最小の距離のものを探す→確定させる
    min_w,min_v,min_sil = heapq.heappop(edgelist)
    #min_w,min_v,min_sil : [0からの(確定)最短距離,頂点,銀貨の枚数]
    if used[min_v][min_sil]:
      continue
    d[min_v][min_sil] = min_w
    used[min_v][min_sil] = True
    for w,v,sil in edge[min_v]:
      if min_sil+sil>=0 and min_sil+sil<=5000 and not used[v][min_sil+sil]:
        heapq.heappush(edgelist,[min_w+w,v,min_sil+sil])
  return d

def solve():
  N, M, S = map(int, input().split())
  edge = [[] for _ in range(N)]
  for i 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])
  for i in range(N):
    c,d = map(int, input().split())
    edge[i].append([d,i,c])
  D = dijkstra_heap(N,S,edge)
  ans = [0]*N
  for i in range(1,N):
    ans[i] = min(D[i])
  return ans[1:]
print(*solve(),sep='\n')

Submission status: Runtime Error

Solution code:
N,M,S=map(int,input().split())

ways=[[] for _ in range(N)]
CD=[[0]*2 for _ in range(N)]

class Way:
  def __init__(self,t,f,ti):
    self.to=t
    self.fare=f
    self.time=ti 

for i in range(M):
  U,V,A,B=map(int,input().split())
  U-=1
  V-=1
  ways[U].append(Way(V,A,B))
  ways[V].append(Way(U,A,B))

for i in range(N):
  C,D=map(int,input().split())
  CD[i][0]=C
  CD[i][1]=D
  
#dp[i][j]:駅iにおいて銀貨をj枚所持するための最短時間
dp=[[float("inf")]*(50*N+1) for _ in range(N)]
dp[0][S]=0
import heapq

#data型は(時間、駅、お金)
#q=heapq.heapify([(0,0,S)])
#q=heapq.heapify([])
q=[]
heapq.heappush(q,(0,0,S))
#print(q)
def Push(time,station,money):
  #print("called")
  global q,dp
  if money<0:
    return
  money=min(money,50*N)
  if dp[station][money] <= time:
    return
  dp[station][money] = time
  heapq.heappush(q,(time,station,money))

while q:
  #print("called!")
  dat = heapq.heappop(q)
  time,station,money=dat[0],dat[1],dat[2]
  
  if dp[station][money]!=time:
    continue
  #まず、両替。
  Push(time+CD[station][1],station,money+CD[station][0])
  #次に、各道について移動
  for w in ways[station]:
    Push(time+w.time,w.to,money-w.fare)

for i in range(1,N):
  ans=float("inf")
  for j in range(50*N+1):
    ans=min(ans,dp[i][j])
  print(ans)

Submission status: Runtime Error

Solution code:
from heapq import heapify,heappush,heappop

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

# !!グラフの作成!! #
tmp = [list(map(int, input().split())) for _ in range(M)]

U = [0 for _ in range(M)]
V = [0 for _ in range(M)]
A = [0 for _ in range(M)]
B = [0 for _ in range(M)]

for i in range(M):
  U[i] = tmp[i][0] -1
  V[i] = tmp[i][1] -1
  A[i] = tmp[i][2]
  B[i] = tmp[i][3]
A_m = max(A)
I = [[] for _ in range(N * (N*A_m+1))] 
# 隣接リスト(頂点iで銀貨j枚持ちのとき、i*N*(A_m+1)+jとおく)
for i in range(M):
  for j in range(A[i], N*A_m+1):
    I[U[i]*(N*A_m+1)+j].append((V[i]*(N*A_m+1)+j-A[i],B[i]))
    I[V[i]*(N*A_m+1)+j].append((U[i]*(N*A_m+1)+j-A[i],B[i]))

for i in range(N):
  C, D = map(int, input().split())
  for j in range(N*A_m+1):
    I[i*(N*A_m+1)+j].append((i*(N*A_m+1)+min(C+j,N*A_m),D))
  
def dijkstra(I):# I:隣接リスト(頂点、コスト、そのほか制約) 
  N = len(I)
  task = [] 
  visited = [0 for _ in range(N)]
  min_cost = [0 for _ in range(N)]
  cost = [10**20 for _ in range(N)]
  prev_points = [0 for _ in range(N)]
  heappush(task, (0, S, -1))
  # !!比較値がスカラーでないときは、一番左の0を適宜変更する!! #
  # !!最初の点番号が0でないときは、真ん中の0を変更する!! #
  
  flag = 0
  while task:
    while task:
      c, p, prev = heappop(task)    
      if visited[p] == 0:
        break  
      if len(task) == 0:
        flag = 1
    if flag == 1:
      break
    #print(task)
    visited[p] = 1
    min_cost[p] = c
    prev_points[p] = prev
  
    for j, c_ad in I[p]: #制約が入るときはここに追加
      if visited[j] == 1: continue
      #print(p//(N*A_m+1),p%(N*A_m+1),j//(N*A_m+1),j%(N*A_m+1),c_ad)
      cost_next = next_cost(I, p, j, c, c_ad)
      if cost[j] > cost_next:
        cost[j] = cost_next
        heappush(task, (cost_next, j, p))

  return (min_cost, prev_points)

def next_cost(I, p, j, c, c_ad): # !!現在の点pから次の点jへのコストを計算する方法を記入!! #  
#c:点pにつくまでに払ったコスト、c_ad:次回追加されるコスト#
  return c + c_ad

min_cost, prev_points = dijkstra(I)

for i in range(1, N):
  print(min(min_cost[i*(N*A_m+1):(i+1)*(N*A_m+1)]))