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:
# -*- coding: utf-8 -*-
##################################
# University of Wisconsin-Madison
# Author: Yaqi Zhang
##################################

# standard library
import collections
import heapq
import sys
from functools import lru_cache

sys.setrecursionlimit(10**9)

Input = lambda: sys.stdin.readline().rstrip()
IntRead = lambda: int(Input())
LineRead = lambda: list(map(int, Input().split()))


INF = 10**18

def main():
    N, M, S = LineRead()
    S = min(S, 50 * 50)
    # state: start at 1, for 2 ... N
    graph = [[] for _ in range(N + 1)]
    cs = [-1]
    ds = [-1]
    for _ in range(M):
        u, v, a, b = LineRead()
        graph[u].append((v, a, b))
        graph[v].append((u, a, b))
    for _ in range(N):
        c, d = LineRead()
        cs.append(c)
        ds.append(d)
    def dijkstra(start, end):
        pq = [(0, start, S)]
        dist = {}
        dist[(start, S)] = 0
        # print("Hello")
        while pq:
            t, u, s = heapq.heappop(pq)
            # print(t, u, s)
            if u == end:
                return t
            if t < dist[u, s]:
                continue
            for v, a, b in graph[u]:
                if s >= a:
                    if (v, s - a) not in dist or dist[v, s - a] > t + b:
                        dist[v, s - a] = t + b
                        heapq.heappush(pq, (t + b, v, s - a))
            # exchange
            c = cs[u]
            d = ds[u]
            if (u, s + c) not in dist or dist[u, s + c] > t + d:
                dist[u, s + c] = t + d
                heapq.heappush(pq, (t + d, u, s + c))
    for i in range(2, N + 1):
        print(dijkstra(1, i))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# from collections import deque
from heapq import heappop, heappush
N, M, S = map(int, input().split())
G = dict([[i, []] for i in range(N)])
C = []
D = []
lm = 0
for _ in range(M):
    u, v, a, b = map(int, input().split())
    G[u-1].append((v-1, a, b))
    G[v-1].append((u-1, a, b))
    lm += a
for _ in range(N):
    c, d = map(int, input().split())
    C.append(c)
    D.append(d)

# Q = deque([(0, S, 0)])  # (time, money, v)
Q = [(0, S, 0)]  # (time, money, v)
visited = [False] * N
ans = [-1] * N
while len(Q) > 0:
    # t, m, v = Q.popleft()
    t, m, v = heappop(Q)

    if ans[v] == -1:
        ans[v] = t
        visited[v] = True

    if all(visited):
        break

    # charge
    if m < lm:
        heappush(Q, (t+D[v], m+C[v], v))
    # move
    for nv, a, b in G[v]:
        if m < a:
            continue
        heappush(Q, (t+b, m-a, nv))

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

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from heapq import heappush, heappop

N, M, S = [int(x) for x in input().split()]
UVAB = [[int(x) for x in input().split()] for i in range(M)]
CD = [[int(x) for x in input().split()] for i in range(N)]

# Never exchange for more silver than needed to traverse entire graph
maxSilver = 0
graph = defaultdict(lambda: defaultdict(tuple))
for u, v, a, b in UVAB:
    # 0-indexed
    graph[u - 1][v - 1] = (a, b)
    graph[v - 1][u - 1] = (a, b)
    maxSilver += a


def dijkstra(source, getNbr, isDest=None):
    dest = None
    dist = {}
    queue = []
    heappush(queue, (0, source))
    while queue:
        # Grab current shortest that isn't finalized yet
        minDist, minNode = heappop(queue)
        if minNode in dist:
            # Finalized with something shorter before, continue
            assert dist[minNode] <= minDist
            continue
        # Finalize the current shortest
        dist[minNode] = minDist
        # Check if it's already at the destination
        if isDest and isDest(minNode):
            dest = minNode
            break
        # Add all neighbors that still needs to be processed
        for nbr, weight in getNbr(minNode):
            if nbr not in dist:
                heappush(queue, (minDist + weight, nbr))
            else:
                assert minDist + weight >= dist[nbr]
    return dist, dest


def getNbr(node):
    index, g, s = node
    ret = []
    # Take edge
    for nbr in graph[index]:
        edgeCost, edgeTime = graph[index][nbr]
        if s - edgeCost >= 0:
            ret.append(((nbr, g, s - edgeCost), edgeTime))
    # Exchange one gold at current node
    exchangeSilver, exchangeTime = CD[index]
    # TODO: How to figure out best amount to exchange?
    if s + exchangeSilver <= maxSilver and g >= -2 * maxSilver:
        ret.append(((index, g - 1, s + exchangeSilver), exchangeTime))
    return ret


seen = set()


def isDest(node):
    seen.add(node[0])
    if len(seen) == N:
        return True
    return False


# TODO: Gold is allowed to be negative
source = (0, 0, S)  # (node index, gold, silver), mapped to current time in dist
dist, dest = dijkstra(source, getNbr, isDest)
best = {}
for (index, g, s), time in dist.items():
    if index in best:
        best[index] = min(best[index], time)
    else:
        best[index] = time

for v in range(1, N):
    print(best[v])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
##################################
# University of Wisconsin-Madison
# Author: Yaqi Zhang
##################################

# standard library
import collections
import heapq
import sys
from functools import lru_cache

sys.setrecursionlimit(10**9)

Input = lambda: sys.stdin.readline().rstrip()
IntRead = lambda: int(Input())
LineRead = lambda: list(map(int, Input().split()))


INF = 10**18

def main():
    N, M, S = LineRead()
    # state: start at 1, for 2 ... N
    graph = [[] for _ in range(N + 1)]
    cs = [-1]
    ds = [-1]
    for _ in range(M):
        u, v, a, b = LineRead()
        graph[u].append((v, a, b))
        graph[v].append((u, a, b))
    for _ in range(N):
        c, d = LineRead()
        cs.append(c)
        ds.append(d)
    def dijkstra(start, end):
        pq = [(0, start, S)]
        dist = {}
        dist[(start, S)] = 0
        # print("Hello")
        while pq:
            t, u, s = heapq.heappop(pq)
            # print(t, u, s)
            if u == end:
                return t
            if t < dist[u, s]:
                continue
            for v, a, b in graph[u]:
                if s >= a:
                    if (v, s - a) not in dist or dist[v, s - a] > t + b:
                        dist[v, s - a] = t + b
                        heapq.heappush(pq, (t + b, v, s - a))
            # exchange
            c = cs[u]
            d = ds[u]
            if (u, s + c) not in dist or dist[u, s + c] > t + d:
                dist[u, s + c] = t + d
                heapq.heappush(pq, (t + d, u, s + c))
    for i in range(2, N + 1):
        print(dijkstra(1, i))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
##################################
# University of Wisconsin-Madison
# Author: Yaqi Zhang
##################################

# standard library
import collections
import heapq
import sys
from functools import lru_cache

sys.setrecursionlimit(10**9)

Input = lambda: sys.stdin.readline().rstrip()
IntRead = lambda: int(Input())
LineRead = lambda: list(map(int, Input().split()))


INF = 10**18

def main():
    N, M, S = LineRead()
    # state: start at 1, for 2 ... N
    graph = [[] for _ in range(N + 1)]
    cs = [-1]
    ds = [-1]
    for _ in range(M):
        u, v, a, b = LineRead()
        graph[u].append((v, a, b))
        graph[v].append((u, a, b))
    for _ in range(N):
        c, d = LineRead()
        cs.append(c)
        ds.append(d)
    def dijkstra(start, end):
        pq = [(0, start, S)]
        dist = {}
        dist[(start, S)] = 0
        # print("Hello")
        while pq:
            t, u, s = heapq.heappop(pq)
            # print(t, u, s)
            if u == end:
                return t
            if (u, s) in dist and t < dist[u, s]:
                continue
            for v, a, b in graph[u]:
                if s >= a:
                    if (v, s - a) not in dist or dist[v, s - a] > t + b:
                        dist[v, s - a] = t + b
                        heapq.heappush(pq, (t + b, v, s - a))
            # exchange
            c = cs[u]
            d = ds[u]
            if (u, s + c) not in dist or dist[u, s + c] > t + d:
                dist[u, s + c] = t + d
                heapq.heappush(pq, (t + d, u, s + c))
    for i in range(2, N + 1):
        print(dijkstra(1, i))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
sysread = sys.stdin.readline
from heapq import heappop, heappush
import math
def run():
    # import sys
    # A = list(map(int, sys.stdin.readline().split()))
    # all = sys.stdin.readlines()
    #N, *A = map(int, open(0))
    #N = int(input())
    N, M, S = list(map(int, sysread().split()))
    to = [[] for _ in range(N+1)]
    for _ in range(M):
        u,m,a,b = list(map(int, sysread().split()))
        to[u].append((m,b,a))
        to[m].append((u,b,a))
    CD = [[0,0]]
    for _ in range(N):
        c,d = list(map(int, sysread().split()))
        CD.append([c,d])
    queue = []
    # (time, node, rest-coin)
    heappush(queue, (0, 1, S))

    min_times = [None for _ in range(N+1)]
    nodes = [0 for _ in range(N)]

    while nodes:
        time, node, coin = heappop(queue)
        if min_times[node] == None:
            min_times[node] = time
            del nodes[0]
        c, d = CD[node]
        for n_node, n_time, n_coin in to[node] + [(node, d, -c)]:
            if coin < n_coin:
                k = math.ceil((n_coin - coin) / c)
                n_time += k * d
                heappush(queue, (time + n_time, n_node, coin + c*k - n_coin))
            else:
                heappush(queue, (time + n_time, n_node, coin - n_coin))
    for s in min_times[2:]:
        print(s)
if __name__ == "__main__":
    run()

Submission status: Time Limit Exceeded

Solution code:
from heapq import *
n, m, s = map(int, input().split())
inf = 10**18
#train_time[i][j]: i -> jに掛かる時間
train = [[] for i in range(n+1)]

for i in range(m):
    u, v, a, b = map(int, input().split())
    train[u].append((v, a, b))
    train[v].append((u, a, b))

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

queue = [(0, 1, s, set([1]), [len(i) for i in train])]
cost = [inf for i in range(n+1)]
cost[1] = 0
count = 0
while queue:
    now_t, now, now_c, visit, visit_count = heappop(queue)
    #print(now_t, now, now_c, visit, visit_count)
    visit.add(now)
    cost[now] = min(cost[now], now_t)
    visit_count[now] -= 1
    if visit_count[now] < 0:
        continue
    for next, next_c, next_t in train[now]:
        if next_c > now_c:
            for ex in visit:
                next_t_plus = ((next_c-now_c-1)//exchange[ex][0] + 1)*exchange[ex][1]
                next_c_plus = ((next_c-now_c-1)//exchange[ex][0] + 1)*exchange[ex][0]
                nx = (now_t+next_t+next_t_plus, next, now_c-next_c+next_c_plus, visit, visit_count[:])
                if nx not in queue:
                    heappush(queue, nx)
        else:
            nx = (now_t+next_t, next, now_c-next_c, visit, visit_count[:])
            if nx not in queue:
                heappush(queue, (now_t+next_t, next, now_c-next_c, visit, visit_count[:]))

for i in range(2, n+1):
    print(cost[i])

Submission status: Time Limit Exceeded

Solution code:
def Int():
    return int(input())
def Ints():
    return map(int,input().split())
def IntList():
    return list(Ints())
def IntMat(N):
    return [IntList() for i in range(N)]

N,M,S = Ints()
from collections import defaultdict
Graph  = defaultdict(list)

for i in range(M):
    u,v,a,b = Ints()
    Graph[u].append([v,a,b])
    Graph[v].append([u,a,b])

City = [0]*N
for i in range(N):
    c,d = Ints()
    City[i] = [c,d]

import heapq
visited = [-1]*(N+1)
visited[0] = 1
que = []
# [time, nowhere, money, flag, visited]
heapq.heappush(que, [0, 1, S, 0])
ans = [-1]*(N+1)
Min = [[10**16]*5001 for i in range(N+1)]
#print(Graph)
while visited != [1]*(N+1):
    #print(que)
    time, nowhere, money, flag = heapq.heappop(que)
    #print(time, nowhere, money, flag)
    #route[nowhere] = 1
    Min[nowhere][min(money,5000)] = min(Min[nowhere][min(money,5000)], time)
    if visited[nowhere] == -1:
        visited[nowhere] = 1
        ans[nowhere] = time
    if flag == 0:
        c,d = City[nowhere-1]
        if money >= 5000:
            heapq.heappush(que, [time+d, nowhere, money+c, 1])
        else:
            heapq.heappush(que, [time+d, nowhere, money+c, 0])
    for (to,a,b) in Graph[nowhere]:
        #if not to in route:
        if money-a >= 0:
            if Min[to][min(money-a,5000)] > time+b:
                heapq.heappush(que, [time+b, to, money-a, flag])

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

Submission status: Time Limit Exceeded

Solution code:
import heapq
import os
from collections import defaultdict

import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353


N, M, S = list(map(int, sys.stdin.buffer.readline().split()))
UVAB = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(M)]
CD = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(N)]
CD = [(0, 0)] + CD

graph = [[] for _ in range(N + 1)]
for u, v, a, b in UVAB:
    graph[u].append((a, b, v))
    graph[v].append((a, b, u))
for vs in graph:
    vs.sort()

mada = set(list(range(2, N + 1)))
heap = [(0, 1, S)]
ans = [INF] * (N + 1)
ans[1] = 0
# dp[v, s]: v にお金を s 持ってる状態で来たときの最小値
dp = defaultdict(lambda: INF)
dp[1, S] = 0
while heap and mada:
    d, v, s = heapq.heappop(heap)
    if d > dp[v, s]:
        continue
    if v in mada:
        mada.remove(v)

    ans[v] = min(ans[v], d)
    for a, b, u in graph[v]:
        if s - a < 0:
            break
        if d + b < dp[u, s - a]:
            dp[u, s - a] = d + b
            heapq.heappush(heap, (d + b, u, s - a))
    c, dd = CD[v]
    for _ in range(3):
        if d + dd < dp[v, s + c]:
            dp[v, s + c] = d + dd
            heapq.heappush(heap, (d + dd, v, s + c))

print(*ans[2:], sep='\n')

Submission status: Time Limit Exceeded

Solution code:
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)]


import math

M = 50 * n + 1

dp = [[float('inf')] * M for _ in range(n)]
s = min(s, M - 1)
dp[0][s] = 0

def inc(dp, i, j):
    c, d = cd[i][0], cd[i][1]
    for jj in range(M):
        dp[i][jj] = min(dp[i][jj], dp[i][j] + max(math.ceil((jj - j) / c), 0) * d)
    return dp

dp = inc(dp, 0, s)

while True:
    flag = False

    for i in range(m):
        u1, v1, a, b = uvab[i][0] - 1, uvab[i][1] - 1, uvab[i][2], uvab[i][3]
        for (u, v) in [(u1, v1), (v1, u1)]:
            for j in range(M):
                if j + a < M:
                    tmp = dp[u][j + a] + b
                    if tmp < dp[v][j]:
                        dp[v][j] = tmp
                        flag = True

                    c, d = cd[v][0], cd[v][1]
                    for jj in range(M):
                        tmp = dp[v][j] + max(0, math.ceil((jj - j) / c)) * d
                        if tmp < dp[v][jj]:
                            dp[v][jj] = tmp
                            flag = True


    if flag == False:
        break

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

Submission status: Time Limit Exceeded

Solution code:
import heapq
N, M, S = map(int, input().split())
G = [[] for _ in range(N)]
for i 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])

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


S = min(2500, S)
# dp[node][silver] := 頂点nodeにいてsilver枚の銀貨を持っているような状況を作るために必要な最小時間
dp = [[float('inf')] * 2501 for _ in range(N)]
distances = [float('inf')] * N
distances[0] = 0
hq = []  # これまでにかかった時間がtimeで、silver枚銀貨を持っていて、頂点nodeにいる

# 頂点0について全両替バターンを試しておく
produce_silver_profit = C[0]
produce_silver_cost = D[0]
push_silver = S + produce_silver_profit
push_time = 0 + produce_silver_cost

heapq.heappush(hq, (0, S, 0))
while push_silver <= 2500:
    dp[0][push_silver] = min(dp[0][push_silver], push_time)
    heapq.heappush(hq, (push_time, push_silver, 0))
    push_silver += produce_silver_profit
    push_time += produce_silver_cost

while hq:
    time, silver, node = heapq.heappop(hq)
    for to, cost_silver, cost_time in G[node]:
        if silver < cost_silver:
            continue

        new_time = time + cost_time
        distances[to] = min(distances[to], new_time)

        produce_silver_profit = C[to]
        produce_silver_cost = D[to]

        push_silver = silver - cost_silver
        push_time = new_time
        if dp[to][max(0, min(2500, push_silver))] <= push_time:
            push_silver += produce_silver_profit
            push_time += produce_silver_cost
            continue

        heapq.heappush(hq, (push_time, push_silver, to))
        while push_silver <= 2500:
            if dp[to][push_silver] <= push_time:
                push_silver += produce_silver_profit
                push_time += produce_silver_cost
                continue

            dp[to][push_silver] = push_time
            heapq.heappush(hq, (push_time, push_silver, to))
            push_silver += produce_silver_profit
            push_time += produce_silver_cost

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def dijkstra(nodes: list, src: int) -> list:
    from heapq import heappush, heappop

    N = len(nodes)
    MAX = 50**2
    res = list2d(N, MAX+1, INF)
    que = [(0, src, min(S, MAX))]
    res[src][min(S, MAX)] = 0
    while que:
        dist, u, coin  = heappop(que)
        if res[u][coin] < dist:
            continue
        while 1:
            for v, a, b in nodes[u]:
                if coin - a >= 0 and dist + b < res[v][coin-a]:
                    res[v][coin-a] = dist + b
                    heappush(que, (dist+b, v, coin-a))
            if coin == MAX:
                break            
            dist += D[u]
            coin = min(coin+C[u], MAX)
    return res

N, M, S = MAP()
nodes = [[] for i in range(N)]
for _ in range(M):
    u, v, a, b = MAP()
    u -= 1; v -= 1
    nodes[u].append((v, a, b))
    nodes[v].append((u, a, b))
C = [0] * N
D = [0] * N
for i in range(N):
    c, d = MAP()
    C[i] = c
    D[i] = d

res = dijkstra(nodes, 0)
for i in range(1, N):
    print(min(res[i]))

Submission status: Time Limit Exceeded

Solution code:
import heapq
import os
from collections import defaultdict

import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353


N, M, S = list(map(int, sys.stdin.buffer.readline().split()))
UVAB = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(M)]
CD = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(N)]
CD = [(0, 0)] + CD

graph = [[] for _ in range(N + 1)]
for u, v, a, b in UVAB:
    graph[u].append((a, b, v))
    graph[v].append((a, b, u))
for vs in graph:
    vs.sort()

mada = set(list(range(2, N + 1)))
heap = [(0, 1, S)]
ans = [INF] * (N + 1)
ans[1] = 0
# dp[v, s]: v にお金を s 持ってる状態で来たときの最小値
dp = defaultdict(lambda: INF)
dp[1, S] = 0
while heap and mada:
    d, v, s = heapq.heappop(heap)
    if d > dp[v, s]:
        continue
    if v in mada:
        mada.remove(v)

    ans[v] = min(ans[v], d)
    for a, b, u in graph[v]:
        if s - a < 0:
            break
        if d + b < dp[u, s - a]:
            dp[u, s - a] = d + b
            heapq.heappush(heap, (d + b, u, s - a))
    c, dd = CD[v]
    if d + dd < dp[v, s + c]:
        dp[v, s + c] = d + dd
        heapq.heappush(heap, (d + dd, v, s + c))

print(*ans[2:], sep='\n')

Submission status: Time Limit Exceeded

Solution code:
import heapq
import os
from collections import defaultdict

import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353


N, M, S = list(map(int, sys.stdin.buffer.readline().split()))
UVAB = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(M)]
CD = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(N)]
CD = [(0, 0)] + CD

graph = [[] for _ in range(N + 1)]
for u, v, a, b in UVAB:
    graph[u].append((a, b, v))
    graph[v].append((a, b, u))
for vs in graph:
    vs.sort()

mada = set(list(range(2, N + 1)))
heap = [(0, 1, S)]
# dp[v, s]: v にお金を s 持ってる状態で来たときの最小値
dp = defaultdict(lambda: INF)
dp[1, S] = 0
while heap and mada:
    d, v, s = heapq.heappop(heap)
    if d > dp[v, s]:
        continue
    if v in mada:
        mada.remove(v)
    for a, b, u in graph[v]:
        if s - a < 0:
            break
        if d + b < dp[u, s - a]:
            dp[u, s - a] = d + b
            heapq.heappush(heap, (d + b, u, s - a))
    c, dd = CD[v]
    if d + dd < dp[v, s + c]:
        dp[v, s + c] = d + dd
        heapq.heappush(heap, (d + dd, v, s + c))

ans = [INF] * (N + 1)
ans[1] = 0
for (v, s), d in dp.items():
    ans[v] = min(ans[v], d)
print(*ans[2:], sep='\n')

Submission status: Time Limit Exceeded

Solution code:
import heapq
def Dijkstra(edge,start):
    d = [float('inf')]*n
    d[start] = 0
    pq = [(0,start)]
    heapq.heapify(pq)
    while pq:
        dist,p = heapq.heappop(pq)
        for to,cost in edge[p].items():
            if d[to] <= dist + cost:continue
            d[to] = dist + cost
            heapq.heappush(pq, (d[to], to))
    return d

def Dijkstra(start):
    inf = float('inf')
    d = [[inf]*(A+1) for _ in range(n)]
    d[start][min(s,A)] = 0
    pq = [(0,start,min(s,A))]
    heapq.heapify(pq)
    while pq:
        dist,p,money = heapq.heappop(pq)
        while True:
            if money >= A:
                money = A
            for to,(cost,time) in path[p].items():
                if money < cost or d[to][money - cost] <= dist + time:continue
                d[to][money - cost] = dist + time
                heapq.heappush(pq, (d[to][money - cost],to,money - cost))
            if money == A:break
            money += C[p]
            dist += D[p]
        for to in path[p].keys():
            m = inf
            for i in range(A+1)[::-1]:
                m = min(m,d[to][i])
                d[to][i] = m
    return d

n,m,s = map(int,input().split())
path = [{} for _ in range(n)]
A = 0
for i in range(m):
    u,v,a,b = map(int,input().split())
    A += a
    u -= 1
    v -= 1
    path[u][v] = (a,b)
    path[v][u] = (a,b)
A *= 2
C = [0]*n
D = [0]*n
for i in range(n):
    C[i],D[i] = map(int,input().split())
ans = Dijkstra(0)
for a in ans[1:]:
    print(min(a))

Submission status: Time Limit Exceeded

Solution code:
def main():
    import heapq
    inf = 10**16
    n, m, s = map(int, input().split())
    uvab = [list(map(int, input().split())) for _ in [0]*m]
    cd = [list(map(int, input().split())) for _ in [0]*n]
    g = [[] for _ in [0]*n]
    [g[a-1].append([b-1, c, d]) for a, b, c, d in uvab]
    [g[b-1].append([a-1, c, d]) for a, b, c, d in uvab]
    vertex = [[inf]*4001 for _ in [0]*n]
    h = [(0, 0, min(s, 4000))]  # 時刻、位置、所持金
    heapq.heapify(h)
    while h:
        t, p, money = heapq.heappop(h)
        if vertex[p][money] != inf:
            continue
        vertex[p][money] = t
        newmoney = min(money+cd[p][0], 4000)
        if vertex[p][newmoney] == inf:
            heapq.heappush(h, (t+cd[p][1], p, newmoney))
        for a, b, c in g[p]:  # 行き先、運賃、時間
            if money < b:
                continue
            if vertex[a][money-b] != inf:
                continue
            heapq.heappush(h, (t+c, a, money-b))
    for i in vertex[1:]:
        print(min(i))


main()

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,m,s = LI()
    v = [[] for i in range(n)]
    M = 0
    for _ in range(m):
        x,y,a,b = LI()
        x -= 1
        y -= 1
        v[x].append((y,a,b))
        v[y].append((x,a,b))
        M += a
    g = LIR(n)
    d = defaultdict(lambda : float("inf"))
    d[(0,s)] = 0
    ans = [float("inf")]*n
    q = [(0,-s,0)]
    k = 0
    f = [0]*n
    f[0] = -s
    while q:
        dx,s,x = heappop(q)
        if f[x] < s:
            continue
        f[x] = s
        if ans[x] == float("inf"):
            k += 1
            ans[x] = dx
            if k >= n:
                break
        c,e = g[x]
        for y,a,b in v[x]:
            if a+s > 0:
                continue
            nd = dx+b
            ns = s+a
            if nd < d[(y,ns)]:
                d[(y,ns)] = nd
                heappush(q,(nd,ns,y))
        s -= c
        dx += e
        while M+s >= 0:
            for y,a,b in v[x]:
                if a+s > 0:
                    continue
                nd = dx+b
                ns = s+a
                if nd < d[(y,ns)]:
                    d[(y,ns)] = nd
                    heappush(q,(nd,ns,y))
            s -= c
            dx += e
    for i in ans[1:]:
        print(i)
    return

#Solve
if __name__ == "__main__":
    solve()