Problem:


Score : 500 points

Problem Statement

There are N cities numbered 1 to N, connected by M railroads.

You are now at City 1, with 10^{100} gold coins and S silver coins in your pocket.

The i-th railroad connects City U_i and City V_i bidirectionally, and a one-way trip costs A_i silver coins and takes B_i minutes.
You cannot use gold coins to pay the fare.

There is an exchange counter in each city. At the exchange counter in City i, you can get C_i silver coins for 1 gold coin.
The transaction takes D_i minutes for each gold coin you give.
You can exchange any number of gold coins at each exchange counter.

For each t=2, ..., N, find the minimum time needed to travel from City 1 to City t. You can ignore the time spent waiting for trains.

Constraints

2 \leq N \leq 50

N-1 \leq M \leq 100

0 \leq S \leq 10^9

1 \leq A_i \leq 50

1 \leq B_i,C_i,D_i \leq 10^9

1 \leq U_i < V_i \leq N

There is no pair i, j(i \neq j) such that (U_i,V_i)=(U_j,V_j).

Each city t=2,...,N can be reached from City 1 with some number of railroads.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M S
U_1 V_1 A_1 B_1
:
U_M V_M A_M B_M
C_1 D_1
:
C_N D_N

Output

For each t=2, ..., N in this order, print a line containing the minimum time needed to travel from City 1 to City t.

Sample Input 1

3 2 1
1 2 1 2
1 3 2 4
1 11
1 2
2 5

Sample Output 1

2
14

The railway network in this input is shown in the figure below.

In this figure, each city is labeled as follows:

The first line: the ID number i of the city (i for City i)

The second line: C_i / D_i

Similarly, each railroad is labeled as follows:

The first line: the ID number i of the railroad (i for the i-th railroad in input)

The second line: A_i / B_i

You can travel from City 1 to City 2 in 2 minutes, as follows:

Use the 1-st railroad to move from City 1 to City 2 in 2 minutes.

You can travel from City 1 to City 3 in 14 minutes, as follows:

Use the 1-st railroad to move from City 1 to City 2 in 2 minutes.

At the exchange counter in City 2, exchange 3 gold coins for 3 silver coins in 6 minutes.

Use the 1-st railroad to move from City 2 to City 1 in 2 minutes.

Use the 2-nd railroad to move from City 1 to City 3 in 4 minutes.

Sample Input 2

4 4 1
1 2 1 5
1 3 4 4
2 4 2 2
3 4 1 1
3 1
3 1
5 2
6 4

Sample Output 2

5
5
7

The railway network in this input is shown in the figure below:

You can travel from City 1 to City 4 in 7 minutes, as follows:

At the exchange counter in City 1, exchange 2 gold coins for 6 silver coins in 2 minutes.

Use the 2-nd railroad to move from City 1 to City 3 in 4 minutes.

Use the 4-th railroad to move from City 3 to City 4 in 1 minutes.

Sample Input 3

6 5 1
1 2 1 1
1 3 2 1
2 4 5 1
3 5 11 1
1 6 50 1
1 10000
1 3000
1 700
1 100
1 1
100 1

Sample Output 3

1
9003
14606
16510
16576

The railway network in this input is shown in the figure below:

You can travel from City 1 to City 6 in 16576 minutes, as follows:

Use the 1-st railroad to move from City 1 to City 2 in 1 minute.

At the exchange counter in City 2, exchange 3 gold coins for 3 silver coins in 9000 minutes.

Use the 1-st railroad to move from City 2 to City 1 in 1 minute.

Use the 2-nd railroad to move from City 1 to City 3 in 1 minute.

At the exchange counter in City 3, exchange 8 gold coins for 8 silver coins in 5600 minutes.

Use the 2-nd railroad to move from City 3 to City 1 in 1 minute.

Use the 1-st railroad to move from City 1 to City 2 in 1 minute.

Use the 3-rd railroad to move from City 2 to City 4 in 1 minute.

At the exchange counter in City 4, exchange 19 gold coins for 19 silver coins in 1900 minutes.

Use the 3-rd railroad to move from City 4 to City 2 in 1 minute.

Use the 1-st railroad to move from City 2 to City 1 in 1 minute.

Use the 2-nd railroad to move from City 1 to City 3 in 1 minute.

Use the 4-th railroad to move from City 3 to City 5 in 1 minute.

At the exchange counter in City 5, exchange 63 gold coins for 63 silver coins in 63 minutes.

Use the 4-th railroad to move from City 5 to City 3 in 1 minute.

Use the 2-nd railroad to move from City 3 to City 1 in 1 minute.

Use the 5-th railroad to move from City 1 to City 6 in 1 minute.

Sample Input 4

4 6 1000000000
1 2 50 1
1 3 50 5
1 4 50 7
2 3 50 2
2 4 50 4
3 4 50 3
10 2
4 4
5 5
7 7

Sample Output 4

1
3
5

The railway network in this input is shown in the figure below:

Sample Input 5

2 1 0
1 2 1 1
1 1000000000
1 1

Sample Output 5

1000000001

The railway network in this input is shown in the figure below:

You can travel from City 1 to City 2 in 1000000001 minutes, as follows:

At the exchange counter in City 1, exchange 1 gold coin for 1 silver coin in 1000000000 minutes.

Use the 1-st railroad to move from City 1 to City 2 in 1 minute.



Sample input:
3 2 1
1 2 1 2
1 3 2 4
1 11
1 2
2 5


Sample output:
2
14

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
sysread = sys.stdin.readline
from heapq import heappop, heappush

def run():
    N, M, S = list(map(int, sysread().split()))
    to = [[] for _ in range(N+1)]
    max_m = 2500
    for _ in range(M):
        u,m,a,b = list(map(int, sysread().split()))
        to[u].append((m,b,a))
        to[m].append((u,b,a))

    cd = [int(i) for i in sys.stdin.read().split()]
    C = [0]+ cd[::2]
    D = [0]+ cd[1::2]

    queue = []
    # (time, node, rest-coin)
    if S > max_m: S = max_m
    heappush(queue, (0, 1, S))

    state = [[1<<61] * (max_m+1) for _ in range(N+1)]

    while queue:
        time, node, coin = heappop(queue)
        if state[node][coin] < time: continue
        if coin + C[node] <= max_m and time + D[node] < state[node][coin+C[node]]:
            state[node][coin+C[node]] = time + D[node]
            heappush(queue, (time+D[node], node, coin+C[node]))
        for n_node, n_time, n_coin in to[node]:
            if coin < n_coin:continue
            if state[n_node][coin-n_coin] < n_time + time:continue
            state[n_node][coin - n_coin] = n_time + time
            heappush(queue, (time + n_time, n_node, coin - n_coin))
    for s in state[2:]:
        print(min(s))

if __name__ == "__main__":
    run()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
sysread = sys.stdin.readline
from heapq import heappop, heappush

def run():
    # import sys
    # A = list(map(int, sys.stdin.readline().split()))
    # all = sys.stdin.readlines()
    # all = list(map(int, sys.stdin.read().split())
    #N, *A = map(int, open(0))
    #N = int(input())
    N, M, S = list(map(int, sysread().split()))
    to = [[] for _ in range(N+1)]
    max_m = 2500
    for _ in range(M):
        u,m,a,b = list(map(int, sysread().split()))
        to[u].append((m,b,a))
        to[m].append((u,b,a))


    C, D = [0], [0]
    for _ in range(N):
        c,d = list(map(int, sysread().split()))
        C.append(c)
        D.append(d)

    queue = []
    # (time, node, rest-coin)
    if S > max_m:
        S = max_m
    heappush(queue, (0, 1, S))

    state = [[1<<61] * (max_m+1) for _ in range(N+1)]

    while queue:
        time, node, coin = heappop(queue)
        if state[node][coin] < time: continue
        if coin + C[node] <= max_m and time + D[node] < state[node][coin+C[node]]:
            state[node][coin+C[node]] = time + D[node]
            heappush(queue, (time+D[node], node, coin+C[node]))
        for n_node, n_time, n_coin in to[node]:
            if coin < n_coin:continue
            if state[n_node][coin-n_coin] < n_time + time:continue
            state[n_node][coin - n_coin] = n_time + time
            heappush(queue, (time + n_time, n_node, coin - n_coin))
    for s in state[2:]:
        print(min(s))

if __name__ == "__main__":
    run()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
sysread = sys.stdin.readline
from heapq import heappop, heappush

def run():
    # import sys
    # A = list(map(int, sys.stdin.readline().split()))
    # all = sys.stdin.readlines()
    # all = list(map(int, sys.stdin.read().split())
    #N, *A = map(int, open(0))
    #N = int(input())
    N, M, S = list(map(int, sysread().split()))
    to = [[] for _ in range(N+1)]
    max_m = 2500
    for _ in range(M):
        u,m,a,b = list(map(int, sysread().split()))
        to[u].append((m,b,a))
        to[m].append((u,b,a))


    CD = [[0,0]]
    for _ in range(N):
        c,d = list(map(int, sysread().split()))
        CD.append([c,d])

    queue = []
    # (time, node, rest-coin)
    if S > max_m:
        S = max_m
    heappush(queue, (0, 1, S))

    state = [[1<<61] * (max_m+1) for _ in range(N+1)]

    while queue:
        time, node, coin = heappop(queue)
        if state[node][coin] < time: continue
        c, d = CD[node]
        if coin + c <= max_m and time + d < state[node][coin+c]:
            state[node][coin+c] = time + d
            heappush(queue, (time+d, node, coin+c))
        for n_node, n_time, n_coin in to[node]:
            if coin < n_coin:continue
            if state[n_node][coin-n_coin] < n_time + time:continue
            state[n_node][coin - n_coin] = n_time + time
            heappush(queue, (time + n_time, n_node, coin - n_coin))
    for s in state[2:]:
        print(min(s))

if __name__ == "__main__":
    run()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
sysread = sys.stdin.readline
from heapq import heappop, heappush

def run():
    # import sys
    # A = list(map(int, sys.stdin.readline().split()))
    # all = sys.stdin.readlines()
    # all = list(map(int, sys.stdin.read().split())
    #N, *A = map(int, open(0))
    #N = int(input())
    N, M, S = list(map(int, sysread().split()))
    to = [[] for _ in range(N+1)]
    max_m = 2500
    for _ in range(M):
        u,m,a,b = list(map(int, sysread().split()))
        to[u].append((m,b,a))
        to[m].append((u,b,a))


    CD = [[0,0]]
    for _ in range(N):
        c,d = list(map(int, sysread().split()))
        CD.append([c,d])

    queue = []
    # (time, node, rest-coin)
    if S > max_m:
        S = max_m
    heappush(queue, (0, 1, S))

    state = [[float('inf')] * (max_m+1) for _ in range(N+1)]

    while queue:
        time, node, coin = heappop(queue)
        if state[node][coin] < time: continue
        c, d = CD[node]
        if coin + c <= max_m and time + d < state[node][coin+c]:
            state[node][coin+c] = time + d
            heappush(queue, (time+d, node, coin+c))
        for n_node, n_time, n_coin in to[node]:
            if coin < n_coin:continue
            if state[n_node][coin-n_coin] < n_time + time:continue
            state[n_node][coin - n_coin] = n_time + time
            heappush(queue, (time + n_time, n_node, coin - n_coin))
    for s in state[2:]:
        print(min(s))

if __name__ == "__main__":
    run()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
sysread = sys.stdin.readline
from heapq import heappop, heappush

def run():
    # import sys
    # A = list(map(int, sys.stdin.readline().split()))
    # all = sys.stdin.readlines()
    # all = list(map(int, sys.stdin.read().split())
    #N, *A = map(int, open(0))
    #N = int(input())
    N, M, S = list(map(int, sysread().split()))
    to = [[] for _ in range(N+1)]
    max_m = 0
    for _ in range(M):
        u,m,a,b = list(map(int, sysread().split()))
        to[u].append((m,b,a))
        to[m].append((u,b,a))
        max_m = max(max_m, a)

    max_m *= N-1

    CD = [[0,0]]
    for _ in range(N):
        c,d = list(map(int, sysread().split()))
        CD.append([c,d])

    queue = []
    # (time, node, rest-coin)
    if S > max_m:
        S = max_m
    heappush(queue, (0, 1, S))

    state = [[float('inf')] * (max_m+1) for _ in range(N+1)]

    while queue:
        time, node, coin = heappop(queue)
        if state[node][coin] < time: continue
        c, d = CD[node]
        if coin + c <= max_m and time + d < state[node][coin+c]:
            state[node][coin+c] = time + d
            heappush(queue, (time+d, node, coin+c))
        for n_node, n_time, n_coin in to[node]:
            if coin < n_coin:continue
            if state[n_node][coin-n_coin] < n_time + time:continue
            state[n_node][coin - n_coin] = n_time + time
            heappush(queue, (time + n_time, n_node, coin - n_coin))
    for s in state[2:]:
        print(min(s))

if __name__ == "__main__":
    run()

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappop, heappush
import numpy as np


def solve(nn, mm, ss, line_list, cd_list):
    if ss > 5000:
        ss = 5000
    g = dict()
    for i in range(1, nn + 1):
        for s in range(5001):
            g[i * 10000 + s] = dict()
            if s + cd_list[i - 1][0] < 5000:
                g[i * 10000 + s][i * 10000 + s + cd_list[i - 1][0]] = cd_list[i - 1][1]
            elif s < 5000:
                g[i * 10000 + s][i * 10000 + 5000] = cd_list[i - 1][1]
    for u, v, a, b in line_list:
        for s in range(a, 5001):
            g[u * 10000 + s][v * 10000 + s - a] = b
            g[v * 10000 + s][u * 10000 + s - a] = b

    # start from 1
    # d[i, j] = best time at city i with silver j
    d = (10 ** 18) * np.ones((nn + 1) * 10000, dtype=np.int)
    d[10000 + ss] = 0
    h = []
    heappush(h, (0, 10000 + ss))
    while len(h) > 0:
        t, u = heappop(h)
        for v in g[u].keys():
            if t + g[u][v] < d[v]:
                d[v] = t + g[u][v]
                heappush(h, (t + g[u][v], v))

    res = []
    for i in range(2, nn + 1):
        res.append(d[i * 10000:(i + 1) * 10000].min())
    # print(res)
    return res


def main():
    n, m, s = map(int, input().split())
    line_list = [list(map(int, input().split())) for _ in range(m)]
    cd_list = [list(map(int, input().split())) for _ in range(n)]
    res = solve(n, m, s, line_list, cd_list)
    for r in res:
        print(r)


def test():
    assert solve(3, 2, 1, [[1, 2, 1, 2], [1, 3, 2, 4]], [[1, 11], [1, 2], [2, 5]]) == [2, 14]
    assert solve(
        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]]
    ) == [5, 5, 7]


if __name__ == "__main__":
    test()
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from heapq import heappop, heappush,heapify
import sys
input = sys.stdin.readline

N,M,S = map(int,input().split())
UVAB = [list(map(int,input().split())) for i in range(M)]
U,V,A,B = zip(*UVAB)
mc = max(A)* M
g = defaultdict(list)

for u,v,a,b in UVAB:
    for i in range(a,mc+1):
        g[(u,i)].append(((v,i-a),b))
        g[(v,i)].append(((u,i-a),b))
CD = [[0,0]] + [list(map(int,input().split())) for i in range(N)]
C,D = zip(*CD)
C = [min(c,mc) for c in C]

for i in range(1,N+1):
    for c in range(mc+1-C[i]):
        g[(i,c)].append(((i,c+C[i]),D[i]))

S = min(S,mc)
dq = [(0,S,1)]

ans = [[10**15 for j in range(mc+1)] for i in range(N+1)]
ans[1][S] = 0
while dq:
    t, w, v = heappop(dq)
    if ans[v][w] < t:
        continue
    for (nv,nw), nt in g[(v,w)]:
        if ans[nv][nw] > t + nt:
            ans[nv][nw] = t + nt
            heappush(dq,(t+nt,nw,nv))

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

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from heapq import heappop, heappush,heapify
import sys
input = sys.stdin.readline

N,M,S = map(int,input().split())
UVAB = [list(map(int,input().split())) for i in range(M)]
U,V,A,B = zip(*UVAB)
mc = max(A)* M
g = defaultdict(list)

for u,v,a,b in UVAB:
    for i in range(a,mc+1):
        g[(u,i)].append(((v,i-a),b))
        g[(v,i)].append(((u,i-a),b))
CD = [[0,0]] + [list(map(int,input().split())) for i in range(N)]
C,D = zip(*CD)
C = [min(c,mc) for c in C]

for i in range(1,N+1):
    for c in range(mc+1-C[i]):
        g[(i,c)].append(((i,c+C[i]),D[i]))

S = min(S,mc)
dq = [(0,S,1)]

ans = [[10**15 for j in range(mc+1)] for i in range(N+1)]
while dq:
    t, w, v = heappop(dq)
    if ans[v][w] <= t:
        continue
    ans[v][w] = t
    for (nv,nw), nt in g[(v,w)]:
        if ans[nv][nw] > t + nt:
            heappush(dq,(t+nt,nw,nv))

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

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from heapq import heappop, heappush,heapify
import sys
input = sys.stdin.readline

N,M,S = map(int,input().split())
UVAB = [list(map(int,input().split())) for i in range(M)]
U,V,A,B = zip(*UVAB)
mc = max(A)* M
g = defaultdict(list)

for u,v,a,b in UVAB:
    for i in range(a,mc+1):
        g[u+N*i].append((v+N*(i-a),b))
        g[v+N*i].append((u+N*(i-a),b))
CD = [[0,0]] + [list(map(int,input().split())) for i in range(N)]
C,D = zip(*CD)
C = [min(c,mc) for c in C]

for i in range(1,N+1):
    for c in range(mc+1-C[i]):
        g[i+N*c].append((i+N*(c+C[i]),D[i]))

S = min(S,mc)
dq = [(0,S,1)]

ans = [[10**15 for j in range(mc+1)] for i in range(N+1)]
while dq:
    t, w, v = heappop(dq)
    if ans[v][w] < t:
        continue
    ans[v][w] = t
    for temp, nt in g[v+N*w]:
        nv = ((temp-1) % N)+1
        nw = (temp-1) // N
        if ans[nv][nw] > t + nt:
            heappush(dq,(t+nt,nw,nv))

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

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from heapq import heappop, heappush,heapify
import sys
input = sys.stdin.readline

N,M,S = map(int,input().split())
UVAB = [list(map(int,input().split())) for i in range(M)]
U,V,A,B = zip(*UVAB)
mc = max(A)* M
g = defaultdict(list)

for u,v,a,b in UVAB:
    for i in range(a,mc+1):
        g[(u,i)].append(((v,i-a),b))
        g[(v,i)].append(((u,i-a),b))
CD = [[0,0]] + [list(map(int,input().split())) for i in range(N)]
C,D = zip(*CD)
C = [min(c,mc) for c in C]

for i in range(1,N+1):
    for c in range(mc+1-C[i]):
        g[(i,c)].append(((i,c+C[i]),D[i]))

S = min(S,mc)
dq = [(0,S,1)]

ans = [[10**15 for j in range(mc+1)] for i in range(N+1)]
while dq:
    t, w, v = heappop(dq)
    if ans[v][w] < t:
        continue
    ans[v][w] = t
    for (nv,nw), nt in g[(v,w)]:
        if ans[nv][nw] > t + nt:
            heappush(dq,(t+nt,nw,nv))

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

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from heapq import heappop, heappush,heapify
import sys
input = sys.stdin.buffer.readline

N,M,S = map(int,input().split())
UVAB = [list(map(int,input().split())) for i in range(M)]
U,V,A,B = zip(*UVAB)
mc = max(A)* M
g = defaultdict(list)

for u,v,a,b in UVAB:
    for i in range(a,mc+1):
        g[(u,i)].append(((v,i-a),b))
        g[(v,i)].append(((u,i-a),b))
CD = [[0,0]] + [list(map(int,input().split())) for i in range(N)]
C,D = zip(*CD)

for i in range(1,N+1):
    for c in range(mc+1-C[i]):
        g[(i,c)].append(((i,c+C[i]),D[i]))

S = min(S,mc)
dq = [(0,1,S)]

ans = [[10**15 for j in range(mc+1)] for i in range(N+1)]
while dq:
    t, v, w = heappop(dq)
    if ans[v][w] < t:
        continue
    ans[v][w] = t
    for (nv,nw), nt in g[(v,w)]:
        if ans[nv][nw] > t + nt:
            heappush(dq,(t+nt,nv,nw))

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

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
sysread = sys.stdin.readline
from heapq import heappop, heappush

def run():
    # import sys
    # A = list(map(int, sys.stdin.readline().split()))
    # all = sys.stdin.readlines()
    # all = list(map(int, sys.stdin.read().split())
    #N, *A = map(int, open(0))
    #N = int(input())
    N, M, S = list(map(int, sysread().split()))
    to = [[] for _ in range(N+1)]
    for _ in range(M):
        u,m,a,b = list(map(int, sysread().split()))
        to[u].append((m,b,a))
        to[m].append((u,b,a))

    CD = [[0,0]]
    for _ in range(N):
        c,d = list(map(int, sysread().split()))
        CD.append([c,d])

    queue = []
    # (time, node, rest-coin)
    heappush(queue, (0, 1, S))

    min_times = [float('inf') for _ in range(N+1)]
    nodes = [0 for _ in range(N)]

    while nodes:
        time, node, coin = heappop(queue)
        if min_times[node] == float('inf'):
            min_times[node] = time
            nodes.pop()
        c, d = CD[node]
        heappush(queue, (time+d, node, coin+c))
        for n_node, n_time, n_coin in to[node]:
            if coin < n_coin:
                continue
            else:
                heappush(queue, (time + n_time, n_node, coin - n_coin))
    for s in min_times[2:]:
        print(s)

if __name__ == "__main__":
    run()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from heapq import heappop, heappush,heapify
import sys
input = sys.stdin.buffer.readline

N,M,S = map(int,input().split())
UVAB = [list(map(int,input().split())) for i in range(M)]
U,V,A,B = zip(*UVAB)
mc = max(A)* M
g = defaultdict(list)

for u,v,a,b in UVAB:
    for i in range(a,mc+1):
        g[(u,i)].append(((v,i-a),b))
        g[(v,i)].append(((u,i-a),b))
CD = [[0,0]] + [list(map(int,input().split())) for i in range(N)]
C,D = zip(*CD)

for i in range(1,N+1):
    for c in range(mc+1-C[i]):
        g[(i,c)].append(((i,c+C[i]),D[i]))

S = min(S,mc)
dq = [(0,1,S)]
heapify(dq)

ans = [[10**15 for j in range(mc+1)] for i in range(N+1)]
while dq:
    t, v, w = heappop(dq)
    if ans[v][w] < t:
        continue
    ans[v][w] = t
    for (nv,nw), nt in g[(v,w)]:
        if ans[nv][nw] > t + nt:
            heappush(dq,(t+nt,nv,nw))

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

Submission status: Time Limit Exceeded

Solution code:
# E - Two Currencies

n, m, s = map(int, input().split())
edge = []
for i in range(m):
    u, v, a, b = map(int, input().split())
    edge.append((u, v, a, b)) # from, to, 料金, 時間
exch = {}
for u in range(1, n+1):
    c, d = map(int, input().split())
    exch[u] = (c, d) # レート, 時間

# 料金の総和
max_silver = sum(a for u, v, a, b in edge)
s = min(s, max_silver) # max_silverまでで十分

# (都市,銀貨)を頂点とする最短経路問題
# Bellman-Ford
dist = {(1, s): 0}
for i in range(n * max_silver):
    for e in edge:
        u, v, a, b = e
        for sil in range(a, max_silver+1):
            xsil = sil - a
            if (u, sil) in dist:
                if (v, xsil) not in dist or \
                    dist[(v, xsil)] > dist[(u, sil)] + b:
                    dist[(v, xsil)] = dist[(u, sil)] + b
            if (v, sil) in dist:
                if (u, xsil) not in dist or \
                    dist[(u, xsil)] > dist[(v, sil)] + b:
                    dist[(u, xsil)] = dist[(v, sil)] + b
    for u in range(1, n+1):
        for sil in range(0, max_silver+1):
            c, d = exch[u]
            xsil = min(sil + c, max_silver)
            if (u, sil) in dist:
                if (u, xsil) not in dist or \
                    dist[(u, xsil)] > dist[(u, sil)] + d:
                    dist[(u, xsil)] = dist[(u, sil)] + d

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

Submission status: Time Limit Exceeded

Solution code:
n, m, s = map(int, input().split())
uvab = [list(map(int, input().split())) for _ in range(m)]
cd = [list(map(int, input().split())) for _ in range(n)]


import math

M = 50 * n + 1
s = min(s, M - 1)

dp = [[float('inf')] * M for _ in range(n)]

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

while True:
    flag = False

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

            c, d = cd[v][0], cd[v][1]
            for jj in range(c, M):
                tmp = dp[v][jj - c] + d
                if tmp < dp[v][jj]:
                    dp[v][jj] = tmp
                    flag = True

    if flag == False:
        break

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

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from heapq import heappop, heappush
import sys
input = sys.stdin.buffer.readline
N,M,S = map(int,input().split())
UVAB = [list(map(int,input().split())) for i in range(M)]
U,V,A,B = zip(*UVAB)
mc = max(A)* M
g = defaultdict(list)

for u,v,a,b in UVAB:
    for i in range(a,mc+1):
        g[(u,i)].append(((v,i-a),b))
        g[(v,i)].append(((u,i-a),b))
CD = [[0,0]] + [list(map(int,input().split())) for i in range(N)]
C,D = zip(*CD)

for i in range(1,N+1):
    for c in range(mc+1-C[i]):
        g[(i,c)].append(((i,c+C[i]),D[i]))

S = min(S,mc)
dq = [((1,S),0)]

ans = [[10**15 for j in range(mc+1)] for i in range(N+1)]
while dq:
    (v, w), t = heappop(dq)
    if ans[v][w] < t:
        continue
    ans[v][w] = t
    for (nv,nw), nt in g[(v,w)]:
        if ans[nv][nw] > ans[v][w] + nt:
            ans[nv][nw] = ans[v][w] + nt 
            heappush(dq,((nv,nw),t+nt))

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

Submission status: Time Limit Exceeded

Solution code:
# E - Two Currencies

n, m, s = map(int, input().split())
#adj = {u: [] for u in range(1, n+1)}
edge = []
max_silver = 0
for i in range(m):
    u, v, a, b = map(int, input().split())
    #adj[u].append((v, a, b)) # 行き先, 料金, 時間
    #adj[v].append((u, a, b))
    edge.append((u, v, a, b)) # from, to, 料金, 時間
    max_silver += a # 料金の総和
exch = {}
max_rate = 0
for u in range(1, n+1):
    c, d = map(int, input().split())
    exch[u] = (c, d) # レート, 時間
    max_rate = max(max_rate, c)
max_silver += max_rate - 1
s = min(s, max_silver)

# (都市,銀貨)を頂点とする最短経路問題

dist = {(1, s): 0}
for i in range(n * max_silver):
    for e in edge:
        u, v, a, b = e
        for sil in range(a, max_silver+1):
            if (u, sil) in dist:
                if (v, sil - a) not in dist or \
                    dist[(v, sil - a)] > dist[(u, sil)] + b:
                    dist[(v, sil - a)] = dist[(u, sil)] + b
            if (v, sil) in dist:
                if (u, sil - a) not in dist or \
                    dist[(u, sil - a)] > dist[(v, sil)] + b:
                    dist[(u, sil - a)] = dist[(v, sil)] + b
    for u in range(1, n+1):
        for sil in range(0, max_silver+1):
            c, d = exch[u]
            if (u, sil) in dist:
                if (u, sil + c) not in dist or \
                    dist[(u, sil + c)] > dist[(u, sil)] + d:
                    dist[(u, sil + c)] = dist[(u, sil)] + d

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

Submission status: Time Limit Exceeded

Solution code:
n,m,s=map(int,input().split())
s=min(s,2500)
edge=[[] for i in range(n*50*51)]
for i in range(m):
    u,v,a,b=map(int,input().split())
    for j in range(a,2501):
        edge[u-1+j*n].append((v-1+(j-a)*n,b))
        edge[v-1+j*n].append((u-1+(j-a)*n,b))
for i in range(n):
    c,d=map(int,input().split())
    for j in range(2501-c):
        edge[i+j*n].append((i+(j+c)*n,d))
    for j in range(2500):
        edge[i+(j+1)*n].append((i+j*n,0))
from heapq import heappush,heappop,heapify
d = [float('inf') for i in range(n*50*51)]
pq = []
heappush(pq,(0,s*n))
while pq:
    weight,u = heappop(pq)
    if d[u]>weight:
        d[u]=weight
        for v,weight in edge[u]:
            heappush(pq,(d[u]+weight,v))
for i in range(1,n):
    print(d[i])

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from heapq import heappop, heappush
import sys
input = sys.stdin.buffer.readline
N,M,S = map(int,input().split())
UVAB = [list(map(int,input().split())) for i in range(M)]
A = {}
B = {}
g = defaultdict(list)
for u,v,a,b in UVAB:
    A[(u+v,u*v)] = a
    B[(u+v,u*v)] = b
mc = max(A.values())* M
for u,v,a,b in UVAB:
    for i in range(a,mc+1):
        g[(u,i)].append(((v,i-a),b))
        g[(v,i)].append(((u,i-a),b))
CD = [[0,0]] + [list(map(int,input().split())) for i in range(N)]
C,D = zip(*CD)

for i in range(1,N+1):
    for c in range(mc+1-C[i]):
        g[(i,c)].append(((i,c+C[i]),D[i]))

S = min(S,mc)
dq = [((1,S),0)]

ans = [[10**15 for j in range(mc+1)] for i in range(N+1)]
while dq:
    (v, w), t = heappop(dq)
    if ans[v][w] < t:
        continue
    ans[v][w] = t
    for (nv,nw), nt in g[(v,w)]:
        if ans[nv][nw] > ans[v][w] + nt:
            ans[nv][nw] = ans[v][w] + nt 
            heappush(dq,((nv,nw),t+nt))

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

Submission status: Time Limit Exceeded

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

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

sys.setrecursionlimit(10**9)

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


INF = 10**18

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


if __name__ == "__main__":
    main()