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:
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:
        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

        # log(city, coin, time)

        # ここで両替した場合 銀貨と時間を増やす
        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
            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    # これだけ持ってたらどの都市へも行ける
s = min(s, max_silver) # max_silverまでで十分

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

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

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

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

Submission status: 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(s) for s 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)


n,m,s = get_nums_l()

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

lines = list(map(lambda s: s.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:
        time, city, coin,  = heappop(hq)

        if city == t:
            print(time)
            break

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

        table[city][coin] = time

        # log(city, coin, time)

        # ここで両替した場合 銀貨と時間を増やす
        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
            heappush(hq, (time+b, v, coin-a))

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(s) for s 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)


n,m,s = get_nums_l()

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

lines = list(map(lambda s: s.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 = []
# 初期状態 今都市1, 銀貨s枚, 時間0
heappush(hq, (1, s, 0))

while hq:
    city, coin, time = heappop(hq)

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

    table[city][coin] = time

    # log(city, coin, time)

    # ここで両替した場合 銀貨と時間を増やす
    heappush(hq, (city, min(max_coin, coin+cities[city][0]), time + cities[city][1]))
    # x = coin
    # y = time
    # while x < max_coin:
    #     heappush(hq, (city, min(max_coin, x+cities[city][0]), y + cities[city][1]))
    #     x += cities[city][0]
    #     y += cities[city][1]

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

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

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)

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s 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)


n,m,s = get_nums_l()

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

lines = list(map(lambda s: s.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 = []
    # 初期状態 今都市1, 銀貨s枚, 時間0
    heappush(hq, (1, s, 0))

    while hq:
        city, coin, time = heappop(hq)

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

        table[city][coin] = time

        # log(city, coin, time)

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

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

    print(min(table[t]))

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    # これだけ持ってたらどの都市へも行ける
s = min(s, max_silver) # max_silverまでで十分

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

# (都市,所有銀貨)を頂点とする最短経路問題
# Dijkstra
dist = {(1, s): 0}  # 開始頂点のみ距離0
queue = [(0, 1, s)]

dmin = {u: float('inf') for u in range(1, n+1)} # dmin[u] = min(dist[(u, si)]
dmin[1] = 0

while len(queue) > 0:
    di, u, si = heapq.heappop(queue)
    # 無効なデータ
    if (u, si) in dist and di > dist[(u, si)]:
        continue
    dmin[u] = min(dmin[u], di)
    for v, a, b in adj[u]:
        if si < a:
            continue
        xsi = si - a
        if (v, xsi) not in dist or \
            dist[(v, xsi)] > di + b:
            dist[(v, xsi)] = di + b
            heapq.heappush(queue, (di + b, v, xsi))
    c, d = exch[u]
    xsi = min(si + c, max_silver)
    if (u, xsi) not in dist or \
        dist[(u, xsi)] > di + d:
        dist[(u, xsi)] = di + d
        heapq.heappush(queue, (di + d, u, xsi))

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

Submission status: 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    # これだけ持ってたらどの都市へも行ける
s = min(s, max_silver) # max_silverまでで十分

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

# (都市,所有銀貨)を頂点とする最短経路問題
# Dijkstra
dist = {(1, s): 0}  # 開始頂点のみ距離0
queue = [(0, 1, s)]

while len(queue) > 0:
    di, u, si = heapq.heappop(queue)
    # 無効なデータ
    if (u, si) in dist and di > dist[(u, si)]:
        continue
    for v, a, b in adj[u]:
        if si < a:
            continue
        xsi = si - a
        if (v, xsi) not in dist or \
            dist[(v, xsi)] > di + b:
            dist[(v, xsi)] = di + b
            heapq.heappush(queue, (di + b, v, xsi))
    c, d = exch[u]
    xsi = min(si + c, max_silver)
    if (u, xsi) not in dist or \
        dist[(u, xsi)] > di + d:
        dist[(u, xsi)] = di + d
        heapq.heappush(queue, (di + d, u, xsi))

for u in range(2, n+1):
    x = min(dist[(u, si)] for si in range(0, max_silver+1) if (u, si) in dist)
    print(x)

Submission status: Time Limit Exceeded

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

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import math
from collections import deque

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

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

C_D_list = [[int(_) for _ in input().split()] for i in range(N)]

def get_arrival_time(start_city, goal_city, start_time, silver_coin):
    min_arrival_time = None
    pass_city_deque = deque()
    passed_binary = 0
    for i_city in city_tree[start_city]:
        next_city, total_cost, total_time = i_city
        passed_binary = 1 << next_city
        pass_city_deque.append([next_city,total_cost,total_time,passed_binary])

    while len(pass_city_deque) > 0:
        now_city,total_cost,total_time,passed_binary=pass_city_deque.popleft()

        if now_city == goal_city:
            now_silver_coin = silver_coin - total_cost
            exchange_coin, exchange_time = C_D_list[start_city]
            exchange_num = math.ceil((total_cost - silver_coin) / exchange_coin)
            if exchange_num > 0:
                total_time += exchange_time * exchange_num
                now_silver_coin += exchange_coin * exchange_num

            if min_arrival_time is None:
                min_arrival_time = total_time + start_time
            else:
                min_arrival_time = min(min_arrival_time, total_time+start_time)
            continue

        for i_city in city_tree[now_city]:
            next_city, next_cost, next_time = i_city
            if passed_binary & (1 << next_city):
                continue

            next_total_cost = total_cost + next_cost
            next_total_time = total_time + next_time
            next_passed_binary = passed_binary + (1 << next_city)
            pass_city_deque.append( \
              [next_city, next_total_cost, next_total_time, next_passed_binary])
    return min_arrival_time, now_silver_coin

arrival_time_coin = [-1] * N
arrival_time_coin[0] = [0, 0]
start_city, start_time = 0, 0
for i_goal_city in range(1, N):
    arrival_time_coin[i_goal_city] = \
                  list(get_arrival_time(start_city, i_goal_city, start_time, S))

start_goal_deque = deque()
for i_start_city in range(1, N):
    for j_goal_city in range(1, N):
        if i_start_city == j_goal_city:
            continue
        
        now_time, now_coin = arrival_time_coin[i_start_city]
        start_goal_deque.append([i_start_city, j_goal_city, now_time, now_coin])

while len(start_goal_deque) > 0:
    start_city, goal_city, now_time, now_coin = start_goal_deque.popleft()
    arrival_time, arrival_coin = \
                     get_arrival_time(start_city, goal_city, now_time, now_coin)

    if arrival_time_coin[goal_city][0] > arrival_time:
        arrival_time_coin[goal_city] = [arrival_time, arrival_coin]
        for next_goal_city in range(1, N):
            if goal_city == next_goal_city:
                continue
            start_goal_deque.append( \
                        [goal_city, next_goal_city, arrival_time, arrival_coin])

for i_time, _ in arrival_time_coin[1:]:
    print(i_time)

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from heapq import heappush, heappop

N,M,S = map(int,readline().split())
ABC = [list(map(int,readline().split())) for _ in range(M)]
m = map(int,read().split())
CD = list(zip(m,m))

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

def f(p):
  INF = 10 ** 18
  qq = 2452
  dist = [[INF] * qq for _ in range(N)]
  dist[0][min(qq-1,S)] = 0
  q = [(0,min(qq-1,S),0)]
  while q:
      st,ss,v = heappop(q) # 総時間、銀貨、今いる頂点
      if dist[v][ss] < st:
        continue
      if v == p:
        break
      c,d = CD[v]
      # 銀貨の購入
      if ss < qq-1:
          ns = min(ss + c, qq-1)
          nt = st + d
          if dist[v][ns] > nt:
              dist[v][ns] = nt
              heappush(q,(nt,ns,v))
      # 移動
      for nex,g,tt in graph[v]:
          if ss-g < 0:
              continue
          dt = st + tt
          if dist[nex][ss-g] <= dt:
              continue
          dist[nex][ss-g] = dt
          heappush(q,(dt,ss-g,nex))
  return st
      
for i in range(1,N):
  answer = f(i)
  print(answer)

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from heapq import heappush, heappop

N,M,S = map(int,readline().split())
ABC = [list(map(int,readline().split())) for _ in range(M)]
m = map(int,read().split())
CD = list(zip(m,m))

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

def f(p):
  INF = 10 ** 18
  ans = INF
  qq = 2500
  dist = [[INF] * qq for _ in range(N)]
  dist[0][min(qq-1,S)] = 0
  q = [(0,min(qq-1,S),0)]
  while q:
      st,ss,v = heappop(q) # 総時間、銀貨、今いる頂点
      if dist[v][ss] < st:
        continue
      if v == p:
        ans = st
        break
      c,d = CD[v]
      # 銀貨の購入
      if ss < qq-1:
          ns = min(ss + c, qq-1)
          nt = st + d
          if dist[v][ns] > nt:
              dist[v][ns] = nt
              heappush(q,(nt,ns,v))
      # 移動
      for nex,g,tt in graph[v]:
          if ss-g < 0:
              continue
          dt = st + tt
          if dist[nex][ss-g] <= dt:
              continue
          dist[nex][ss-g] = dt
          heappush(q,(dt,ss-g,nex))
  return ans
      
for i in range(1,N):
  answer = f(i)
  print(answer)

Submission status: Time Limit Exceeded

Solution code:
import heapq

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

for i in range(M):
    uvab[i][0] -= 1
    uvab[i][1] -= 1

railways = [[] for _ in range(N)]
max_a = 0
for u, v, a, b in uvab:
    railways[u].append((v, a, b))
    railways[v].append((u, a, b))
    max_a = max(max_a, a)
del uvab

max_silver = max_a * (N - 1)

ans = [-1] * N
d = dict()
d[(S, 0)] = 0  # silver, station
Q = [(0, S, 0)]  # time, silver, station
sum_reached = 0
reached = [False] * N

while Q:
    t, sv, st = heapq.heappop(Q)
    if not reached[st]:
        ans[st] = t
        reached[st] = True
        sum_reached += 1
        if sum_reached == N:
            break

    new_key = (sv + cd[st][0], st)
    new_value = t + cd[st][1]
    if new_key not in d or d[new_key] > new_value:
        d[new_key] = t + cd[st][1]
        heapq.heappush(Q, (new_value, *new_key))

    for dist, a, b in railways[st]:
        if sv >= a:
            new_key = (sv - a, dist)
            new_value = t + b
            if new_key not in d or d[new_key] > new_value:
                d[new_key] = new_value
                heapq.heappush(Q, (new_value, *new_key))

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

Submission status: Time Limit Exceeded

Solution code:
from heapq import heapify, heappop, heappush

DEBUG = False
INF = float('inf')
MAX_N = 50
MAX_A = 50

N, M, S = map(int, input().split())
U = []
V = []
A = []
B = []
C = []
D = []

connect = [[] for _ in range(N)]
for _ in range(M):
    u, v, a, b = map(int, input().split())
    U.append(u)
    V.append(v)
    A.append(a)
    B.append(b)
    connect[u-1].append([v-1, a, b])
    connect[v-1].append([u-1, a, b])
for _ in range(N):
    c, d = map(int, input().split())
    C.append(c)
    D.append(d)

if DEBUG:
    print("U: {}".format(U))
    print("V: {}".format(V))
    print("A: {}".format(A))
    print("B: {}".format(B))
    print("C: {}".format(C))
    print("D: {}".format(D))
    print("connect: {}".format(connect))

MAX_N = N
MAX_A = max(A)
MAX_MONEY = MAX_N * MAX_A
S = min(S, MAX_MONEY-1)

node = [INF for _ in range(MAX_MONEY * N)]
node[0] = 0

hq = []
heappush(hq, (0, S))
while hq:
    time, current_node = heappop(hq)
    if time < node[current_node]:
        node[current_node] = time
    index_city = current_node // MAX_MONEY
    money = current_node % MAX_MONEY

    for index_next_city, a, b in connect[index_city]:
        if money >= a and time+b < node[index_next_city*MAX_MONEY + money-a]:
            heappush(hq, (time+b, index_next_city*MAX_MONEY + money-a))
    if money < MAX_MONEY-1:
        heappush(hq, (time+D[index_city], min(money+C[index_city], MAX_MONEY-1)+MAX_MONEY*index_city))

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
from collections import defaultdict
def resolve():
    N, M, S = lr()
    uvab = [[] for i in range(N)]
    amax = 0
    for i in range(M):
        u, v, a, b = lr()
        uvab[u-1].append([v-1, a, b])
        uvab[v-1].append([u-1, a, b])
        amax = max(amax, a)
    cd = []
    for i in range(N):
        cd.append(lr())
    dp = defaultdict(lambda: float('inf'))
    A = amax*(N-1)
    dp[0, min(S, A)] = 0
    s = [[0, min(S, A), 0]]
    while len(s) > 0:
        s = sorted(s, key=lambda x: x[2])[::-1]
        u, i, x  = s.pop()
        if dp[u, i] != x:
            continue
        c, d = cd[u]
        ni = min(i+c, A)
        if dp[u, ni] > dp[u, i]+d:
            dp[u, ni] = dp[u, i]+d
            s.append([u, ni, dp[u, ni]])
        for vab in uvab[u]:
            v, a, b = vab
            if i >= a and i < A and dp[v, i-a] > dp[u, i] + b:
                dp[v, i-a] = dp[u, i] + b
                s.append([v, i-a, dp[v, i-a]])
            elif i == A and dp[v, i] > dp[u, i] + b:
                dp[v, i] = dp[u, i] + b
                s.append([v, i, dp[v, i]])
    for i in range(1, N):
        ans = float('inf')
        for j in range(A+1):
            ans = min(dp[i, j], ans)
        print(ans)
resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
from collections import defaultdict, deque
def resolve():
    N, M, S = lr()
    uvab = [[] for i in range(N)]
    amax = 0
    for i in range(M):
        u, v, a, b = lr()
        uvab[u-1].append([v-1, a, b])
        uvab[v-1].append([u-1, a, b])
        amax = max(amax, a)
    cd = []
    for i in range(N):
        cd.append(lr())
    dp = defaultdict(lambda: float('inf'))
    A = amax*(N-1)
    dp[0, min(S, A)] = 0
    s = deque([[0, min(S, A)]])
    while len(s) > 0:
        tu, i = s.popleft()
        for vab in uvab[tu]:
            v, a, b = vab
            if i >= a and i < A and dp[v, i-a] > dp[tu, i] + b:
                dp[v, i-a] = dp[tu, i] + b
                s.append([v, i-a])
            elif i == A and dp[v, i] > dp[tu, i] + b:
                dp[v, i] = dp[tu, i] + b
                s.append([v, i])
        c, d = cd[tu]
        t = i
        while t < A:
            nt = min(t+c, A)
            if dp[tu, nt] > dp[tu, t] + d:
                dp[tu, nt] = dp[tu, t] + d
                s.append([tu, nt])
            t = nt
    for i in range(1, N):
        ans = float('inf')
        for j in range(A+1):
            ans = min(dp[i, j], ans)
        print(ans)
resolve()