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

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

def main():
    N,M,S = map(int,input().split())
    INF = 10**10
    
    cost = [[INF]*N for _ in range(N)]
    dist = [[INF]*N for _ in range(N)]
    exch = [[0]*2 for _ in range(N)]
    
    for _ in range(M):
        a,b,c,d = map(int,input().split())
        cost[a-1][b-1] = c
        cost[b-1][a-1] = c
        dist[a-1][b-1] = d
        dist[b-1][a-1] = d
        
    for i in range(N):
        e,f = map(int,input().split())
        exch[i][0] = e
        exch[i][1] = f
        
    for i in range(N):
        cost[i][i] = 0
        dist[i][i] = 0
        
    _cost = copy.deepcopy(cost)
    _dist = copy.deepcopy(dist)
    time = [[0]*N for _ in range(N)]
    _time = copy.deepcopy(time)
        
    for i in range(N):
        for j in range(N):
            for k in range(N):
                if dist[j][k] > dist[j][i] + dist[i][k]:
                    dist[j][k] = dist[j][i] + dist[i][k]
                    cost[j][k] = cost[j][i] + cost[i][k]
    
    for i in range(1,N):
        time[0][i] = (-(-max(0,cost[0][i]-S)//exch[0][0]))*exch[0][1]+dist[0][i]
        
    for i in range(1,N):
        for j in range(N):
            if i == j:
                continue
            time[i][j] = (-(-cost[i][j]//exch[i][0]))*exch[i][1]+dist[i][j]
    
    for i in range(N):
        for j in range(N):
            for k in range(N):
                if time[j][k] > time[j][i] + time[i][k]:
                    time[j][k] = time[j][i] + time[i][k]
    
    # _________________________________________________________________________
    for i in range(N):
        for j in range(N):
            for k in range(N):
                if _cost[j][k] > _cost[j][i] + _cost[i][k]:
                    _dist[j][k] = _dist[j][i] + _dist[i][k]
                    _cost[j][k] = _cost[j][i] + _cost[i][k]
    
    for i in range(1,N):
        _time[0][i] = (-(-max(0,_cost[0][i]-S)//exch[0][0]))*exch[0][1]+_dist[0][i]
        
    for i in range(1,N):
        for j in range(N):
            if i == j:
                continue
            _time[i][j] = (-(-_cost[i][j]//exch[i][0]))*exch[i][1]+_dist[i][j]
    
    for i in range(N):
        for j in range(N):
            for k in range(N):
                if _time[j][k] > _time[j][i] + _time[i][k]:
                    _time[j][k] = _time[j][i] + _time[i][k]
    
    for i in range(1,N):
        print(min(time[0][i],_time[0][i]))
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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 and count <= 10000:
    now_t, now, now_c, visit, visit_count = heappop(queue)
    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 += ((next_c-now_c-1)//exchange[ex][0] + 1)*exchange[ex][1]
                next_c -= ((next_c-now_c-1)//exchange[ex][0] + 1)*exchange[ex][0]
                heappush(queue, (now_t+next_t, next, now_c-next_c, visit, visit_count))
        else:
            heappush(queue, (now_t+next_t, next, now_c-next_c, visit, visit_count))

print(cost)

Submission status: Wrong Answer

Solution code:
def dijkstra(N, s, E):
    import heapq
    Ret = [[10**12, 10**12]]*N
    Ret[s] = [0,0]
    C = [False]*N
    q = [(0,0,s)]
    while q:
        d, w, t = heapq.heappop(q)
        if C[t]:
            continue
        C[t] = True
        Ret[t] = [d,w]
        for v, a, b in E[t]:
            if C[v]:
                continue
            if d+b < Ret[v][0]:
                Ret[v] = [d+b, w+a]
                heapq.heappush(q, (d+b,w+a,v))
            elif d+b == Ret[v][0]:
                if w+a < Ret[v][1]:
                    Ret[v][1] = w+a
                    heapq.heappush(q, (d+b,w+a,v))
    return Ret
                


def main():
    import heapq
    N, M, S = map( int, input().split())
    E = [[] for _ in range(N)]
    for _ in range(M):
        u,v,a,b = map( int, input().split())
        u, v = u-1, v-1
        E[u].append((v,a,b))
        E[v].append((u,a,b))
    CD = [ tuple( map( int, input().split())) for _ in range(N)]
    # print(dijkstra(N, 1, E))
    q = [(0, S, 0)]
    ANS = [10**12]*N
    F = [False]*N
    while q:
        t, s, v = heapq.heappop(q)
        if F[v]:
            continue
        F[v] = True
        ANS[v] = t
        Dij = dijkstra(N, v, E)
        c, d = CD[v]
        for i in range(N):
            e, m = Dij[i]
            if m <= s:
                heapq.heappush(q, (t+e, s-m, i))
            else:
                # print(v,i, Dij[i])
                n = (m-s+c-1)//c
                heapq.heappush(q, (t+e+n*d, s+c*n-m, i))

    print("\n".join( map( str, ANS[1:])))
        
    
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque

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

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

queue = deque((N - 1, ))
max_fares = [None] * N
max_fares[N - 1] = 0
while queue:
	cur = queue.pop()
	fare = max_fares[cur]
	for n, a, b in graph[cur]:
		n_fare = fare + a
		if max_fares[n] == None or max_fares[n] > n_fare:
			max_fares[n] = n_fare
			queue.append(n)

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

queue = deque(((0, 0, S),))

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

while queue:
	cur, time, money = queue.popleft()
	count, d_time = exchanges[cur]
	if cur == N - 1:
		continue
	for n, a, b in graph[cur]:
		n_money = money - a
		n_time = time + b
		states = state_table[n]
		max_fare = max_fares[n] + 100
		while n_money <= max_fare:
			if n_money >= 0:
				if states[n_money] == None or states[n_money] > n_time:
					states[n_money] = n_time
					queue.append((n, n_time, n_money))
			n_money += count
			n_time += d_time

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

Submission status: Wrong Answer

Solution code:
import sys
from heapq import heapify, heappop, heappush

def solve():
    input = sys.stdin.readline
    N, M, S = map(int, input().split())
    Edge = [[] for _ in range(N)] #time, nextnode, cost
    for _ in range(M):
        u, v, a, b = map(int, input().split())
        Edge[u-1].append((b, v-1, a))
        Edge[v-1].append((b, u-1, a))
    exchange = [None] * N #c枚, Dmin
    for i in range(N):
        exchange[i] = [int(c) for c in input().split()]
    Ans = [-1] * N
    q = []
    heapify(q)
    heappush(q, (0, 0, S, 0, [0] * N)) #currentTime, node, moneyLeft, visited(bit)
    visitCount = 0
    while q:
        cT, nn, mL, v, rep = heappop(q)
        if Ans[nn] == -1: 
            Ans[nn] = cT
            visitCount += 1
            #print(Ans)
            if visitCount == N: break
        if visitCount < rep[nn]: continue
        rep[nn] += 1
        for time, nextnode, paycost in Edge[nn]:
            tv = v | (1 << nn)
            if mL >= paycost: heappush(q, (cT + time, nextnode, mL - paycost, tv, rep))
            else:
                toAdd = paycost - mL
                addS = 0
                minExchangeTime = 10 ** 20
                for i in range(N):
                    if tv & (1 << i) == (1 << i):
                        c, d = exchange[i]
                        gold = (toAdd - 1) // c + 1
                        if gold * d < minExchangeTime:
                            minExchangeTime = gold * d
                            addS = gold * c
                        elif gold * d == minExchangeTime:
                            if addS < gold * c: addS = gold * c
                heappush(q, (cT + time + minExchangeTime, nextnode, mL + addS - paycost, tv, rep))

    print("\n".join(map(str, Ans[1:])))

    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
MOD = 10 ** 9 + 7
INF = 10 ** 10
import sys
sys.setrecursionlimit(100000000)
dy = (-1,0,1,0)
dx = (0,1,0,-1)
from collections import deque

def main():
    n,m,s = map(int,input().split())
    G = [[] for _ in range(n)]
    for _ in range(m):
        u,v,a,b = map(int,input().split())
        u -= 1
        v -= 1
        G[u].append((v,a,b))
        G[v].append((u,a,b))
    
    Silver = [tuple(map(int,input().split())) for _ in range(n)]
    MAXS = 2600
    dp = [[INF]* (MAXS+1) for _ in range(n)]
    for i in range(min(s + 1,MAXS)):
        dp[0][i] = 0
    c,d = Silver[0]
    for i in range(min(s + 1,MAXS),MAXS):
        dp[0][i] = d*((i - s + c - 1)//c)
    
    q = deque([0])
    while q:
        i = q.popleft()
        c,d = Silver[i]
        for e,a,b in G[i]:
            flag = False
            for s in range(MAXS - 1,-1,-1):
                if s - a >= 0:
                    if dp[e][s - a] > dp[i][s] + b:
                        dp[e][s - a] = dp[i][s] + b
                        flag = True
                else:
                    k = (a - s + c - 1)//c
                    while s - a + k*c <= MAXS:
                        if dp[e][s - a + k*c] > dp[i][s] + b + k*d:
                            dp[e][s - a + k*c] = dp[i][s] + b + k*d
                            flag = True
                        k += 1
            if flag:
                q.append(e)
    #print(dp)
    for i in range(1,n):
        ans = min(dp[i])
        print(ans)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque

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

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

queue = deque((N - 1, ))
max_fares = [None] * N
max_fares[N - 1] = 0
while queue:
	cur = queue.pop()
	fare = max_fares[cur]
	for n, a, b in graph[cur]:
		n_fare = fare + a
		if max_fares[n] == None or max_fares[n] > n_fare:
			max_fares[n] = n_fare
			queue.append(n)

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

queue = deque(((0, 0, S),))

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

while queue:
	cur, time, money = queue.popleft()
	count, d_time = exchanges[cur]
	if cur == N - 1:
		continue
	for n, a, b in graph[cur]:
		n_money = money - a
		n_time = time + b
		states = state_table[n]
		max_fare = max_fares[n] + 50
		while n_money <= max_fare:
			if n_money >= 0:
				if states[n_money] == None or states[n_money] > n_time:
					states[n_money] = n_time
					queue.append((n, n_time, n_money))
			n_money += count
			n_time += d_time

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

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop


def dijkstra(graph: list, n: int, v_s: int, INF: int = float('inf')) -> list:
    # graph[v_from] = [(cost, v_to), ...]
    dist = [INF] * n

    dist[v_s] = 0
    heap = [(0, v_s)]  # heap = [(dist[v], v), ...]
    while heap:
        dist2v, v_from = heappop(heap)
        if dist[v_from] < dist2v:
            continue
        for cost, v_to in graph[v_from]:
            dist_cand = dist2v + cost
            if dist_cand < dist[v_to]:
                dist[v_to] = dist_cand
                heappush(heap, (dist[v_to], v_to))
    return dist


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

MAX_SILVER = 5005
n2 = MAX_SILVER * n
graph = [[] for _ in range(n2)]
for _ in range(m):
    u, v, a, b = map(int, input().split())
    u -= 1
    v -= 1
    for k in range(a, MAX_SILVER):
        graph[u * MAX_SILVER + k].append((b, v * MAX_SILVER + k - a))
        graph[v * MAX_SILVER + k].append((b, u * MAX_SILVER + k - a))
for i in range(n):
    c, d = map(int, input().split())
    for k in range(MAX_SILVER - 1):
        graph[i * MAX_SILVER + k].append(
            (d, i * MAX_SILVER + min(k + c, MAX_SILVER - 1)))

dist = dijkstra(graph, n2, 0 + min(s, MAX_SILVER - 1))

for i in range(1, n):
    ans_i = 10**12
    for k in range(MAX_SILVER):
        ans_i = min(ans_i, dist[i * MAX_SILVER + k])
    print(ans_i)

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop


def dijkstra(graph: list, n: int, v_s: int, INF: int = float('inf')) -> list:
    # graph[v_from] = [(cost, v_to), ...]
    dist = [INF] * n

    dist[v_s] = 0
    heap = [(0, v_s)]  # heap = [(dist[v], v), ...]
    while heap:
        dist2v, v_from = heappop(heap)
        if dist[v_from] < dist2v:
            continue
        for cost, v_to in graph[v_from]:
            dist_cand = dist2v + cost
            if dist_cand < dist[v_to]:
                dist[v_to] = dist_cand
                heappush(heap, (dist[v_to], v_to))
    return dist


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

MAX_SILVER = 5001
n2 = MAX_SILVER * n
graph = [[] for _ in range(n2)]
for _ in range(m):
    u, v, a, b = map(int, input().split())
    u -= 1
    v -= 1
    for k in range(a, MAX_SILVER):
        graph[u * MAX_SILVER + k].append((b, v * MAX_SILVER + k - a))
        graph[v * MAX_SILVER + k].append((b, u * MAX_SILVER + k - a))
for i in range(n):
    c, d = map(int, input().split())
    for k in range(MAX_SILVER - 1):
        graph[i * MAX_SILVER + k].append(
            (d, i * MAX_SILVER + min(k + c, MAX_SILVER - 1)))

dist = dijkstra(graph, n2, 0 + min(s, MAX_SILVER - 1))

for i in range(1, n):
    ans_i = 10**12
    for k in range(MAX_SILVER):
        ans_i = min(ans_i, dist[i * MAX_SILVER + k])
    print(ans_i)

Submission status: Wrong Answer

Solution code:
import sys
from heapq import heapify, heappop, heappush

def solve():
    input = sys.stdin.readline
    N, M, S = map(int, input().split())
    Edge = [[] for _ in range(N)] #time, nextnode, cost
    for _ in range(M):
        u, v, a, b = map(int, input().split())
        Edge[u-1].append((b, v-1, a))
        Edge[v-1].append((b, u-1, a))
    exchange = [None] * N #c枚, Dmin
    for i in range(N):
        exchange[i] = [int(c) for c in input().split()]
    money = [0] * N
    Ans = [-1] * N
    q = []
    heapify(q)
    heappush(q, (0, 0, S, 1)) #currentTime, node, moneyLeft, visited(bit)
    while q:
        cT, nn, mL, v = heappop(q)
        if Ans[nn] == -1: 
            Ans[nn] = cT
            if -1 not in Ans: break
        for time, nextnode, paycost in Edge[nn]:
            tv = v | (1 << nn)
            if mL >= paycost: heappush(q, (cT + time, nextnode, mL - paycost, tv))
            else:
                toAdd = paycost - mL
                addS = 0
                minExchangeTime = 10 ** 20
                for i in range(N):
                    if tv & (1 << i) == (1 << i):
                        c, d = exchange[i]
                        gold = (toAdd - 1) // c + 1
                        if gold * d < minExchangeTime:
                            minExchangeTime = gold * d
                            addS = gold * c
                heappush(q, (cT + time + minExchangeTime, nextnode, mL + addS - paycost, tv))

    print("\n".join(map(str, Ans[1:])))

    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
import heapq


def inpl():
    return list(map(int, input().split()))


N, M, S = inpl()
A = 50  # max A
S = min(S, M * A)

lines = [[] for _ in range(N * (M * A + 1))]
for _ in range(M):
    in_s, in_t, cost, time = inpl()
    in_s -= 1
    in_t -= 1

    for n in range(cost, M * A + 1):
        s = in_s + n * N
        t = in_t + (n - cost) * N
        lines[s].append((t, time))

        s = in_s + (n - cost) * N
        t = in_t + n * N
        lines[t].append((s, time))


for i in range(N):
    cost, time = inpl()
    for n in range(0, M * A + 1):
        s = i + n * N
        if n + cost > M * A:
            t = i + (M * A) * N
        else:
            t = i + (n + cost) * N
        lines[s].append((t, time))


INF = 10**20


def dijkstra(N, S):
    weight = [INF] * N
    weight[S] = 0
    q = [[0, S]]
    heapq.heapify(q)
    while q:
        w0, s = heapq.heappop(q)
        for t, w in lines[s]:
            w += w0
            if weight[t] > w:
                heapq.heappush(q, [w, t])
                weight[t] = w

    return weight


weight = dijkstra(N * (M * A + 1), 0 + S * N)

print("\n".join(map(str, weight[1:N])))

Submission status: Wrong Answer

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

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

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

import heapq

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

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

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

Submission status: Wrong Answer

Solution code:
import sys

stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

n, m, s = nm()
N = n * 3001
G = [list() for _ in range(N)]
for _ in range(m):
    u, v, a, b = nm()
    u -= 1; v -= 1
    for j in range(0, N, n):
        if v + j - a * n >= 0:
            G[u + j].append((v + j - a * n, b))
        if u + j - a * n >= 0:
            G[v + j].append((u + j - a * n, b))
for u in range(n):
    c, d = nm()
    for j in range(0, N, n):
        G[u + j].append((min(u + j + c * n, u + N - n), d))

import heapq as hq

def dijkstra(G, s, t=None):
    """
    G[v] = [(x1, c1), (x2, c2), ...]
    """
    dist = [10**12]*len(G)
    dist[s] = 0
    q = [(0, s)]
    while q:
        d, v = hq.heappop(q)
        if d > dist[v]: continue
        for x, c in G[v]:
            if dist[x] > d + c:
                dist[x] = d + c
                hq.heappush(q, (d + c, x))
    if t is None:
        return dist
    else:
        return dist[t]

dist = dijkstra(G, min(s, 3000) * n)
for i in range(1, n):
    print(min(dist[i::n]))

Submission status: Wrong Answer

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

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

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

import heapq

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

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

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

Submission status: Wrong Answer

Solution code:
import sys

stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

n, m, s = nm()
N = n * 3001
G = [list() for _ in range(N)]
for _ in range(m):
    u, v, a, b = nm()
    u -= 1; v -= 1
    for j in range(0, N, n):
        if v + j - a * n > 0:
            G[u + j].append((v + j - a * n, b))
        if u + j - a * n > 0:
            G[v + j].append((u + j - a * n, b))
for u in range(n):
    c, d = nm()
    for j in range(0, N, n):
        G[u + j].append((min(u + j + c * n, u + N - n), d))

import heapq as hq

def dijkstra(G, s, t=None):
    """
    G[v] = [(x1, c1), (x2, c2), ...]
    """
    dist = [10**12]*len(G)
    dist[s] = 0
    q = [(0, s)]
    while q:
        d, v = hq.heappop(q)
        if d > dist[v]: continue
        for x, c in G[v]:
            if dist[x] > d + c:
                dist[x] = d + c
                hq.heappush(q, (d + c, x))
    if t is None:
        return dist
    else:
        return dist[t]

dist = dijkstra(G, min(s, 3000) * n)
for i in range(1, n):
    print(min(dist[i::n]))

Submission status: Time Limit Exceeded

Solution code:
import heapq

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

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

Q = []
heapq.heappush(Q, (0, 0, S)) # 今の時間、場所、持っているお金
Ans = [-1] * N
Ans[0] = 0
while -1 in Ans:
    time, where, money = heapq.heappop(Q)
    if Ans[where] == -1:
        Ans[where] = time
    for nex, cost, take in Map[where]:
        if cost > money:
            continue
        heapq.heappush(Q, (time + take, nex, money - cost))
    heapq.heappush(Q, (time + Exchange[where][1], where, money + Exchange[where][0]))


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

Submission status: Time Limit Exceeded

Solution code:
import heapq

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

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

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

Submission status: Time Limit Exceeded

Solution code:
import heapq

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

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

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