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 heapq
from collections import defaultdict


class Dijkstra(object):

    """ 使用例
    dik = Dijkstra()
    edge = defaultdict(list)
    edge[(1, 1)].append([1, (1, 2)])
    edge[(1, 2)].append([1, (1, 1)])
    edge[(1, 2)].append([2, (2, 1)])
    edge[(2, 1)].append([2, (1, 2)])
    edge[(2, 1)].append([5, (2, 2)])
    edge[(2, 2)].append([5, (2, 1)])
    edge[(2, 2)].append([3, (1, 2)])
    edge[(1, 2)].append([3, (2, 2)])

    s0 = (1, 1)
    ans = dik(s0, edge)

    """

    def __init(self):
        pass

    def __call__(self, s0, edge):

        # s0:始点 (,,,)
        # edge[(,,,)] = [コスト、(,,,)], [コスト、(,,,)]

        d = defaultdict(lambda: float('inf'))
        used = defaultdict(lambda: True)

        edgelist = edge[s0]
        heapq.heapify(edgelist)

        d[s0] = 0
        used[s0] = False

        while len(edgelist):
            minedge = heapq.heappop(edgelist)
            if not used[minedge[1]]:
                continue
            v = minedge[1]
            d[v] = minedge[0]
            used[v] = False

            for e in edge[v]:
                if used[e[1]]:
                    heapq.heappush(edgelist, [e[0] + d[v], e[1]])

        return d


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

s_max = 2500
S = min(S, s_max)

dik = Dijkstra()
edge = defaultdict(list)
s0 = (1, S)


for m in range(1, M + 1):
    U, V, A, B = map(int, input().split())
    for s in range(A, s_max + 1):
        edge[(U, s)].append([B, (V, s - A)])
        edge[(V, s)].append([B, (U, s - A)])

for n in range(1, N + 1):
    C, D = map(int, input().split())
    for s in range(s_max + 1):
        s1 = min(s + C, s_max)
        edge[(n, s)].append([D, (n, s1)])

exit()
d = dik(s0, edge)

for n in range(2, N + 1):
    ans = []
    for s in range(s_max + 1):
        ans.append(d[(n, s)])
    print(min(ans))

Submission status: Wrong Answer

Solution code:
import heapq
from collections import defaultdict


class Dijkstra(object):

    """ 使用例
    dik = Dijkstra()
    edge = defaultdict(list)
    edge[(1, 1)].append([1, (1, 2)])
    edge[(1, 2)].append([1, (1, 1)])
    edge[(1, 2)].append([2, (2, 1)])
    edge[(2, 1)].append([2, (1, 2)])
    edge[(2, 1)].append([5, (2, 2)])
    edge[(2, 2)].append([5, (2, 1)])
    edge[(2, 2)].append([3, (1, 2)])
    edge[(1, 2)].append([3, (2, 2)])

    s0 = (1, 1)
    ans = dik(s0, edge)

    """

    def __init(self):
        pass

    def __call__(self, s0, edge):

        # s0:始点 (,,,)
        # edge[(,,,)] = [コスト、(,,,)], [コスト、(,,,)]

        d = defaultdict(lambda: float('inf'))
        used = defaultdict(lambda: True)

        edgelist = edge[s0]
        heapq.heapify(edgelist)

        d[s0] = 0
        used[s0] = False

        while len(edgelist):
            minedge = heapq.heappop(edgelist)
            if not used[minedge[1]]:
                continue
            v = minedge[1]
            d[v] = minedge[0]
            used[v] = False

            for e in edge[v]:
                if used[e[1]]:
                    heapq.heappush(edgelist, [e[0] + d[v], e[1]])

        return d


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

s_max = 2500
S = min(S, s_max)

dik = Dijkstra()
edge = defaultdict(list)
s0 = (1, S)


for m in range(1, M + 1):
    U, V, A, B = map(int, input().split())
    for s in range(A, s_max + 1):
        edge[(U, s)].append([B, (V, s - A)])
        edge[(V, s)].append([B, (U, s - A)])

for n in range(1, N + 1):
    C, D = map(int, input().split())
    for s in range(s_max + 1):
        s1 = min(s + C, s_max)
        edge[(n, s)].append([D, (n, s1)])

d = dik(s0, edge)
exit()
for n in range(2, N + 1):
    ans = []
    for s in range(s_max + 1):
        ans.append(d[(n, s)])
    print(min(ans))

Submission status: Wrong Answer

Solution code:
import heapq
from collections import defaultdict


class Dijkstra(object):

    """ 使用例
    dik = Dijkstra()
    edge = defaultdict(list)
    edge[(1, 1)].append([1, (1, 2)])
    edge[(1, 2)].append([1, (1, 1)])
    edge[(1, 2)].append([2, (2, 1)])
    edge[(2, 1)].append([2, (1, 2)])
    edge[(2, 1)].append([5, (2, 2)])
    edge[(2, 2)].append([5, (2, 1)])
    edge[(2, 2)].append([3, (1, 2)])
    edge[(1, 2)].append([3, (2, 2)])

    s0 = (1, 1)
    ans = dik(s0, edge)

    """

    def __init(self):
        pass

    def __call__(self, s0, edge):

        # s0:始点 (,,,)
        # edge[(,,,)] = [コスト、(,,,)], [コスト、(,,,)]

        d = defaultdict(lambda: float('inf'))
        used = defaultdict(lambda: True)

        edgelist = edge[s0]
        heapq.heapify(edgelist)

        d[s0] = 0
        used[s0] = False

        while len(edgelist):
            minedge = heapq.heappop(edgelist)
            if not used[minedge[1]]:
                continue
            v = minedge[1]
            d[v] = minedge[0]
            used[v] = False

            for e in edge[v]:
                if used[e[1]]:
                    heapq.heappush(edgelist, [e[0] + d[v], e[1]])

        return d


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

dik = Dijkstra()
edge = defaultdict(list)
s0 = (1, S)

s_max = 3000
for m in range(1, M + 1):
    U, V, A, B = map(int, input().split())
    for s in range(A, s_max + 1):
        edge[(U, s)].append([B, (V, s - A)])
        edge[(V, s)].append([B, (U, s - A)])

for n in range(1, N + 1):
    C, D = map(int, input().split())
    for s in range(s_max - C + 1):
        edge[(n, s)].append([n, (D, s + C)])

d = dik(s0, edge)

for n in range(2, N + 1):
    ans = []
    for s in range(s_max + 1):
        ans.append(d[(n, s)])
    print(min(ans))

Submission status: Wrong Answer

Solution code:
from operator import mul
from functools import reduce
from fractions import gcd
import math
import bisect
import itertools
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
INF = float("inf")


class Edge:
    def __init__(self, to, cost):
        self.to = to
        self.cost = cost


def dijkstra(G, s1, s2, n1, n2):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d = [[INF] * n2 for _ in range(n1)]
    used = [[False] * n2 for _ in range(n1)]
    d[s1][s2] = 0
    
    while True:
        ni, nj = -1, -1
        #まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n1):
            for j in range(n2):
                if used[i][j]:
                    continue
                if ni == -1 and nj == -1:
                    ni, nj = i, j
                elif d[i][j] < d[ni][nj]:
                    ni, nj = i, j
        if ni == -1 and nj == -1:
               break
        used[ni][nj] = True
               
        for edge in G[ni][nj]:
            to1, to2 = edge.to[0], edge.to[1]
            cost = edge.cost
            d[to1][to2] = min(d[to1][to2], d[ni][nj] + cost)
    
    return d


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

    U = [0] * M
    V = [0] * M
    A = [0] * M
    B = [0] * M
    for i in range(M):
        U[i], V[i], A[i], B[i] = map(int, input().split())
        U[i] -= 1; V[i] -= 1
    
    L = max(A) * (N-1)
    G = [[[] for _ in range(L+1)] for _ in range(N)]
    for i in range(M):
        u, v, a, b = U[i], V[i], A[i], B[i]
        for money in range(L):
            if money - a >= 0:
                G[u][money].append(Edge([v, money - a], b))
                G[v][money].append(Edge([u, money - a], b))
    
    for node in range(N):
        c, d = map(int, input().split())
        for money in range(L):
            nmoney = money + c
            if nmoney > L:
                nmoney = L
            G[node][money].append(Edge([node, nmoney], d))
            G[node][nmoney].append(Edge([node, money], 0))
    
    if S > L:
        S = L
    ans = dijkstra(G, 0, S, N, L+1)
    for i in range(1, N):
        print(min(ans[i]))
    

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import heapq
INF = 10 ** 18

class edge:
    def __init__(self, to, cost, t):
        self.to, self.cost, self.t = to, cost, t

def main():
    N, M, S = (int(_) for _ in input().split())
    E = defaultdict(list)
    d = [INF] * (N+1)
    d[1] = 0
    c = [0] * (N+1)
    c[1] = S
    for i in range(M):
        u, v, a, b = (int(_) for _ in input().split())
        E[u].append(edge(v, a, b))
        E[v].append(edge(u, a, b))

    change = [[int(_) for _ in input().split()] for __ in range(N)]

    def dijkstra(s, d, c):
        que = list()
        heapq.heapify(que)
        dd = [[0] * 2 for _ in range(N+1)]
        for i in range(N+1):
            dd[i][0] = INF
        dd[s][0] = d[s]
        heapq.heappush(que, [dd[s][0], s])

        while que:
            p = heapq.heappop(que)
            v = p[1]
            if dd[v][0] < p[0]: continue
            for e in E[v]:
                if dd[e.to][0] > dd[v][0] + e.t:
                    dd[e.to][0] = dd[v][0] + e.t
                    dd[e.to][1] = dd[v][1] + e.cost
                    heapq.heappush(que, [dd[e.to][0], e.to])
        f = [0]
        cc = [0] * (N+1)
        cc[s] = c[s]
        #print(dd)
        for i in range(1, N+1):
            if i == s: f.append(min(d[i], dd[i][0]))
            elif cc[s] >= dd[i][1]:
                if d[i] <= dd[i][0]:
                    f.append(d[i])
                    cc[i] = c[i]
                else:
                    f.append(dd[i][0])
                    cc[i] = cc[s] - dd[i][1]
            else:
                dd[i][0] += (dd[i][1] - cc[s] + change[s-1][0] - 1)//change[s-1][0] * change[s-1][1]
                if d[i] <= dd[i][0]:
                    f.append(d[i])
                    cc[i] = c[i]
                else:
                    f.append(dd[i][0])
                    cc[i] = (dd[i][1] - cc[s] + change[s-1][0] - 1)//change[s-1][0] * change[s-1][0] - (dd[i][1] - cc[s])
        #print(f, cc)
        return f, cc

    for i in range(1, N+1):
        d, c = dijkstra(i, d, c)
    print(*d[2:], sep='\n')
    return

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import heapq
INF = 10 ** 18

class edge:
    def __init__(self, to, cost, t):
        self.to, self.cost, self.t = to, cost, t

def main():
    N, M, S = (int(_) for _ in input().split())
    E = defaultdict(list)
    d = [INF] * (N+1)
    d[1] = 0
    c = [0] * (N+1)
    c[1] = S
    for i in range(M):
        u, v, a, b = (int(_) for _ in input().split())
        E[u].append(edge(v, a, b))
        E[v].append(edge(u, a, b))

    change = [[int(_) for _ in input().split()] for __ in range(N)]

    def dijkstra(s, d, c):
        que = list()
        heapq.heapify(que)
        dd = [[0] * 2 for _ in range(N+1)]
        for i in range(N+1):
            dd[i][0] = INF
        dd[s][0] = d[s]
        heapq.heappush(que, [dd[s][0], s])

        while que:
            p = heapq.heappop(que)
            v = p[1]
            if dd[v][0] < p[0]: continue
            for e in E[v]:
                if dd[e.to][0] > dd[v][0] + e.t:
                    dd[e.to][0] = dd[v][0] + e.t
                    dd[e.to][1] = dd[v][1] + e.cost
                    heapq.heappush(que, [dd[e.to][0], e.to])
        f = [0]
        cc = [0] * (N+1)
        cc[s] = c[s]
        for i in range(1, N+1):
            if i == s: f.append(dd[s][0])
            elif cc[s] >= dd[i][1]:
                cc[i] = cc[s] - dd[i][1]
                f.append(min(d[i], dd[i][0]))
            else:
                dd[i][0] += (dd[i][1] - cc[s] + change[s-1][0] - 1)//change[s-1][0] * change[s-1][1]
                cc[i] = 0
                f.append(min(d[i], dd[i][0]))
        return f, cc

    for i in range(1, N+1):
        d, c = dijkstra(i, d, c)
    print(*d[2:], sep='\n')
    return

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import heapq
INF = 10 ** 12

class edge:
    def __init__(self, to, cost, t):
        self.to, self.cost, self.t = to, cost, t

def main():
    N, M, S = (int(_) for _ in input().split())
    E = defaultdict(list)
    d = [INF] * (N+1)
    d[1] = 0
    c = [0] * (N+1)
    c[1] = S
    for i in range(M):
        u, v, a, b = (int(_) for _ in input().split())
        E[u].append(edge(v, a, b))
        E[v].append(edge(u, a, b))

    change = [[int(_) for _ in input().split()] for __ in range(N)]

    def dijkstra(s, d, c):
        que = list()
        heapq.heapify(que)
        dd = [[0] * 2 for _ in range(N+1)]
        for i in range(N+1):
            dd[i][0] = INF
        dd[s][0] = d[s]
        heapq.heappush(que, [dd[s][0], s])

        while que:
            p = heapq.heappop(que)
            v = p[1]
            if dd[v][0] < p[0]: continue
            for e in E[v]:
                if dd[e.to][0] > dd[v][0] + e.t:
                    dd[e.to][0] = dd[v][0] + e.t
                    dd[e.to][1] = dd[v][1] + e.cost
                    heapq.heappush(que, [dd[e.to][0], e.to])
        f = [0]
        cc = [0] * (N+1)
        cc[s] = c[s]
        for i in range(1, N+1):
            if i == s: f.append(dd[s][0])
            elif cc[s] >= dd[i][1]:
                cc[i] = cc[s] - dd[i][1]
                f.append(min(d[i], dd[i][0]))
            else:
                dd[i][0] += (dd[i][1] - cc[s] + change[s-1][0] - 1)//change[s-1][0] * change[s-1][1]
                cc[i] = 0
                f.append(min(d[i], dd[i][0]))
        return f, cc

    for i in range(1, N+1):
        d, c = dijkstra(i, d, c)
    print(*d[2:], sep='\n')
    return

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# Generated by https://github.com/kyuridenamida/atcoder-tools
import sys
import heapq

INF = 1145141919


def solve(N: int, M: int, S: int, U: "List[int]", V: "List[int]", A: "List[int]", B: "List[int]", C: "List[int]", D: "List[int]"):
    MAX = max(A) * (N-1)
    S = min(S, MAX)

    G = [[] for _ in range(N)]
    for u, v, a, b in zip(U, V, A, B):
        G[u-1].append([v-1, [a, b]])
        G[v-1].append([u-1, [a, b]])

    dp = [[INF for _ in range(MAX + 1)] for _ in range(N)]
    dp[0][S] = 0

    Q = []
    heapq.heapify(Q)
    heapq.heappush(Q, [0, S, 0])

    while len(Q) != 0:
        time, s, v = heapq.heappop(Q)
        if time > dp[v][s]:
            continue

        if s + C[v] <= MAX:
            ns = s + C[v]
            ntime = time + D[v]
            if dp[v][ns] > ntime:
                dp[v][ns] = ntime
                heapq.heappush(Q, [ntime, ns, v])

        for nv, [ns, ntime] in G[v]:
            if s < ns:
                continue
            ns = s - ns
            ntime += time
            if dp[nv][ns] > ntime:
                dp[nv][ns] = ntime
                heapq.heappush(Q, [ntime, ns, nv])

    ans = [min(dp[i]) for i in range(1, N)]
    return "\n".join(map(str, ans))


def main():

    sys.setrecursionlimit(10 ** 6)

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    S = int(next(tokens))  # type: int
    U = [int()] * (M)  # type: "List[int]"
    V = [int()] * (M)  # type: "List[int]"
    A = [int()] * (M)  # type: "List[int]"
    B = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        U[i] = int(next(tokens))
        V[i] = int(next(tokens))
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    C = [int()] * (N)  # type: "List[int]"
    D = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        C[i] = int(next(tokens))
        D[i] = int(next(tokens))
    print(solve(N, M, S, U, V, A, B, C, D))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# Generated by https://github.com/kyuridenamida/atcoder-tools
import sys
import heapq

INF = 1145141919


def solve(N: int, M: int, S: int, U: "List[int]", V: "List[int]", A: "List[int]", B: "List[int]", C: "List[int]", D: "List[int]"):
    MAX = max(A) * (N-1)
    S = min(S, MAX)

    G = [[] for _ in range(N)]
    for u, v, a, b in zip(U, V, A, B):
        G[u-1].append([v-1, [a, b]])
        G[v-1].append([u-1, [a, b]])

    dp = [[INF for _ in range(MAX + 1)] for _ in range(N)]
    dp[0][S] = 0

    Q = []
    heapq.heapify(Q)
    heapq.heappush(Q, [0, [0, -S]])

    while len(Q) != 0:
        tmp = heapq.heappop(Q)
        time, [v, s] = -tmp[0], [-tmp[1][0], -tmp[1][1]]
        if time > dp[v][s]:
            continue

        if s + C[v] <= MAX:
            ns = s + C[v]
            ntime = time + D[v]
            if dp[v][ns] > ntime:
                dp[v][ns] = ntime
                heapq.heappush(Q, [-ntime, [-v, -ns]])

        for nv, [ns, ntime] in G[v]:
            if s < ns:
                continue
            ns = s - ns
            ntime += time
            if dp[nv][ns] > ntime:
                dp[nv][ns] = ntime
                heapq.heappush(Q, [-ntime, [-nv, -ns]])

    ans = [min(dp[i]) for i in range(1, N)]
    return "\n".join(map(str, ans))


def main():

    sys.setrecursionlimit(10 ** 6)

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    S = int(next(tokens))  # type: int
    U = [int()] * (M)  # type: "List[int]"
    V = [int()] * (M)  # type: "List[int]"
    A = [int()] * (M)  # type: "List[int]"
    B = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        U[i] = int(next(tokens))
        V[i] = int(next(tokens))
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    C = [int()] * (N)  # type: "List[int]"
    D = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        C[i] = int(next(tokens))
        D[i] = int(next(tokens))
    print(solve(N, M, S, U, V, A, B, C, D))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# Generated by https://github.com/kyuridenamida/atcoder-tools
import sys
import heapq

INF = 1145141919


def solve(N: int, M: int, S: int, U: "List[int]", V: "List[int]", A: "List[int]", B: "List[int]", C: "List[int]", D: "List[int]"):
    MAX = 2500  # max(A) * (N-1)
    S = min(S, MAX)

    G = [[] for _ in range(N)]
    for u, v, a, b in zip(U, V, A, B):
        G[u-1].append([v-1, [a, b]])
        G[v-1].append([u-1, [a, b]])

    dp = [[INF for _ in range(MAX + 1)] for _ in range(N)]
    dp[0][S] = 0

    Q = []
    heapq.heapify(Q)
    heapq.heappush(Q, [0, [0, S]])

    while len(Q) != 0:
        time, [v, s] = heapq.heappop(Q)
        if time > dp[v][s]:
            continue

        if s + C[v] <= MAX:
            ns = s + C[v]
            ntime = time + D[v]
            if dp[v][ns] > ntime:
                dp[v][ns] = ntime
                heapq.heappush(Q, [ntime, [v, ns]])

        for nv, [ns, ntime] in G[v]:
            if s < ns:
                continue
            ns = s-ns
            ntime += time
            if dp[nv][ns] > ntime:
                dp[nv][ns] = ntime
                heapq.heappush(Q, [ntime, [nv, ns]])

    ans = []
    for i in range(1, N):
        # print(dp[i])
        ans.append(min([dp[i][j] for j in range(MAX + 1)]))

    return "\n".join(map(str, ans))


def main():

    sys.setrecursionlimit(10 ** 6)

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    S = int(next(tokens))  # type: int
    U = [int()] * (M)  # type: "List[int]"
    V = [int()] * (M)  # type: "List[int]"
    A = [int()] * (M)  # type: "List[int]"
    B = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        U[i] = int(next(tokens))
        V[i] = int(next(tokens))
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    C = [int()] * (N)  # type: "List[int]"
    D = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        C[i] = int(next(tokens))
        D[i] = int(next(tokens))
    print(solve(N, M, S, U, V, A, B, C, D))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# Generated by https://github.com/kyuridenamida/atcoder-tools
import sys
import heapq

INF = 1145141919


def solve(N: int, M: int, S: int, U: "List[int]", V: "List[int]", A: "List[int]", B: "List[int]", C: "List[int]", D: "List[int]"):
    MAX = max(A) * (N-1)
    S = min(S, MAX)

    G = [[] for _ in range(N)]
    for u, v, a, b in zip(U, V, A, B):
        G[u-1].append([v-1, [a, b]])
        G[v-1].append([u-1, [a, b]])

    dp = [[INF for _ in range(MAX + 1)] for _ in range(N)]
    dp[0][S] = 0

    Q = []
    heapq.heapify(Q)
    heapq.heappush(Q, [0, [0, S]])

    while len(Q) != 0:
        time, [v, s] = heapq.heappop(Q)
        if time > dp[v][s]:
            continue

        if s + C[v] <= MAX:
            ns = s + C[v]
            ntime = time + D[v]
            if dp[v][ns] > ntime:
                dp[v][ns] = ntime
                heapq.heappush(Q, [ntime, [v, ns]])

        for nv, [ns, ntime] in G[v]:
            if s < ns:
                continue
            ns = s-ns
            ntime += time
            if dp[nv][ns] > ntime:
                dp[nv][ns] = ntime
                heapq.heappush(Q, [ntime, [nv, ns]])

    ans = []
    for i in range(1, N):
        # print(dp[i])
        ans.append(min([dp[i][j] for j in range(MAX + 1)]))

    return "\n".join(map(str, ans))


def main():

    sys.setrecursionlimit(10 ** 6)

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    S = int(next(tokens))  # type: int
    U = [int()] * (M)  # type: "List[int]"
    V = [int()] * (M)  # type: "List[int]"
    A = [int()] * (M)  # type: "List[int]"
    B = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        U[i] = int(next(tokens))
        V[i] = int(next(tokens))
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    C = [int()] * (N)  # type: "List[int]"
    D = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        C[i] = int(next(tokens))
        D[i] = int(next(tokens))
    print(solve(N, M, S, U, V, A, B, C, D))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import heapq
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 9)
INF = 1001001001001
MAX_V = 50
MAX_S = MAX_V*50+5

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())
    g[u-1].append((v-1,a,b))
    g[v-1].append((u-1,a,b))
cd = [list(map(int, input().split())) for _ in range(n)]

# print(g)
# print(cd)
dp = [[INF]*(MAX_S+5) for _ in range(MAX_V)]   # 頂点vに銀貨xを持っている時の時間
s = min(s, MAX_S)
q = []

def push(v,s,x):
    if s<0: return
    if dp[v][s]<=x: return
    dp[v][s] = x
    heapq.heappush(q, (x,s,v))

push(0, s, 0)
while q:
    x,s,v = heapq.heappop(q)
    if dp[v][s] != x: continue
    ns = min(s+cd[v][0], MAX_S)
    push(v, ns, x+cd[v][1])
    for to, a, b in g[v]:
        push(to, s-a, x+b)

# print(dp)
for i in range(1,n):
    print(min(dp[i][:MAX_S+5]))
    # print(dp[i][:50])

Submission status: Wrong Answer

Solution code:
import heapq
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 9)
INF = 1001001001
MAX_V = 50
MAX_S = MAX_V*50+5

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())
    g[u-1].append((v-1,a,b))
    g[v-1].append((u-1,a,b))
cd = [list(map(int, input().split())) for _ in range(n)]

# print(g)
# print(cd)
dp = [[INF]*(MAX_S+5) for _ in range(MAX_V)]   # 頂点vに銀貨xを持っている時の時間
s = min(s, MAX_S)
q = []

def push(v,s,x):
    if s<0: return
    if dp[v][s]<=x: return
    dp[v][s] = x
    heapq.heappush(q, (x,s,v))

push(0, s, 0)
while q:
    x,s,v = heapq.heappop(q)
    if dp[v][s] != x: continue
    ns = min(s+cd[v][0], MAX_S)
    push(v, ns, x+cd[v][1])
    for to, a, b in g[v]:
        push(to, s-a, x+b)

# print(dp)
for i in range(1,n):
    print(min(dp[i][:MAX_S+5]))
    # print(dp[i][:50])

Submission status: Wrong Answer

Solution code:
def main():    
    import heapq
    
    n, m, s = map(int, input().split())
    if s >= 2500:
        s = 2499
    
    edges = [[] for _ in range(n)]
    for _ in range(m):
        from_, to, cost, time = map(int, input().split())
        edges[from_-1].append((to-1, cost, time))
        edges[to-1].append((from_-1, cost, time))
    
    banks = []
    for i in range(n):
        coin, time = map(int, input().split())
        banks.append((coin, time))
    
    INF = float('INF')
    DP = [[INF] * 2500 for _ in range(n)]
    DP[0][s] = 0
    ans = [INF] * n
    
    def push_todo(node, coin, time):
        if coin < 0:
            return
        if time >= DP[node][coin]:
            return
        heapq.heappush(todo, (time, node, coin))
        DP[node][coin] = time
    
    def charge(node, current_coin, current_time):
        coin, time = banks[node]
        new_coin = current_coin + coin
        if new_coin >= 2500:
            new_coin = 2499
        push_todo(node, new_coin, current_time+time)
    
    todo = [(0, 0, s)]  # time, node, coin
    while todo:
        current_time, node, current_coin = heapq.heappop(todo)
        if current_time >= DP[node][current_coin]:
            continue
    
        if current_time < ans[node]:
            ans[node] = current_time
    
        charge(node, current_coin, current_time)
    
        for to, cost, time in edges[node]:
            push_todo(to, current_coin-cost, current_time+time)
    
    for a in ans[1:]:
        print(a)


if __name__ == '__main__':
    main()