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

MAX_FARE = M * 50

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

state_table = [[None] * (max_fares[i] + 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]
		while True:
			if n_money >= 0:
				if n_money > max_fare:
					n_money = max_fare
				if states[n_money] == None or states[n_money] > n_time:
					states[n_money] = n_time
					queue.append((n, n_time, n_money))
				if n_money >= max_fare:
					break
			n_money += count
			n_time += d_time


#for i in range(N):
#	print(i, state_table[i])

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
            if visitCount == N: break
        if visitCount < rep[nn]: continue
        newrep = [rep[i] for i in range(N)]
        newrep[nn] += 1
        for time, nextnode, paycost in Edge[nn]:
            tv = (v | pow(2, nn))
            if mL >= paycost: heappush(q, (cT + time, nextnode, mL - paycost, tv, newrep))
            else:
                toAdd = paycost - mL
                addS = 0
                minExchangeTime = 10 ** 20
                for i in range(N):
                    if (tv & pow(2, i)) == pow(2, 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, newrep))

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

    return 0

if __name__ == "__main__":
    solve()

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
            if visitCount == N: break
        if visitCount + N < rep[nn]: continue
        newrep = [rep[i] for i in range(N)]
        newrep[nn] += 1
        for time, nextnode, paycost in Edge[nn]:
            tv = (v | pow(2, nn))
            if mL >= paycost: heappush(q, (cT + time, nextnode, mL - paycost, tv, newrep))
            else:
                toAdd = paycost - mL
                addS = 0
                minExchangeTime = 10 ** 20
                for i in range(N):
                    if (tv & pow(2, i)) == pow(2, 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, newrep))

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

    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
from heapq import *
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():

    inf=10**32
    n,m,s=MI()
    to=[[] for _ in range(n)]
    for _ in range(m):
        u,v,a,b=MI()
        to[u-1].append((v-1,a,b))
        to[v-1].append((u-1,a,b))
    cd=LLI(n)

    dp=[[inf]*10005 for _ in range(n)]
    hp=[]
    heappush(hp,(0,min(s,10000),0))

    while hp:
        t,g,u=heappop(hp)
        if dp[u][g]<t:continue
        #fin[u]=True
        #if sum(fin)==n:break
        c,d=cd[u]
        if g+c<10000:
            if dp[u][g + c] <= t + d: continue
            dp[u][g + c] = t + d
            heappush(hp, (t + d, g + c, u))
        else:
            if dp[u][10000] <= t + d: continue
            dp[u][10000] = t + d
            heappush(hp, (t + d, 10000, u))
        for v,a,b in to[u]:
            if g-a<0:continue
            if dp[v][g-a]<=t+b:continue
            dp[v][g - a] = t + b
            heappush(hp,(t+b,g-a,v))
    for u in range(1,n):
        print(min(dp[u]))

main()

Submission status: Wrong Answer

Solution code:
N, M, S = map(int, input().split()) #S銀貨の枚数

# U = [0]*M 
# V = [0]*M
# A = [0]*M #銀貨
# B = [0]*M #時間
train = [[] for _ in range(N)]
for i in range(M):
    u,v,a,b = map(int, input().split())
    train[u-1].append([v-1,a,b])
    train[v-1].append([u-1,a,b])

# C = [0]*N #金:銀貨
# D = [0]*N #交換時間
for i in range(N):
    c,d = map(int, input().split())
    train[i].append([i,d,c])

    

from collections import deque

ans = []
for i in range(2,N):
    d = deque()
    d.append([0,S,0]) #頂点,お金、時間

    while len(d)>0:
        v,m,t = d.popleft()
        for vertex,money,time in train[v]:
            if vertex==v:
                m += money
            elif m<money:
                continue
            else:
                m -= money
                v = vertex
            d.append([v,m,t])
        if v == i:
            ans.append(t)
            break
print(*ans, sep='\n')

Submission status: Wrong Answer

Solution code:
import copy
# スペース区切りの整数入力
N,M,S = map(int, input().split())

U=[]
V=[]
A=[]
B=[]

for i in range(M):
    u,v,a,b = map(int, input().split())
    U.append(u)
    V.append(v)
    A.append(a)
    B.append(b)

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

for pp in range(2,N+1):
    p0 = [[0,1,100,S]]
    p1 = []

    res = 999999999999999999
    while True:
        for t,p,g,s in p0:
            #g2s
            if g > 0:
                p1.append([t+D[p-1],p,g-1,s+C[p-1]])
            #move
            for i in range(M):
                if U[i] == p and A[i] <= s:
                    p1.append([t+B[i],V[i],g,s-A[i]])
                    if V[i] == pp:
                        res = min(res,t+B[i])
                if V[i] == p and A[i] <= s:
                    p1.append([t+B[i],U[i],g,s-A[i]])
                    if U[i] == pp:
                        res = min(res,t+B[i])
        p0 = []
        p0 = copy.deepcopy(p1)
        p1 = []
        ok = 0
        for t,p,g,s in p0:
            if t < res:
                ok = 1
        if ok == 0:
            break
    print(res)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

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

def print_l(l):
    print(' '.join(map(str, l)))

class Interval():
    def __init__(self, li):
        self.li = li
        self.n = len(li)
        self.sum_li = [li[0]]
        for i in range(1, self.n):
            self.sum_li.append(self.sum_li[i-1] + li[i])

    def sum(self, a, b=None):
        if b is None:
            return self.sum(0, a)

        res = self.sum_li[min(self.n-1, b-1)]
        if a > 0:
            res -= self.sum_li[a-1]
        return res

n,m,s=l_in()

uvab=[]
edges = [[] for _ in range(n)]
for _ in range(m):
    u,v,a,b = l_in()
    edges[u-1].append((v-1,a,b))
    edges[v-1].append((u-1,a,b))

cd = [l_in() for _ in range(n)]

# dp[i][g] city i で g まいの銀貨をもつための最小時間
m = 1001
dp = [[-1]*m for _ in range(n)]

from heapq import heappush,heappop
h = []

for g in range(min(s+1,m)):
    heappush(h, (0,-g,0))
 #   print(g,h,s,m)
 
while len(h) > 0:
    t,g,i = h[0]
    g = min(-g,m-1)
#    print(h)

#    g*=-1

#   print(h[0])
    heappop(h)

    if dp[i][g] != -1:
        continue

    dp[i][g] = t
    
    
    for v,a,b in edges[i]:
        if g-a >= 0:
            heappush(h,(t+b,-(g-a),v))

    c,d = cd[i]
    heappush(h,(t+d,-(g+c),i))
    


#for d in dp:
#    pass
#    print(d)


for i in range(1, n):
    res = -1
    for v,a,b in edges[i]:
        min_t = -1
        for g in range(a,m):
            t = dp[v][g]
            if t == -1:
                continue
            if min_t == -1 or min_t > t:
                min_t = t
#                print("min_t", v,g,min_t)

        if res == -1 or res > min_t+b:
            res = min_t+b

#    print(dp[i])
    for t in dp[i]:
        if t == -1:
            continue
        if res == -1  or t < res:
            res = t
            
    print(res)

Submission status: Wrong Answer

Solution code:
from collections import deque
from itertools import product
import sys

sys.setrecursionlimit(200000)
input = sys.stdin.readline


def read(INF=10**15):
    N, M, S = map(int, input().strip().split())
    A = [[-1 for j in range(N+1)] for i in range(N+1)]
    B = [[-1 for j in range(N+1)] for i in range(N+1)]
    for i in range(M):
        u, v, a, b = map(int, input().strip().split())
        A[u][v] = a
        B[u][v] = b
        A[v][u] = a
        B[v][u] = b
    C = [INF, ]
    D = [INF, ]
    for i in range(N):
        c, d =  map(int, input().strip().split())
        C.append(c)
        D.append(d)
    return N, M, S, A, B, C, D


def solve(N, M, S, A, B, C, D, INF=10**15):
    t = [[INF for j in range(N+1)] for i in range(N+1)]  # time
    c = [[INF for j in range(N+1)] for i in range(N+1)]  # cost
    for i in range(1, N+1):
        t[i][i] = 0
        c[i][i] = 0
    for i in range(1, N+1):
        for j in range(1, N+1):
            t[i][j] = B[i][j] if B[i][j] >= 0 else INF
    
    for k in range(1, N+1):
        for i in range(1, N+1):
            for j in range(1, N+1):
                if t[i][j] > t[i][k] + t[k][j]:
                    t[i][j] = t[i][k] + t[k][j]
                    c[i][j] = c[i][k] + c[k][j] + A[i][j]
    
    for i in range(2, N+1):
        print(t[1][i])

if __name__ == '__main__':
    inputs = read()
    solve(*inputs)

Submission status: Wrong Answer

Solution code:
MOD = 10 ** 9 + 7
INF = 10 ** 15
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)]
    MAXS = 100
    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))
        MAXS += a
    
    Silver = [tuple(map(int,input().split())) for _ in range(n)]
    dp = [[INF]* (MAXS+1) for _ in range(n)]
    for i in range(min(s + 1,MAXS + 1)):
        dp[0][i] = 0
    c,d = Silver[0]
    for i in range(min(s + 1,MAXS + 1),MAXS + 1):
        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):
                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:
import sys
input = sys.stdin.readline

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
    P = [pow(2,i) for i in range(51)]
    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, 1)]
    ANS = [10**12]*N
    F = [False]*N
    while q:
        t, s, v, l = heapq.heappop(q)
        s = -s
        if F[v]:
            continue
        F[v] = True
        ANS[v] = t
        Dij = dijkstra(N, v, E)
        for j in range(N):
            if l & P[j] == 0 :
                continue
            c, d = CD[j]
            for i in range(N):
                e, m = Dij[i]
                if m <= s:
                    heapq.heappush(q, (t+e, s-m, i, l |P[i]))
                else:
                    n = (m-s+c-1)//c
                    heapq.heappush(q, (t+e+n*d, s+c*n-m, i, l|P[i]))

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

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict
from math import ceil
input = sys.stdin.readline

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

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

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

# dfsで今まで訪れた箇所をsetで持っておく
# 次に行く場所がそこにあれば行かない
# 経路上の換金できる最小の時間も持っておく
def dfs(cur_num, goal, route_set, time_trade, cost, silver):
    if cur_num == goal:
        return cost, time_trade, silver
    cnt = 0
    res = INF
    final_time_trade = []
    final_silver = -INF
    for next_num in edges[cur_num].keys():
        if next_num in route_set:
            continue
        cnt += 1
        tmp_cost = edges[cur_num][next_num][1]
        tmp_s = -edges[cur_num][next_num][0]
        if silver + tmp_s < 0:
            # 銀が足りない場合の処理
            min_time = [INF, 0]
            for c, d in time_trade:
                times = ceil(-(silver + tmp_s) / c)
                if times * d < min_time[0] or (times * d == min_time[0] and times*c > min_time[1]):
                    min_time = [times*d, times*c]
            tmp_cost += min_time[0]
            tmp_s += min_time[1]
        ret = dfs(next_num, goal, route_set | {next_num}, time_trade + [cd[next_num]], cost + tmp_cost, silver + tmp_s)
        if ret[0] < res:
            res = ret[0]
            final_time_trade = ret[1]
            final_silver = ret[2]

    if cnt == 0:
        return INF, [], -INF
    else:
        return res, final_time_trade, final_silver

plus_costs = [(0, [cd[0], s])]
for i in range(1, n):
    plus_costs.append(dfs(0, i, set(), [cd[0]],0 , s))

for i in range(1, n):
    ans = plus_costs[i][0]
    for j in range(1, n):
        if i == j:
            continue
        # j経由でiまで行く
        tmp_s = plus_costs[j][2]
        tmp_ans = dfs(j, i, set(), plus_costs[j][1], plus_costs[j][0], tmp_s)[0]
        ans = min(ans, tmp_ans)
    print(ans)

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
            if visitCount == N: break
        if visitCount * N < rep[nn]: continue
        rep[nn] += 1
        for time, nextnode, paycost in Edge[nn]:
            tv = (v | pow(2, 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 & pow(2, i)) == pow(2, 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:
import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

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

def print_l(l):
    print(' '.join(map(str, l)))

class Interval():
    def __init__(self, li):
        self.li = li
        self.n = len(li)
        self.sum_li = [li[0]]
        for i in range(1, self.n):
            self.sum_li.append(self.sum_li[i-1] + li[i])

    def sum(self, a, b=None):
        if b is None:
            return self.sum(0, a)

        res = self.sum_li[min(self.n-1, b-1)]
        if a > 0:
            res -= self.sum_li[a-1]
        return res

n,m,s=l_in()

uvab=[]
edges = [[] for _ in range(n)]
for _ in range(m):
    u,v,a,b = l_in()
    edges[u-1].append((v-1,a,b))
    edges[v-1].append((u-1,a,b))

cd = [l_in() for _ in range(n)]

# dp[i][g] city i で g まいの銀貨をもつための最小時間
m = 1001
dp = [[-1]*m for _ in range(n)]

from heapq import heappush,heappop
h = []

for g in range(min(s+1,m)):
    heappush(h, (0,-g,0))
 #   print(g,h,s,m)
 
while len(h) > 0:
    t,g,i = h[0]
#    print(h)

    g*=-1

#   print(h[0])
    heappop(h)

    if dp[i][g] != -1:
        continue

    dp[i][g] = t
    
    
    for v,a,b in edges[i]:
        if g-a >= 0:
            heappush(h,(t+b,-(g-a),v))

    c,d = cd[i]
    if g+c < m:
        heappush(h,(t+d,-(g+c),i))
    


#for d in dp:
#    pass
#    print(d)


for i in range(1, n):
    res = -1
    for v,a,b in edges[i]:
        min_t = -1
        for g in range(a,m):
            t = dp[v][g]
            if t == -1:
                continue
            if min_t == -1 or min_t > t:
                min_t = t
#                print("min_t", v,g,min_t)

        if res == -1 or res > min_t+b:
            res = min_t+b

#    print(dp[i])
    for t in dp[i]:
        if t == -1:
            continue
        if res == -1  or t < res:
            res = t
            
    print(res)

Submission status: Wrong Answer

Solution code:
from heapq import *
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():

    inf=10**32
    n,m,s=MI()
    to=[[] for _ in range(n)]
    for _ in range(m):
        u,v,a,b=MI()
        to[u-1].append((v-1,a,b))
        to[v-1].append((u-1,a,b))
    cd=LLI(n)

    dp=[[inf]*5005 for _ in range(n)]
    hp=[]
    heappush(hp,(0,min(s,5000),0))

    while hp:
        t,g,u=heappop(hp)
        if dp[u][g]<t:continue
        #fin[u]=True
        #if sum(fin)==n:break
        c,d=cd[u]
        if g+c<5000:
            if dp[u][g + c] <= t + d: continue
            dp[u][g + c] = t + d
            heappush(hp, (t + d, g + c, u))
        else:
            if dp[u][5000] <= t + d: continue
            dp[u][5000] = t + d
            heappush(hp, (t + d, 5000, u))
        for v,a,b in to[u]:
            if g-a<0:continue
            if dp[v][g-a]<=t+b:continue
            dp[v][g - a] = t + b
            heappush(hp,(t+b,g-a,v))
    for u in range(1,n):
        print(min(dp[u]))

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

MAX_FARE = M * 50

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

state_table = [[None] * (MAX_FARE + 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]
		while True:
			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))
				if n_money >= max_fare:
					break
			n_money += count
			n_time += d_time


#for i in range(N):
#	print(i, state_table[i])

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
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

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

def print_l(l):
    print(' '.join(map(str, l)))

class Interval():
    def __init__(self, li):
        self.li = li
        self.n = len(li)
        self.sum_li = [li[0]]
        for i in range(1, self.n):
            self.sum_li.append(self.sum_li[i-1] + li[i])

    def sum(self, a, b=None):
        if b is None:
            return self.sum(0, a)

        res = self.sum_li[min(self.n-1, b-1)]
        if a > 0:
            res -= self.sum_li[a-1]
        return res

n,m,s=l_in()

uvab=[]
edges = [[] for _ in range(n)]
for _ in range(m):
    u,v,a,b = l_in()
    edges[u-1].append((v-1,a,b))
    edges[v-1].append((u-1,a,b))

cd = [l_in() for _ in range(n)]

# dp[i][g] city i で g まいの銀貨をもつための最小時間
m = 101
dp = [[-1]*m for _ in range(n)]

from heapq import heappush,heappop
h = []

for g in range(min(s+1,m)):
    heappush(h, (0,-g,0))
 #   print(g,h,s,m)
 
while len(h) > 0:
    t,g,i = h[0]
#    print(h)

    g*=-1

#   print(h[0])
    heappop(h)

    if dp[i][g] != -1:
        continue

    dp[i][g] = t
    
    
    for v,a,b in edges[i]:
        if g-a >= 0:
            heappush(h,(t+b,-(g-a),v))

    c,d = cd[i]
    if g+c < m:
        heappush(h,(t+d,-(g+c),i))
    


#for d in dp:
#    pass
#    print(d)


for i in range(1, n):
    res = -1
    for v,a,b in edges[i]:
        min_t = -1
        for g in range(a,m):
            t = dp[v][g]
            if t == -1:
                continue
            if min_t == -1 or min_t > t:
                min_t = t
#                print("min_t", v,g,min_t)

        if res == -1 or res > min_t+b:
            res = min_t+b

#    print(dp[i])
    for t in dp[i]:
        if t == -1:
            continue
        if res == -1  or t < res:
            res = t
            
    print(res)