Problem:


Score : 500 points

Problem Statement

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

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

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

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

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

Constraints

2 \leq N \leq 50

N-1 \leq M \leq 100

0 \leq S \leq 10^9

1 \leq A_i \leq 50

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

1 \leq U_i < V_i \leq N

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

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

All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

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

Sample Output 1

2
14

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

In this figure, each city is labeled as follows:

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

The second line: C_i / D_i

Similarly, each railroad is labeled as follows:

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

The second line: A_i / B_i

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

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

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

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

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

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

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

Sample Input 2

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

Sample Output 2

5
5
7

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

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

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

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

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

Sample Input 3

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

Sample Output 3

1
9003
14606
16510
16576

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Sample Input 4

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

Sample Output 4

1
3
5

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

Sample Input 5

2 1 0
1 2 1 1
1 1000000000
1 1

Sample Output 5

1000000001

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

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

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

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



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


Sample output:
2
14

Submission status: Wrong Answer

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

n, m, s = map(int,input().split())
A = [list(map(int,input().split())) for i in range(m)]
C = [list(map(int,input().split())) for i in range(n)]


for i in range(m):  # ノード番号が1始まりで与えられている場合
    for j in range(2):
        A[i][j] -= 1

M = [[[float("inf") for _ in range(5)] for j in range(n)] for i in range(n)]

for i in range(n):
    for j in range(n):
        M[i][j][3] = 0
        M[i][j][4] = 0

for i in range(n):
    M[i][i] = [0,0,0,0,0]
M[0][0][3] = s

for i in range(m):
    aa = A[i][0]
    bb = A[i][1]
    ss = s if A[i][0] == 0 else 0
    M[A[i][0]][A[i][1]] = [A[i][2], A[i][3], max(0, ((A[i][2]-ss+C[aa][0]-1) // C[aa][0]) * C[aa][1]), ss, max(0, ss-A[i][2])]  # 辺の重み付け
    ss = s if A[i][1] == 0 else 0
    M[A[i][1]][A[i][0]] = [A[i][2], A[i][3], max(0, ((A[i][2]-ss+C[bb][0]-1) // C[bb][0]) * C[bb][1]), ss, max(0, ss-A[i][2])]
    # [運賃の合計, 乗車時間の合計, 両替時間の合計]

# print(M)

for kk in range(2*n+2):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                sa = M[i][k][0] + M[k][j][0]
                si = M[i][k][3]
                sj = M[i][k][4]
                if M[i][j][1] + M[i][j][2] > M[i][k][1] + M[k][j][1] + max(0, ((sa-si+C[i][0]-1) // C[i][0]) * C[i][1]):
                    M[i][j] = [sa, M[i][k][1] + M[k][j][1], max(0, ((sa-si+C[i][0]-1) // C[i][0]) * C[i][1]), M[i][k][3], max(0, si-sa)]
                    # print(k,i, j,0, M)

                if M[i][j][1] + M[i][j][2] > M[i][k][1] + M[k][j][1] + M[i][k][2] + max(0, ((M[k][j][0]-sj+C[k][0]-1) // C[k][0]) * C[k][1]):
                    M[i][j] = [sa, M[i][k][1] + M[k][j][1], M[i][k][2] + max(0, ((M[k][j][0]-sj+C[k][0]-1) // C[k][0]) * C[k][1]), M[i][k][3], max(0, sj-M[k][j][0])]
                    # print(k,i, j,1, M)

                # if M[i][j][1] + M[i][j][2] > M[i][k][1] + M[k][j][1] + M[k][j][2] + max(0, ((M[i][k][0]-si+C[i][0]-1) // C[i][0]) * C[i][1]):
                #     M[i][j] = [sa, M[i][k][1] + M[k][j][1], M[k][j][2] + max(0, ((M[i][k][0]-si+C[i][0]-1) // C[i][0]) * C[i][1]), M[i][k][3], max(0, si-M[i][k][0])]
                    # print(k,i, j,1, M)
                if M[i][j][1] + M[i][j][2] > M[i][k][1] + M[k][j][1] + M[i][k][2] + M[k][j][2]:
                    M[i][j] = [sa, M[i][k][1] + M[k][j][1], M[i][k][2] + M[k][j][2], M[i][k][3], M[k][j][4]]
                    # print(k,i, j,1, M)


for i in range(1, n):
    print(M[0][i][1] + M[0][i][2])
# print(M)

Submission status: Wrong Answer

Solution code:
if __name__ == '__main__':
    from sys import stdin
    input = stdin.readline

    # from collections import defaultdict

    INFTY = 2**21
    WHITE = 0
    GRAY = 1
    BLACK = 2

    n, m, s = map(int, input().split())
    M = [[INFTY]*n for _ in range(n)]
    for _ in range(m):
        u, v, a, b = map(int, input().split())
        M[u-1][v-1] = (a, b)
        M[v-1][u-1] = (a, b)

    cds = [0]*n
    
    for i in range(n):
        c, d = map(int, input().split())
        cds[i] = (c, d)

    def dijkstra():
        def get_minute(u, v):
            min_minute = INFTY
            sc_coin = total_coin[u]+M[u][v][0]-s
            if sc_coin <= 0:
                total_coin[u] += M[u][v][0]
                return 0
            for c, d in changes[u]:
                this_coin = ((sc_coin-1)//c)*d
                if min_minute > this_coin:
                    min_minute = this_coin
            return min_minute
        ans = [INFTY]*n
        d = [INFTY]*n
        total_coin = [0]*n
        changes = [[] for _ in range(n)]
        color = [WHITE]*n

        d[0] = 0
        ans[0] = 0
        color[0] = GRAY
        changes[0] = [cds[0]]

        while True:
            minv = INFTY
            u = -1
            for i in range(n):
                if minv > ans[i] and color[i] != BLACK:
                    u = i
                    minv = ans[i]

            if u == -1:
                break
            color[u] = BLACK
            for v in range(n):
                if color[v] != BLACK and M[u][v] != INFTY:
                    needed_minute = get_minute(u, v)
                    if ans[v] > d[u]+M[u][v][1]+needed_minute:
                        ans[v] = d[u] + M[u][v][1]+needed_minute
                        d[v] = d[u] + M[u][v][1]
                        total_coin[v] = total_coin[u] + M[u][v][0]
                        changes[v] = changes[u]+[cds[u]]
                        color[v] = GRAY

        for i in ans[1:]:
            print(i)

        
    dijkstra()

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

def warshall_floyd(n, d):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if i == j:
                    continue
                # j経由でiまで行く
                ret = dfs(i, k, set(), [cd[0]],0 , s)
                d[i][k] = ret[0]
                tmp_trade = ret[1]
                tmp_s = ret[2]
                d[k][j] = dfs(k, j, set(), ret[1], 0, tmp_s)[0]
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
    return d

d = defaultdict(lambda: defaultdict(lambda: INF))
d = warshall_floyd(n, d)
ans = warshall_floyd(n, d)
for i in range(1, n):
    print(ans[0][i])

Submission status: Wrong Answer

Solution code:
import heapq
from copy import deepcopy
def dijkstra(graph,start,cd):
    dist = [float("inf") for _ in range(n)]
    
    
    q = []
    h = cd[start]
    
    heapq.heappush(q, (0,start,s,h))
    
    while q:
        
        cost, cur_node,have,coin = heapq.heappop(q)
        
        if dist[cur_node] < cost:
            continue
        
        for nex_node,nex_cost,nex_time  in graph[cur_node]:

            if nex_cost > have:
                d = (nex_cost-have+coin[1]-1)//coin[1]
                now_time  = cost + d*coin[2] + nex_time
                now_coin = d*coin[1]+have-nex_cost
            else:
                now_time = cost + nex_time
                now_coin = have-nex_cost

            if now_time < dist[nex_node]:
                dist[nex_node] = now_time
                if cd[nex_node][0] < coin[0]:
                    heapq.heappush(q, (dist[nex_node], nex_node,now_coin,cd[nex_node]))
                else:
                    heapq.heappush(q, (dist[nex_node], nex_node,now_coin,coin))
    for i in dist[1:]:
        print(i)
n,m,s = map(int,input().split())
E = [[] for i in range(n)]
for i in range(m):
    u,v,a,b = map(int,input().split())
    u -= 1
    v-= 1
    E[u].append((v,a,b))
    E[v].append((u,a,b))

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

dijkstra(E,0,cd)

Submission status: Wrong Answer

Solution code:
import heapq

def dijkstra(s):
    dist = [inf] * n
    cost = [inf] * n
    dist[s] = 0
    cost[s] = 0
    c = [0] * n
    p = []
    heapq.heapify(p)
    heapq.heappush(p, (dist[s], s))
    while p:
        d, u = heapq.heappop(p)
        if dist[u] < d:
            continue
        c[u] = 1
        for g in G[u]:
            if c[g[0]] == 0 and dist[u] + g[1] < dist[g[0]]:
                dist[g[0]] = dist[u] + g[1]
                cost[g[0]] = cost[u] + g[2]
                heapq.heappush(p, (dist[g[0]], g[0]))
    return [dist, cost]

n, m, s = map(int, input().split())
inf = 1145141919810893
G = [[] * (n + 1) for _ in range(n)]
x = [list(map(int, input().split())) for _ in range(m)]
c = [list(map(int, input().split())) for _ in range(n)]
for t in x:
    G[t[0] - 1].append([t[1] - 1, t[3], t[2]])
    G[t[1] - 1].append([t[0] - 1, t[3], t[2]])
d = [dijkstra(i) for i in range(n)]
ans = [inf] * (n - 1)
for i in range(1, n):
    for j in range(n):
        dist0 = d[0][0][j] + d[j][0][i]
        if d[0][1][j] <= s:
            ss = d[0][1][j] + d[j][1][i] - s
            if ss % c[j][0] == 0:
                dist0 += (ss // c[j][0]) * c[j][1]
            else:
                dist0 += ((ss // c[j][0]) + 1) * c[j][1]
            ans[i - 1] = min(ans[i - 1], dist0)
for i in ans:
    print(i)

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)):
        dp[0][i] = 0
    c,d = Silver[0]
    for i in range(min(s + 1,MAXS),MAXS):
        dp[0][i] = d*((i - s + c - 1)//c)
    
    q = deque([0])
    while q:
        i = q.popleft()
        c,d = Silver[i]
        for e,a,b in G[i]:
            flag = False
            for s in range(MAXS - 1,-1,-1):
                if s - a >= 0:
                    if dp[e][s - a] > dp[i][s] + b:
                        dp[e][s - a] = dp[i][s] + b
                        flag = True
                else:
                    k = (a - s + c - 1)//c
                    while s - a + k*c <= MAXS:
                        if dp[e][s - a + k*c] > dp[i][s] + b + k*d:
                            dp[e][s - a + k*c] = dp[i][s] + b + k*d
                            flag = True
                        k += 1
            if flag:
                q.append(e)
    #print(dp)
    for i in range(1,n):
        ans = min(dp[i])
        print(ans)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
from heapq import *
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**16
    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))
    fin=[False]*n
    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:
MOD = 10 ** 9 + 7
INF = 10 ** 13
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 = 1
    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)):
        dp[0][i] = 0
    c,d = Silver[0]
    for i in range(min(s + 1,MAXS),MAXS):
        dp[0][i] = d*((i - s + c - 1)//c)
    
    q = deque([0])
    while q:
        i = q.popleft()
        c,d = Silver[i]
        for e,a,b in G[i]:
            flag = False
            for s in range(MAXS - 1,-1,-1):
                if s - a >= 0:
                    if dp[e][s - a] > dp[i][s] + b:
                        dp[e][s - a] = dp[i][s] + b
                        flag = True
                else:
                    k = (a - s + c - 1)//c
                    while s - a + k*c <= MAXS:
                        if dp[e][s - a + k*c] > dp[i][s] + b + k*d:
                            dp[e][s - a + k*c] = dp[i][s] + b + k*d
                            flag = True
                        k += 1
            if flag:
                q.append(e)
    #print(dp)
    for i in range(1,n):
        ans = min(dp[i])
        print(ans)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

n, m, s = map(int,input().split())
A = [list(map(int,input().split())) for i in range(m)]
C = [list(map(int,input().split())) for i in range(n)]


for i in range(m):  # ノード番号が1始まりで与えられている場合
    for j in range(2):
        A[i][j] -= 1

M = [[[float("inf") for _ in range(5)] for j in range(n)] for i in range(n)]

for i in range(n):
    for j in range(n):
        M[i][j][3] = 0
        M[i][j][4] = 0

for i in range(n):
    M[i][i] = [0,0,0,0,0]
M[0][0][3] = s

for i in range(m):
    aa = A[i][0]
    bb = A[i][1]
    ss = s if A[i][0] == 0 else 0
    M[A[i][0]][A[i][1]] = [A[i][2], A[i][3], max(0, ((A[i][2]-ss+C[aa][0]-1) // C[aa][0]) * C[aa][1]), ss, max(0, ss-A[i][2])]  # 辺の重み付け
    ss = s if A[i][1] == 0 else 0
    M[A[i][1]][A[i][0]] = [A[i][2], A[i][3], max(0, ((A[i][2]-ss+C[bb][0]-1) // C[bb][0]) * C[bb][1]), ss, max(0, ss-A[i][2])]
    # [運賃の合計, 乗車時間の合計, 両替時間の合計]

# print(M)

for kk in range(n):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                sa = M[i][k][0] + M[k][j][0]
                si = M[i][k][3]
                sj = M[i][k][4]
                if M[i][j][1] + M[i][j][2] > M[i][k][1] + M[k][j][1] + max(0, ((sa-si+C[i][0]-1) // C[i][0]) * C[i][1]):
                    M[i][j] = [sa, M[i][k][1] + M[k][j][1], max(0, ((sa-si+C[i][0]-1) // C[i][0]) * C[i][1]), M[i][k][3], max(0, si-sa)]
                    # print(k,i, j,0, M)

                if M[i][j][1] + M[i][j][2] > M[i][k][1] + M[k][j][1] + M[i][k][2] + max(0, ((M[k][j][0]-sj+C[k][0]-1) // C[k][0]) * C[k][1]):
                    M[i][j] = [sa, M[i][k][1] + M[k][j][1], M[i][k][2] + max(0, ((M[k][j][0]-sj+C[k][0]-1) // C[k][0]) * C[k][1]), M[i][k][3], max(0, sj-M[k][j][0])]
                    # print(k,i, j,1, M)

                if M[i][j][1] + M[i][j][2] > M[i][k][1] + M[k][j][1] + M[i][k][2] + M[k][j][2]:
                    M[i][j] = [sa, M[i][k][1] + M[k][j][1], M[i][k][2] + M[k][j][2], M[i][k][3], M[k][j][4]]
                    # print(k,i, j,1, M)


for i in range(1, n):
    print(M[0][i][1] + M[0][i][2])
# print(M)