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: Time Limit Exceeded

Solution code:
from heapq import *
import collections
I = [int(_) for _ in open(0).read().split()]
N, M, S = I[:3]
I1 = I[3:3 + 4 * M]
U, V, A, B = I1[::4], I1[1::4], I1[2::4], I1[3::4]
I2 = I[3 + 4 * M:]
C, D = I2[::2], I2[1::2]

INF = float('inf')
ma = max(A)
S = min(ma * (N - 1), S)
Di = collections.defaultdict(lambda: INF)

G = collections.defaultdict(lambda: collections.defaultdict(int))

for u, v, a, b, in zip(U, V, A, B):
    u -= 1  # 0-indexed
    v -= 1  # 0-indexed
    G[u][v] = (a, b)
    G[v][u] = (a, b)

H = [(0, S, 0)]
while H:
    du, s, u = heappop(H)
    c = C[u]
    d = D[u]
    if Di[s, u] <= du:
        continue
    Di[s, u] = du
    for v, ab in G[u].items():
        a, b = ab
        if s - a >= 0:
            heappush(H, (du + b, s - a, v))
    for i in range(s):
        heappush(H, (du, i, u))
    for i in range(s + 1, ma * (N - 1) + 1):
        heappush(H, (du + d * ((i - s - 1) // c + 1), i, u))
ans = [INF] * N
for s in range(ma * (N - 1)):
    for n in range(N):
        ans[n] = min(ans[n], Di[s, n])
print('\n'.join(map(str, ans[1:])))

Submission status: Time Limit Exceeded

Solution code:


import heapq
from collections import defaultdict
h = []
heapq.heapify(h)

n, m, s = list(map(int, input().split()))
a, b = [[None] * m for _ in range(2)]
c, d = [[None] * n for _ in range(2)]

ns = defaultdict(list)
uv2e = {}
for i in range(m):
    u,v,a[i],b[i] = list(map(int, input().split()))
    ns[u-1].append(v-1)
    ns[v-1].append(u-1)
    uv2e[u-1,v-1] = i
    uv2e[v-1,u-1] = i
for i in range(n):
    c[i], d[i] = list(map(int, input().split()))

maxs = max(a)*(n-1)
s = min(s, maxs)
state = (0, 0, s) # (距離, ノード, 銀貨枚数)
ans = [[None] * (maxs+1) for _ in range(n)]
heapq.heappush(h, state)
count = 0
while h:
    count += 1
    dd, u, ss = heapq.heappop(h)
#     print(dd, u, ss)
    ans[u][ss] = min(ans[u][ss], dd) if ans[u][ss] is not None else dd
    # グラフの隣接点
    for v in ns[u]:
        e= uv2e[u,v]
        if ss<a[e] or ans[v][ss-a[e]] is not None:
            continue
        heapq.heappush(h, (dd + b[e], v, ss-a[e]))
    # 両替
    if ss+c[u] <= maxs:
        heapq.heappush(h, (dd + d[u], u, ss+c[u]))
    elif ss < maxs:
        heapq.heappush(h, (dd + d[u], u, maxs))

for item in ans[1:]:
    print(min(item))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from scipy.sparse import lil_matrix, csr_matrix
from scipy.sparse.csgraph import shortest_path
M=49*50+1
n,m,s=map(int,input().split())
s=min(s,M-1)
G=lil_matrix((n*M,n*M),dtype=np.int64)
for _ in range(m):
    a,b,silver,time=map(int,input().split())
    a-=1
    b-=1
    for i in range(silver,M):
        G[a*M+i,b*M+i-silver]=time
        G[b*M+i,a*M+i-silver]=time
for i in range(n):
    silver,time=map(int,input().split())
    for j in range(M-1):
        G[i*M+j,i*M+min(j+silver,M-1)]=time
G=G.tocsr()
G=shortest_path(G,method='D',indices=s) # D=VlogE ndarray

for i in range(1,n):
    ans=np.min(G[i*M:i*M+M])
    print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
n, m, s = map(int, input().split())

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

banks = tuple(tuple(map(int, input().split())) for _ in range(n))

max_s = 50 * (n-1)

s = min(s, max_s)

import heapq

h = []
dp = [[float('inf')] * (max_s+1) for _ in range(n)]
ans = [float('inf')] * n

heapq.heappush(h, (0, 0, s))
while h:
    time, node, coin = heapq.heappop(h)
    if time < dp[node][coin]:
        dp[node][coin] = time
    if time < ans[node]:
        ans[node] = time

    c, d = banks[node]
    if coin < max_s:
        heapq.heappush(h, (time+d, node, min(coin + c, max_s)))

    for n, a, b in edges[node]:
        new_time = time + b
        new_coin = coin - a
        if new_coin < 0 or new_time >= dp[n][new_coin]:
            continue
        heapq.heappush(h, (new_time, n, new_coin))

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

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate, product
import sys
import bisect
import string
import math
import time


def I(): return int(input())


def S(): return input()


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


def MS(): return map(str, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def debug(table, *args):
    ret = []
    for name, val in table.items():
        if val in args:
            ret.append('{}: {}'.format(name, val))
    print(' | '.join(ret), file=sys.stderr)


yn = {False: 'No', True: 'Yes'}
YN = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']

show_flg = False
# show_flg = True

def dijkstra(cost, start):
    n = len(cost)
    dist = [IINF] * n
    visited = [False] * n
    dist[start] = 0

    while True:
        v = -1
        for i in range(n):
            if not visited[i] and v == -1:
               v = i
            elif not visited[i] and dist[i] < dist[v]:
               v = i

        if v == -1:
            break

        visited[v] = True

        for i in range(n):
            dist[i] = min(dist[i], dist[v] + cost[v][i])

    return dist

MX = 2500

def trans(e, s):
    return MX * e + s


def main():
    N, M, S = MI()
    U = [0] * M
    V = [0] * M
    A = [0] * M
    B = [0] * M
    C = [0] * N
    D = [0] * N
    edges = [[] for i in range(N)]
    cost = [[IINF] * N * MX for i in range(N * MX)]

    for i in range(M):
        U[i], V[i], A[i], B[i] = MI()
        U[i] -= 1
        V[i] -= 1
        edges[U[i]].append((V[i], i))
        edges[V[i]].append((U[i], i))

    for i in range(N):
        C[i], D[i] = MI()

    for i in range(N):
        for j in range(0, MX):
            to = min(j + C[i], MX-1)
            cost[trans(i, j)][trans(i, to)] = D[i]
            for pair in edges[i]:
                to = pair[0]
                idx = pair[1]
                if j - A[idx] >= 0:
                    cost[trans(i, j)][trans(to, j - A[idx])] = B[idx]

    S = min(2499, S)
    # print('S', S)
    ret = dijkstra(cost, trans(0, S))

    # print()
    # for i in range(1, N):
    #     print(i, *['IINF' if v == IINF else "{:0=4}".format(v) for v in cost[i]])

    for i in range(1, N):
        ans = IINF
        for j in range(MX):
            # if j <= 4:
            #     print(i, j, cost[i][j])
            ans = min(ans, ret[trans(i, j)])
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N, M, S = map(int, input().split())
road = [[] for i in range(N+1)]#road[i]がとしiから伸びる[to, cost, time]が入る
cosa = []
for i in range(M):
    u,v,a,b = map(int, input().split())
    road[u].append([v,a,b])
    road[v].append([u,a,b])
    cosa.append(a)
city = [[]]#city[i]がi番目の都市の[枚数, 時間]になってる
for i in range(N):
    c,d = map(int, input().split())
    city.append([c,d])

import heapq
d = [0]*(N+1)#d[i]には都市iでの最短時間が入ってる dp[0]は無意味
used = [False]*(N+1)
used[0] = True
que = []#queには[時間,位置,所持銀貨の枚数が入ってる]
que.append([0,1,S])
ma = max(cosa)
maa = ma*(N+1)
while True:
    mn = heapq.heappop(que)
    if not used[mn[1]]:
        d[mn[1]] = mn[0]
        used[mn[1]] = True
    for item in road[mn[1]]:
        if mn[2] < item[1]:
            a = int((item[1]-mn[2])/city[mn[1]][0])
            if not a*city[item[0]] == item[1]-mn[2]:
                a += 1
            si = a*city[mn[1]][0]-item[1] #渡ったあとのシルバーの数
            ti = a*city[mn[1]][1] + item[2] + mn[0]
            if si > maa:
                si = maa
            heapq.heappush(que,[ti,item[0],si])
        else:
            si = mn[2]-item[1]
            ti = mn[0]+item[2]
            heapq.heappush(que,[ti,item[0],si])
    k = mn[2]
    kt = mn[0]
    while k < maa:
        k = k + city[mn[1]][0]
        kt = kt + city[mn[1]][1]
        heapq.heappush(que,[kt,mn[1],k])
    if used == [True]*(N+1):
      break

for i in d[2:]:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
import heapq
import sys

input = sys.stdin.readline

inf = 10**13

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

data = [[] for _ in range(N)]

sumA = 0

for i in range(M):
    U,V,A,B = map(int,input().split())
    sumA += A
    U -= 1
    V -= 1
    data[U].append((B,V,A))###(距離, 行き先, 費用)
    data[V].append((B,U,A))###(距離, 行き先, 費用)

P = sumA

C = [0]*N
D = [0]*N

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

dist = [[inf]*(P+1) for _ in range(N)]
#visit = [[0]*(P+1) for _ in range(N)]
###heapにぶち込んだことがあるかないか

q = [(0,0,min(S,P))]###(仮の最短距離, 頂点番号, 所持金)
heapq.heapify(q)

while q:
    v = heapq.heappop(q)
    if v[0] >= dist[v[1]][v[2]]:
        continue
    dist[v[1]][v[2]] = v[0]

    if v[2] + C[v[1]] <= P:
        heapq.heappush(q,(v[0]+D[v[1]],v[1],v[2]+C[v[1]]))

    for x in data[v[1]]:
        if x[2] > v[2]:
            continue
        heapq.heappush(q,(v[0]+x[0],x[1],v[2]-x[2]))
    
    ###
    #print(P)
    #print(q)
    #print(v)
    ###

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

Submission status: Time Limit Exceeded

Solution code:
import heapq
import sys

input = sys.stdin.readline

inf = 10**12

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

data = [[] for _ in range(N)]

sumA = 0

for i in range(M):
    U,V,A,B = map(int,input().split())
    sumA += A
    U -= 1
    V -= 1
    data[U].append((B,V,A))###(距離, 行き先, 費用)
    data[V].append((B,U,A))###(距離, 行き先, 費用)

P = sumA

C = [0]*N
D = [0]*N

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

dist = [[inf]*(P+1) for _ in range(N)]
#visit = [[0]*(P+1) for _ in range(N)]
###heapにぶち込んだことがあるかないか

q = [(0,0,min(S,P))]###(仮の最短距離, 頂点番号, 所持金)
heapq.heapify(q)

while q:
    v = heapq.heappop(q)
    if v[0] > dist[v[1]][v[2]]:
        continue
    dist[v[1]][v[2]] = v[0]

    if v[2] + C[v[1]] <= P:
        heapq.heappush(q,(v[0]+D[v[1]],v[1],v[2]+C[v[1]]))

    for x in data[v[1]]:
        if x[2] > v[2]:
            continue
        heapq.heappush(q,(v[0]+x[0],x[1],v[2]-x[2]))
    
    ###
    #print(P)
    #print(q)
    #print(v)
    ###

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

Submission status: Time Limit Exceeded

Solution code:
import heapq

inf = 10**12

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

data = [[] for _ in range(N)]

maxA = 0

for i in range(M):
    U,V,A,B = map(int,input().split())
    maxA = max(maxA,A)
    U -= 1
    V -= 1
    data[U].append((B,V,A))###(距離, 行き先, 費用)
    data[V].append((B,U,A))###(距離, 行き先, 費用)

P = maxA * (N-1)

C = [0]*N
D = [0]*N

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

dist = [[inf]*(P+1) for _ in range(N)]
#visit = [[0]*(P+1) for _ in range(N)]
###heapにぶち込んだことがあるかないか

q = [(0,0,min(S,P))]###(仮の最短距離, 頂点番号, 所持金)
heapq.heapify(q)

while q:
    v = heapq.heappop(q)
    if v[0] > dist[v[1]][v[2]]:
        continue
    dist[v[1]][v[2]] = v[0]

    if v[2] + C[v[1]] <= P:
        heapq.heappush(q,(v[0]+D[v[1]],v[1],v[2]+C[v[1]]))

    for x in data[v[1]]:
        if x[2] > v[2]:
            continue
        heapq.heappush(q,(v[0]+x[0],x[1],v[2]-x[2]))
    
    ###
    #print(P)
    #print(q)
    #print(v)
    ###

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

Submission status: Time Limit Exceeded

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

INF = 10**12
n, m, s = map(int, input().split())
edges = defaultdict(lambda: defaultdict(lambda: [INF, INF]))
cd = []
max_a = 0

for i in range(m):
    u, v, a, b = map(int, input().split())
    max_a = max(max_a, a)
    edges[u-1][v-1] = [a, b]
    edges[v-1][u-1] = [a, b]

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

# 解答ACする
# Dijakstraの状態を(頂点、所持している銀貨の枚数, cost)で持つ
SIZE = max_a * n + 1
# SIZE = 2550
if s > SIZE:
    s = SIZE
nodes = [[INF for _ in range(SIZE+1)] for _ in range(n)]
nodes[0][s] = 0

def dijakstra():
    goals = set({0})
    que = [(0, 0, s)]
    heapify(que)
    while 10**6 > len(que) > 0:
        if len(goals) >= n:
            break
        cost, num, silver = heappop(que)
        if num not in goals:
            goals.add(num)
        c, d = cd[num]
        s_tmp = min(SIZE, silver+c)
        if silver < SIZE and s_tmp != silver:
            heappush(que, (cost + d, num, s_tmp))
            nodes[num][s_tmp] = min(nodes[num][s_tmp], cost + d)
        for v in edges[num].keys():
            a, b = edges[num][v]
            if silver >= a:
                if nodes[v][silver-a] > cost + b:
                    heappush(que, (cost + b, v, silver - a))
                    nodes[v][silver - a] = min(nodes[v][silver - a], cost + b)

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

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappop, heappush

import sys
def input():return sys.stdin.readline().strip()

def main():
    N, M, S = map(int, input().split())
    to = [{} for _  in range(N)]
    for _ in range(M):
        u, v, a, b = map(int, input().split())
        u -= 1
        v -= 1
        to[u][v] = (a, b)
        to[v][u] = (a, b)
    info = tuple(tuple(map(int, input().split())) for _ in range(N))

    MAX_SILVER = 50 * (N-1)
    INF = 10 ** 18
    # dijkstra (time, vertex, money)
    visited = [[False]*(MAX_SILVER+1) for _ in range(N)]
    cost = [[INF]*(MAX_SILVER+1) for _ in range(N)]
    q = []
    S = min(S, MAX_SILVER)
    heappush(q, (0, 0, S)) # (time, vertex, silver)

    while q:
        t, now, s = heappop(q)
        if visited[now][s]:continue
        visited[now][s] = True
        cost[now][s] = t

        # next node
        for nv, (a, b) in to[now].items():
            nt = t + b
            rest = s - a
            if rest >= 0:
                if cost[nv][rest] <= nt : continue 
                heappush(q, (nt, nv, rest))
        
        # exchange gold with silver
        rate, time = info[now]
        for i, ns in enumerate(range(s + rate, MAX_SILVER, rate), 1):
            nt = t + time * i
            if cost[nv][ns] <= nt : continue
            heappush(q, (nt, now, ns))
    
    for i in range(1, N):
        print(min(cost[i]))

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
N, M, S = map(int, input().split(" "))
adj = [ [] for _ in range(N) ] 
convert = []
cost_max = 0
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) )
    cost_max = max(cost_max, a)

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

import heapq 

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

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

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

Submission status: Time Limit Exceeded

Solution code:
N, M, S = map(int, input().split(" "))
adj = [ [] for _ in range(N) ] 
convert = []
cost_max = 0
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) )
    cost_max = max(cost_max, a)

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

import heapq 

limit = cost_max*N
S = min(S, limit)
h = [ (0, 0, S) ] 
ans = [  [-1]*(limit+1) for _ in range(N) ]

while h != [] :
    time_consumed, city, coin = heapq.heappop(h)
    if ans[city][coin] != -1:
        continue
    ans[city][coin] = time_consumed
            
    while coin <= limit :
        for v, a, b in adj[city] :
            if coin - a < 0 or ans[v][coin-a] != -1:
                continue
            heapq.heappush( h, (time_consumed+b, v, coin-a) )
        coin += convert[city][0]
        time_consumed += convert[city][1]

for i in range(1, N) :
    _min = float('inf')
    for j in range(limit+1) :
        if ans[i][j] == -1 : 
            continue
        _min = min(_min, ans[i][j])
    print(_min)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop
import sys
sys.setrecursionlimit(10**7)
from time import sleep

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(ss) for ss in input().split(" ")]

def rangeI(it, l, r):
    for i, e in enumerate(it):
        if l <= i < r:
            yield e
        elif l >= r:
            break

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

# cdef int n,m,s,co,coin,city,max_coin,u,v,a,b
# cdef long long time

n,m,s = get_nums_l()

# 銀貨所持枚数の上限。確実に最短経路を通過できる枚数
max_coin = 50*(n-1)
s = min(s, max_coin)

lines = list(map(lambda line: line.strip(), sys.stdin.readlines()))

# rails[i] = 都市iを始点とする路線情報(行き先, 運賃, 時間)
rails  = [ [] for _ in range(n + 1) ]
for line in rangeI(lines, 0, m):
    u,v,a,b = map(int, line.split())
    rails[u].append([v, a, b])
    rails[v].append([u, a, b])

cities = [None] + [ list(map(int, line.split())) for line in rangeI(lines, m, m+n) ]

# log("rails:", rails)
# log("cities:", cities)

# t = 目的地
# for t in range(2, n+1):
    # log("t:", t)

# table[i][j] = 現在頂点i, 銀貨j枚持っている場合の最小時間
table = [ [999999999999999999] * (max_coin + 1) for _ in range(n+1)]
hq = []
# 初期状態 時間0, 都市1, 銀貨s枚
heappush(hq, (0, 1, s))

check = {i for i in range(2, n+1) }

while hq:
    # sleep(0.1)
    time, city, coin,  = heappop(hq)

    # if city == t:
    #     print(time)
    #     break

    if table[city][coin] <= time:
        continue

    # for co in range(coin+1):
    #     if table[city][co] > time:
    #         table[city][co] = time

    table[city][coin] = time
    
    if city in check:
        check.remove(city)
        if len(check) == 0:
            break


    # log(city, coin, time)

    # ここで両替した場合 銀貨と時間を増やす
    # log("-", city, min(max_coin, coin+cities[city][0]), time + cities[city][1])
    heappush(hq, (time + cities[city][1], city, min(max_coin, coin+cities[city][0])))

    # 進める都市に進む
    for v, a, b in rails[city]:
        if coin < a:
            # 銀貨が足りないと移動できない
            continue
        # log("-", v, coin-a, time + b)
        heappush(hq, (time+b, v, coin-a))

for t in range(2, n+1):
    print(min(table[t]))

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop
import sys
sys.setrecursionlimit(10**7)
from time import sleep

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(ss) for ss in input().split(" ")]

def rangeI(it, l, r):
    for i, e in enumerate(it):
        if l <= i < r:
            yield e
        elif l >= r:
            break

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

# cdef int n,m,s,co,coin,city,max_coin,u,v,a,b
# cdef long long time

n,m,s = get_nums_l()

# 銀貨所持枚数の上限。確実に最短経路を通過できる枚数
max_coin = 50*(n-1)
s = min(s, max_coin)

lines = list(map(lambda line: line.strip(), sys.stdin.readlines()))

# rails[i] = 都市iを始点とする路線情報(行き先, 運賃, 時間)
rails  = [ [] for _ in range(n + 1) ]
for line in rangeI(lines, 0, m):
    u,v,a,b = map(int, line.split())
    rails[u].append([v, a, b])
    rails[v].append([u, a, b])

cities = [None] + [ list(map(int, line.split())) for line in rangeI(lines, m, m+n) ]

# log("rails:", rails)
# log("cities:", cities)

# t = 目的地
# for t in range(2, n+1):
    # log("t:", t)

# table[i][j] = 現在頂点i, 銀貨j枚持っている場合の最小時間
table = [ [999999999999999999] * (max_coin + 1) for _ in range(n+1)]
hq = []
# 初期状態 時間0, 都市1, 銀貨s枚
heappush(hq, (0, 1, s))

while hq:
    # sleep(0.1)
    time, city, coin,  = heappop(hq)

    # if city == t:
    #     print(time)
    #     break

    if table[city][coin] <= time:
        continue

    # for co in range(coin+1):
    #     if table[city][co] > time:
    #         table[city][co] = time

    table[city][coin] = time

    # log(city, coin, time)

    # ここで両替した場合 銀貨と時間を増やす
    # log("-", city, min(max_coin, coin+cities[city][0]), time + cities[city][1])
    heappush(hq, (time + cities[city][1], city, min(max_coin, coin+cities[city][0])))

    # 進める都市に進む
    for v, a, b in rails[city]:
        if coin < a:
            # 銀貨が足りないと移動できない
            continue
        # log("-", v, coin-a, time + b)
        heappush(hq, (time+b, v, coin-a))

for t in range(2, n+1):
    print(min(table[t]))

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop
import sys
sys.setrecursionlimit(10**7)
from time import sleep

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(ss) for ss in input().split(" ")]

def rangeI(it, l, r):
    for i, e in enumerate(it):
        if l <= i < r:
            yield e
        elif l >= r:
            break

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

# cdef int n,m,s,co,coin,city,max_coin,u,v,a,b
# cdef long long time

n,m,s = get_nums_l()

# 銀貨所持枚数の上限。確実に最短経路を通過できる枚数
max_coin = 50*(n-1)
s = min(s, max_coin)

lines = list(map(lambda line: line.strip(), sys.stdin.readlines()))

# rails[i] = 都市iを始点とする路線情報(行き先, 運賃, 時間)
rails  = [ [] for _ in range(n + 1) ]
for line in rangeI(lines, 0, m):
    u,v,a,b = map(int, line.split())
    rails[u].append([v, a, b])
    rails[v].append([u, a, b])

cities = [None] + [ list(map(int, line.split())) for line in rangeI(lines, m, m+n) ]

# log("rails:", rails)
# log("cities:", cities)

# t = 目的地
for t in range(2, n+1):
    # log("t:", t)

    # table[i][j] = 現在頂点i, 銀貨j枚持っている場合の最小時間
    table = [ [999999999999999999] * (max_coin + 1) for _ in range(n+1)]
    hq = []
    # 初期状態 時間0, 都市1, 銀貨s枚
    heappush(hq, (0, 1, s))

    while hq:
        # sleep(0.1)
        time, city, coin,  = heappop(hq)

        if city == t:
            print(time)
            break

        if table[city][coin] <= time:
            continue

        # for co in range(coin+1):
        #     if table[city][co] > time:
        #         table[city][co] = time

        table[city][coin] = time

        # log(city, coin, time)

        # ここで両替した場合 銀貨と時間を増やす
        # log("-", city, min(max_coin, coin+cities[city][0]), time + cities[city][1])
        heappush(hq, (time + cities[city][1], city, min(max_coin, coin+cities[city][0])))

        # 進める都市に進む
        for v, a, b in rails[city]:
            if coin < a:
                # 銀貨が足りないと移動できない
                continue
            # log("-", v, coin-a, time + b)
            heappush(hq, (time+b, v, coin-a))

Submission status: Time Limit Exceeded

Solution code:
# E - Two Currencies

import heapq

n, m, s = map(int, input().split())
adj = {u: [] for u in range(1, n+1)}
for i in range(m):
    u, v, a, b = map(int, input().split())
    adj[u].append((v, a, b)) # to, 料金, 時間
    adj[v].append((u, a, b)) # to, 料金, 時間
exch = {}
for u in range(1, n+1):
    c, d = map(int, input().split())
    exch[u] = (c, d) # レート, 時間

max_silver = 50 * m    # これだけ持ってたらどの都市へも行ける

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

# (都市,必要銀貨)を頂点とする最短経路問題

# 目的都市
for dest in range(2, n+1):
    # Dijkstra
    dist = {(dest, 0): 0}  # 開始頂点のみ距離0
    queue = [(0, dest, 0)]

    while len(queue) > 0:
        di, u, si = heapq.heappop(queue)
        # 用済みのデータ
        if (u, si) in dist and di > dist[(u, si)]:
            continue
        # 都市1に到達
        if u == 1 and si <= s:
            print(di)
            break

        # uに直接行ける各都市
        for v, a, b in adj[u]:
            if si + a > max_silver:
                break
            xsi = si + a
            if (v, xsi) not in dist or \
                dist[(v, xsi)] > di + b:
                dist[(v, xsi)] = di + b
                heapq.heappush(queue, (di + b, v, xsi))
        # 両替による遷移
        c, d = exch[u]
        xsi = max(si - c, 0)
        if (u, xsi) not in dist or \
            dist[(u, xsi)] > di + d:
            dist[(u, xsi)] = di + d
            heapq.heappush(queue, (di + d, u, xsi))

Submission status: Time Limit Exceeded

Solution code:
import math
from functools import reduce
from collections import deque
from heapq import heappush, heappop
import sys
sys.setrecursionlimit(10**7)
from time import sleep

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(ss) for ss in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def rangeI(it, l, r):
    for i, e in enumerate(it):
        if l <= i < r:
            yield e
        elif l >= r:
            break

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)


# cdef int n,m,s,co,coin,city,max_coin,u,v,a,b
# cdef long long time

n,m,s = get_nums_l()

# 銀貨所持枚数の上限。確実に最短経路を通過できる枚数
max_coin = 50*(n-1)
s = min(s, max_coin)

lines = list(map(lambda line: line.strip(), sys.stdin.readlines()))

# rails[i] = 都市iを始点とする路線情報(行き先, 運賃, 時間)
rails  = [ [] for _ in range(n + 1) ]
for line in rangeI(lines, 0, m):
    u,v,a,b = map(int, line.split())
    rails[u].append([v, a, b])
    rails[v].append([u, a, b])

cities = [None] + [ list(map(int, line.split())) for line in rangeI(lines, m, m+n) ]

# log("rails:", rails)
# log("cities:", cities)


# t = 目的地
for t in range(2, n+1):
    # log("t:", t)

    # table[i][j] = 現在頂点i, 銀貨j枚持っている場合の最小時間
    table = [ [999999999999999999] * (max_coin + 1) for _ in range(n+1)]
    hq = []
    # 初期状態 時間0, 都市1, 銀貨s枚
    heappush(hq, (0, 1, s))

    while hq:
        # sleep(0.1)
        time, city, coin,  = heappop(hq)

        if city == t:
            print(time)
            break

        if table[city][coin] <= time:
            continue

        # for co in range(coin+1):
        #     if table[city][co] > time:
        #         table[city][co] = time

        table[city][coin] = time

        # log(city, coin, time)

        # ここで両替した場合 銀貨と時間を増やす
        # log("-", city, min(max_coin, coin+cities[city][0]), time + cities[city][1])
        heappush(hq, (time + cities[city][1], city, min(max_coin, coin+cities[city][0])))

        # 進める都市に進む
        for v, a, b in rails[city]:
            if coin < a:
                # 銀貨が足りないと移動できない
                continue
            # log("-", v, coin-a, time + b)
            heappush(hq, (time+b, v, coin-a))