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 bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

def dijkstra(s,n):
    hq = [(0, s)]
    heapq.heapify(hq) # リストを優先度付きキューに変換
    cost = [float('inf')] * n # 行ったことのないところはinf
    cost[s] = 0 # 開始地点は0
    while hq:
        c, v = heapq.heappop(hq)
        if c > cost[v]: # コストが現在のコストよりも高ければスルー
            continue
        for d, u in e[v]:
            tmp = d + cost[v]
            if tmp < cost[u]:
                cost[u] = tmp
                heapq.heappush(hq, (tmp, u))
    return cost


e = [[] for _ in range(1000*(n+1))]
for i in range(n):
    c,d=cd[i]
    for j in range(250):
        e[1000*i+j].append((d,1000*i+min(j+c,250)))
    
for i in range(m):
    u,v,a,b=uvab[i]
    u,v = u-1, v-1
    for j in range(250):
        if j-a>=0:
            e[1000*v+j].append((b,1000*u+j-a))
            e[1000*u+j].append((b,1000*v+j-a))
# print(e)
s=min(249,s)
# print(s)
lst=dijkstra(s,1000*(n+1))
# print(lst)
for i in range(1,n):
    ans=float('inf')
    for j in range(250):
        ans=min(ans,lst[1000*i+j])
    print(ans)

Submission status: Wrong Answer

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)]
g=[[] for _ in range(n)]
for u,v,a,b in uvab:
    u,v=u-1,v-1
    g[u].append([v,a,b])
    g[v].append([u,a,b])

#「現在いる頂点、現在持っている銀貨枚数」を頂点とし、ダイクストラ法でとく。
from heapq import heappop,heappush
inf=float('inf')
ans=[[inf]*501 for _ in range(n)]
s=min(s,500)
todo=[[0,0,s]]
ans[0][s]=0
while todo:
    t,v,ss=heappop(todo)
    if ans[v][ss]<t:continue
    for nv,na,nb in g[v]:
        if na>ss:continue
        if ans[nv][ss-na]>t+nb:
            heappush(todo,[t+nb,nv,ss-na])
            ans[nv][ss-na]=t+nb
    if ans[v][min(ss+cd[v][0],500)]>t+cd[v][1]:
        heappush(todo,[t+cd[v][1],v,min(ss+cd[v][0],500)])
        ans[v][min(ss+cd[v][0],500)]=t+cd[v][1]
for i in range(1,n):
    print(min(ans[i]))

Submission status: Wrong Answer

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)]
g=[[] for _ in range(n)]
for u,v,a,b in uvab:
    u,v=u-1,v-1
    g[u].append([v,a,b])
    g[v].append([u,a,b])

#「現在いる頂点、現在持っている銀貨枚数」を頂点とし、ダイクストラ法でとく。
from heapq import heappop,heappush
inf=float('inf')
ans=[[inf]*501 for _ in range(n)]
s=min(s,500)
todo=[[0,0,s]]
ans[0][s]=0
while todo:
    t,v,ss=heappop(todo)
    if ans[v][ss]<t:continue
    for nv,na,nb in g[v]:
        if na>ss:continue
        if ans[nv][ss-na]>t+nb:
            heappush(todo,[t+nb,nv,ss-na])
            ans[nv][ss-na]=t+nb
    if ss+cd[v][0]<501 and ans[v][ss+cd[v][0]]>t+cd[v][1]:
        heappush(todo,[t+cd[v][1],v,ss+cd[v][0]])
        ans[v][ss+cd[v][0]]=t+cd[v][1]
for i in range(1,n):
    print(min(ans[i]))

Submission status: Wrong Answer

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)]
g=[[] for _ in range(n)]
for u,v,a,b in uvab:
    u,v=u-1,v-1
    g[u].append([v,a,b])
    g[v].append([u,a,b])

#「現在いる頂点、現在持っている銀貨枚数」を頂点とし、ダイクストラ法でとく。
from heapq import heappop,heappush
inf=float('inf')
ans=[[inf]*251 for _ in range(n)]
s=min(s,250)
todo=[[0,0,s]]
ans[0][s]=0
while todo:
    t,v,ss=heappop(todo)
    if ans[v][ss]<t:continue
    for nv,na,nb in g[v]:
        if na>ss:continue
        if ans[nv][ss-na]>t+nb:
            heappush(todo,[t+nb,nv,ss-na])
            ans[nv][ss-na]=t+nb
    if ss+cd[v][0]<251 and ans[v][ss+cd[v][0]]>t+cd[v][1]:
        heappush(todo,[t+cd[v][1],v,ss+cd[v][0]])
        ans[v][ss+cd[v][0]]=t+cd[v][1]
for i in range(1,n):
    print(min(ans[i]))

Submission status: Wrong Answer

Solution code:
import heapq

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

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

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

Submission status: Wrong Answer

Solution code:
from heapq import heappush,heappop

N,M,S=map(int,input().split())
edges = [tuple(map(int,input().split())) for _ in range(M)]
cd = [tuple(map(int,input().split())) for _ in range(N)]
INF= 10**12
mod=55

mmax = sum([edges[i][2] for i in range(M)])
if S>mmax:
  S = mmax

G=[{} for _ in range((mmax+1)*mod+N+1)]
for i in range(M):
  u,v,a,b=edges[i]
  for p in range(a,mmax+1):
    G[u+p*mod][v+(p-a)*mod] = b
    G[v+p*mod][u+(p-a)*mod] = b
    
for i in range(N):
  c,d=cd[i]
  for p in range(mmax+1-c):
    G[i+1+p*mod][i+1+(p+c)*mod] = d
    
def dijkstra(start = 0):
    
    d = [INF for i in range(len(G)+1)]
    d[start] = 0
    
    que = []
    heappush(que, (0, start))

    while len(que):
        p = heappop(que)
        v = p[1]
        
        if d[v] < p[0]:
            continue
            
        for u in G[v].keys():
            if d[u] > d[v] + G[v][u]:
                d[u] = d[v] + G[v][u]
                heappush(que, (d[u], u))
    
    return d
  
start = 1+S*mod
d = dijkstra(start)

ans=[INF]*(N+1)
for i in range(2,len(G)+1):
  v = i%mod
  if v>N:continue
  ans[v] = min(ans[v],d[i])
  
print(*ans[2:])

Submission status: Wrong Answer

Solution code:
class Graph:
    class Edge:
        def __init__(self, to, cost, fare):
            """
            :param to:  終点ノード
            :param cost: 辺の重み
            """
            self.to, self.cost, self.fare = to, cost, fare

    def __init__(self, n, directed=False, decrement=True, edges=[]):
        self.n = n
        self.directed = directed
        self.decrement = decrement
        self.edges = [[] for _ in range(self.n)]
        self.parent = [-1]*self.n
        self.info = [-1]*self.n
        self.fare_max = 0
        for x, y, cost, fare in edges:
            self.add_edge(x, y, cost, fare)
            if fare > self.fare_max:
                self.fare_max = fare

    def add_edge(self, x, y, cost, fare):
        if self.decrement:
            x -= 1
            y -= 1
        self.edges[x].append(self.Edge(y, cost, fare))
        if self.directed == False:
            self.edges[y].append(self.Edge(x, cost, fare))
        if fare > self.fare_max:
            self.fare_max = fare

    def dijkstra(self, start, S, INF=10**18):
        """
        :param start: スタート地点
        :return: スタート地点から各点への距離のリスト
        備考: heqpq の比較のための key は第一引数である点に注意（ =　heappush(heapq, (key,value))　）
        """
        res = [[INF] * (self.fare_max*self.n+1) for _ in  range(self.n)]
        if self.decrement:
            start -= 1
        money = S%(self.fare_max*(self.n-1)+1)
        res[start][money] = 0
        next_set = [(0, start, money)]
        while next_set:
            dist, p, money = heappop(next_set)
            if res[p][money] < dist:
                continue
            if money <= self.fare_max*(self.n - 1):
                heappush(next_set, (dist + D[p], p, (money + C[p])%(self.fare_max*(self.n-1)+1)))
            for edge in self.edges[p]:
                q, cost, fare = edge.to, edge.cost, edge.fare
                temp_d = dist + cost
                if temp_d < res[q][money-fare] and money >= fare:
                    res[q][money-fare] = temp_d
                    heappush(next_set, (temp_d, q, money - fare))
        if self.decrement:
            return [[0]] + res
        else:
            return res

##############################################################################################################

import sys
input = sys.stdin.readline
from heapq import *
INF = 10**18  # 大きい数字

C, D = [], []
N, M, S = map(int, input().split())

graph = Graph(N, directed=False, decrement=True)
for _ in range(M):
    x, y, fare, cost = map(int, input().split())
    graph.add_edge(x, y, cost, fare)
for _ in range(N):
    c, d = map(int, input().split())
    C.append(c)
    D.append(d)
d = graph.dijkstra(1,S,INF=INF)
for i in range(2,N+1):
    print(min(d[i]))

Submission status: Wrong Answer

Solution code:
import heapq
import collections


def main():
    INF = 10 ** 12
    # Load data
    N, M, S = list(map(int, input().split()))
    SUM_A = 0
    A = [[INF for _ in range(N)] for _ in range(N)]  # fare
    B = [[INF for _ in range(N)] for _ in range(N)]  # time
    C = [0 for _ in range(N)]  # silver coins per 1 gold coin
    D = [0 for _ in range(N)]  # time per 1 gold coin
    ADJ = collections.defaultdict(list)
    for _ in range(M):
        u, v, a, b = list(map(int, input().split()))
        u -= 1
        v -= 1
        A[u][v] = a
        A[v][u] = a
        B[u][v] = b
        B[v][u] = b
        ADJ[u].append(v)
        ADJ[v].append(u)
        SUM_A += a
    S = min(SUM_A, S)  # SUM_A だけ銀貨があればどこへでも無条件で移動可能
    for n in range(N):
        c, d = list(map(int, input().split()))
        C[n] = c
        D[n] = d
    # 「都市 i で銀貨 s 枚所持」を1ノードと考え、
    # 初期状態 (0, S) からの最短距離（時間）をDijkstraで求める
    arr_dist = [[INF for _ in range(SUM_A + 1)] for _ in range(N)]
    arr_dist[0][S] = 0
    que = [(0, 0, S)]  # (距離, 都市, 銀貨)
    while len(que) > 0:
        dist, city, silver = heapq.heappop(que)
        # same city (next_city == city)
        next_silver, next_dist = silver + C[city], dist + D[city]
        if next_silver <= SUM_A and arr_dist[city][next_silver] > next_dist:
            arr_dist[city][next_silver] = next_dist
            heapq.heappush(que, (next_dist, city, next_silver))
        # other city
        for next_city in ADJ[city]:
            next_silver, next_dist = silver - A[city][next_city], dist + B[city][next_city]
            if 0 <= next_silver <= SUM_A and arr_dist[next_city][next_silver] > next_dist:
                arr_dist[next_city][next_silver] = next_dist
                heapq.heappush(que, (next_dist, next_city, next_silver))
    # 最後に都市 i に関連するノードを全部チェックし、最短距離（時間）を出す
    min_dist = [0 for _ in range(N)]
    for city in range(1, N):
        min_dist[city] = min(arr_dist[city])
    for ans in min_dist[1:]:
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import heapq
import collections


def main():
    INF = 10 ** 12
    # Load data
    N, M, S = list(map(int, input().split()))
    SUM_A = 0
    A = [[INF for _ in range(N)] for _ in range(N)]  # fare
    B = [[INF for _ in range(N)] for _ in range(N)]  # time
    C = [0 for _ in range(N)]  # silver coins per 1 gold coin
    D = [0 for _ in range(N)]  # time per 1 gold coin
    ADJ = collections.defaultdict(list)
    for _ in range(M):
        u, v, a, b = list(map(int, input().split()))
        u -= 1
        v -= 1
        A[u][v] = a
        A[v][u] = a
        B[u][v] = b
        B[v][u] = b
        ADJ[u].append(v)
        ADJ[v].append(u)
        SUM_A += a
    MAX_SILVER = N * SUM_A
    S = min(MAX_SILVER, S)  # MAX_SILVERだけあればどこへでも無条件で移動可能
    for n in range(N):
        c, d = list(map(int, input().split()))
        C[n] = c
        D[n] = d
    # 「都市 i で銀貨 s 枚所持」を1ノードと考え、
    # 初期状態 (0, S) からの最短距離（時間）をDijkstraで求める
    arr_dist = [[INF for _ in range(MAX_SILVER + 1)] for _ in range(N)]
    arr_dist[0][S] = 0
    que = [(0, 0, S)]  # (距離, 都市, 銀貨)
    while len(que) > 0:
        dist, city, silver = heapq.heappop(que)
        # same city (next_city == city)
        next_silver, next_dist = silver + C[city], dist + D[city]
        if next_silver <= MAX_SILVER and arr_dist[city][next_silver] > next_dist:
            arr_dist[city][next_silver] = next_dist
            heapq.heappush(que, (next_dist, city, next_silver))
        # other city
        for next_city in ADJ[city]:
            next_silver, next_dist = silver - A[city][next_city], dist + B[city][next_city]
            if 0 <= next_silver <= MAX_SILVER and arr_dist[next_city][next_silver] > next_dist:
                arr_dist[next_city][next_silver] = next_dist
                heapq.heappush(que, (next_dist, next_city, next_silver))
    # 最後に都市 i に関連するノードを全部チェックし、最短距離（時間）を出す
    min_dist = [0 for _ in range(N)]
    for city in range(1, N):
        min_dist[city] = min(arr_dist[city])
    for ans in min_dist[1:]:
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:

from heapq import heappop, heappush

N, M, S = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(M)]
Y = [list(map(int, input().split())) for _ in range(N)]

lim = 2510
graph = [[] for _ in range((N + 1) * lim)]

for u, v, a, b in X:
    for n in range(a, lim):
        graph[u * lim + n].append((v * lim + (n - a), b))
        graph[v * lim + n].append((u * lim + (n - a), b))

for n, (c, d) in enumerate(Y):
    for x in range(lim - 1):
        graph[(n + 1) * lim + x].append(
            ((n + 1) * lim + min(lim - 1, x + c), d))


INF = 10 ** 9 + 7
start = lim + min(S, lim - 1)
dist = [INF] * ((N + 1) * lim + 1)
dist[start] = 0
pq = []
heappush(pq, (0, start))

while pq:
    _, u = heappop(pq)
    for v, c in graph[u]:
        if dist[v] > dist[u] + c:
            dist[v] = dist[u] + c
            heappush(pq, (dist[v], v))

ans = []
for i in range(2, N + 1):
    ans.append(min(dist[i * lim:i * lim + lim]))

print(*ans, sep="\n")

Submission status: Wrong Answer

Solution code:

from heapq import heappop, heappush

N, M, S = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(M)]
Y = [list(map(int, input().split())) for _ in range(N)]

a_max = max(a for *_, a, _ in X)
lim = a_max * (N - 1) + 1
graph = [[] for _ in range((N + 1) * lim)]

for u, v, a, b in X:
    for n in range(a, lim):
        graph[u * lim + n].append((v * lim + (n - a), b))
        graph[v * lim + n].append((u * lim + (n - a), b))

for n, (c, d) in enumerate(Y):
    for x in range(lim - 1):
        graph[(n + 1) * lim + x].append(
            ((n + 1) * lim + min(lim - 1, x + c), d))


INF = 10 ** 9 + 7
start = lim + min(S, lim - 1)
dist = [INF] * ((N + 1) * lim + 1)
dist[start] = 0
pq = []
heappush(pq, (0, start))

while pq:
    _, u = heappop(pq)
    for v, c in graph[u]:
        if dist[v] > dist[u] + c:
            dist[v] = dist[u] + c
            heappush(pq, (dist[v], v))

ans = []
for i in range(2, N + 1):
    ans.append(min(dist[i * lim:i * lim + lim]))

print(*ans, sep="\n")

Submission status: Wrong Answer

Solution code:

from heapq import heappop, heappush

N, M, S = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(M)]
Y = [list(map(int, input().split())) for _ in range(N)]

a_max = max(a for *_, a, _ in X)
lim = a_max * (N - 1) + 1
graph = [[] for _ in range((N + 1) * lim)]

for u, v, a, b in X:
    for n in range(a, lim):
        graph[u * lim + n].append((v * lim + (n - a), b))
        graph[v * lim + n].append((u * lim + (n - a), b))

for n, (c, d) in enumerate(Y):
    for x in range(lim):
        graph[(n + 1) * lim + x].append(
            ((n + 1) * lim + min(lim - 1, x + c), d))


INF = 10 ** 9 + 7
start = lim + min(S, lim - 1)
dist = [INF] * ((N + 1) * lim + 1)
dist[start] = 0
pq = []
heappush(pq, (0, start))

while pq:
    _, u = heappop(pq)
    for v, c in graph[u]:
        if dist[v] > dist[u] + c:
            dist[v] = dist[u] + c
            heappush(pq, (dist[v], v))

ans = []
for i in range(2, N + 1):
    ans.append(min(dist[i * lim:i * lim + lim]))

print(*ans, sep="\n")

Submission status: Wrong Answer

Solution code:

from heapq import heappop, heappush

N, M, S = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(M)]
Y = [list(map(int, input().split())) for _ in range(N)]

a_max = max(a for *_, a, _ in X)
lim = a_max * (N - 1) + 1
graph = [[] for _ in range((N + 1) * lim)]

for u, v, a, b in X:
    for n in range(a, lim):
        graph[u * lim + n].append((v * lim + (n - a), b))
        graph[v * lim + n].append((u * lim + (n - a), b))

for n, (c, d) in enumerate(Y):
    for x in range(lim):
        graph[(n + 1) * lim + x].append(
            ((n + 1) * lim + min(lim - 1, x + c), d))


INF = 10 ** 9 + 7
start = lim + min(S, lim)
dist = [INF] * ((N + 1) * lim + 1)
dist[start] = 0
pq = []
heappush(pq, (0, start))

while pq:
    _, u = heappop(pq)
    for v, c in graph[u]:
        if dist[v] > dist[u] + c:
            dist[v] = dist[u] + c
            heappush(pq, (dist[v], v))

ans = []
for i in range(2, N + 1):
    ans.append(min(dist[i * lim:i * lim + lim]))

print(*ans, sep="\n")

Submission status: Wrong Answer

Solution code:
import heapq
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)

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

inf = 10**18
U = N*50
S = min(S, U)
dist = [[inf] * (U + 1) for _ in range(N)]
dist[0][S] = 0

que = [(0, 0, S)]  # 時間、現在地、銀貨の数
while que:
    time, now, silver = heapq.heappop(que)
    if dist[now][silver] < time:
        continue
    # 両替する
    c, d = CD[now]
    for i in range(1, U + 1):
        if silver + i > U:
            break
        t = (i + c - 1) // c * d
        if dist[now][silver + i] > time + t:
            dist[now][silver + i] = time + t
            heapq.heappush(que, (time + t, now, silver + i))
        else:
            break
    # 移動する
    for nxt, s, t in edge[now]:
        if silver < s:
            continue
        if dist[nxt][silver - s] > time + t:
            dist[nxt][silver - s] = time + t
            heapq.heappush(que, (time + t, nxt, silver - s))

for i in range(1, N):
    print(min(dist[i]))

Submission status: Wrong Answer

Solution code:
import heapq
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)

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

inf = 10**18
U = N*50
S = min(S, U)
dist = [[inf] * (U + 1) for _ in range(N)]
dist[0][S] = 0

que = [(0, 0, S)]  # 時間、現在地、銀貨の数
while que:
    time, now, silver = heapq.heappop(que)
    if dist[now][silver] < time:
        continue
    # 両替する
    c, d = CD[now]
    for i in range(1, U + 1):
        if silver + i > U:
            break
        t = (i + c - 1) // c * d
        if dist[now][silver + i] <= time + t:
            break
        dist[now][silver + i] = time + t
        heapq.heappush(que, (time + t, now, silver + i))

    # 移動する
    for nxt, s, t in edge[now]:
        if silver < s:
            continue
        if dist[nxt][silver - s] > time + t:
            dist[nxt][silver - s] = time + t
            heapq.heappush(que, (time + t, nxt, silver - s))

for i in range(1, N):
    print(min(dist[i]))

Submission status: Wrong Answer

Solution code:
import heapq as hq
n,m,s = list(map(int,input().split()))
G = [[] for _ in range(n)]

for i in range(m):
  u,v,A,B = list(map(int,input().split()))
  u -= 1
  v -= 1
  #hq.heappush(G[u], (B,A,v))
  #hq.heappush(G[v], (B,A,u))
  G[u].append((B,A,v))
  G[v].append((B,A,u))

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

inf = 10**10
M = 50*51
if s > M:s = M-1
dp = [[inf] * M for _ in range(n)] 
cur = 0
dp[cur][s] = 0
que = [(0,s,0)]
while que:
  cd,cs,cur = hq.heappop(que)
  C = c[cur];D = d[cur]
  if dp[cur][cs] < cd:continue
  if cs+C < M and cd+D < dp[cur][cs+C]:
    dp[cur][cs+C] = cd+D
    hq.heappush(que, (cd+D, cs+C, cur))
  for g in G[cur]:
    B = g[0];A = g[1];to = g[2]
    if cs >= A and B+cd < dp[to][cs-A]:
      dp[to][cs-A] = B+cd
      hq.heappush(que, (B+cd, cs-A, to))

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

Submission status: Wrong Answer

Solution code:
import heapq as hq
n,m,s = list(map(int,input().split()))
G = [[] for _ in range(n)]

for i in range(m):
  u,v,A,B = list(map(int,input().split()))
  u -= 1
  v -= 1
  hq.heappush(G[u], (B,A,v))
  hq.heappush(G[v], (B,A,u))
  #G[u].append((B,A,v))
  #G[v].append((B,A,u))

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

inf = 10**10
M = 50*51
if s > M:s = M-1
dp = [[inf] * M for _ in range(n)] 
cur = 0
dp[cur][s] = 0
que = [(0,s,0)]
while que:
  cd,cs,cur = hq.heappop(que)
  C = c[cur];D = d[cur]
  if dp[cur][cs] < cd:continue
  if cs+C < M and cd+D < dp[cur][cs+C]:
    dp[cur][cs+C] = cd+D
    hq.heappush(que, (cd+D, cs+C, cur))
  for g in G[cur]:
    B = g[0];A = g[1];to = g[2]
    if cs >= A and B+cd < dp[to][cs-A]:
      dp[to][cs-A] = B+cd
      hq.heappush(que, (B+cd, cs-A, to))

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

Submission status: Wrong Answer

Solution code:
from heapq import heapify,heappush,heappop
N, M, S = map(int, input().split())

I = [[] for _ in range(N)]#隣接リスト
for i in range(M):
  U, V, A, B = map(int, input().split())
  U -= 1
  V -= 1
  I[U].append((U,A,B))
  I[V].append((V,A,B))

CD = [list(map(int, input().split())) for j in range(N)]
  
task = [] 
used = [0 for _ in range(N)]
min_len = [0 for _ in range(N)]
length = [(10**20,0) for _ in range(N)]
prev_points = [0 for _ in range(N)]
heappush(task, ((0, -S), 0, -1))
print("Yes")

while task:
  while task:
    l, p, prev = heappop(task)    
    if used[p] == 0:
      break
  #print(task)
  used[p] = 1
  min_len[p] = l
  prev_points[p] = prev +1 #番号を1ずらす
  
  for (j, a, b) in I[p]:
    if used[j] == 1: continue
    #print(p,j)
    svr = l[1]
    tm = l[0]
    while -svr < b:
      svr -= C[p]
      tm += N[p]
    l_next = (tm,svr)      
    
    if length[j] > l_next:
      length[j] = l_next
      heappush(task, (l_next, j, p))

"""
for i in range(1, N):
  print(prev_points[i])
"""

for i in range(1, N):
  print(length[i][0])

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, M, S = mapint()
S = min(S, N*50)
query = [[[] for _ in range(N*50+1)] for _ in range(N)]
for _ in range(M):
    u, v, a, b = mapint()
    for coin in range(a, N*50+1):
        query[u-1][coin].append((v-1, a, b))
        query[v-1][coin].append((u-1, a, b))
for i in range(N):
    c, d = mapint()
    for coin in range(N*50+1):
        query[i][coin].append((i, -c, d))

inf = 10**18
dp = [[inf]*(N*50+1) for _ in range(N)]
dp[0][0] = 0

import heapq
queue = [(0, 0, S)]
checked = [0]*N
cnt = 0

while queue:
    t, now, coin = heapq.heappop(queue)
    if cnt==N:
        break
    if not checked[now]:
        checked[now] = 1
        cnt += 1
    qlis = query[now][coin]
    dp[now][coin] = t
    for nx, a, b in qlis:
        if 0<=coin-a:
            coin = min(coin, N*50+a)
            if t+b<dp[nx][coin-a]:
                heapq.heappush(queue, (t+b, nx, coin-a))

for i in range(1, N):
    print(min(dp[i]))

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, M, S = mapint()
query = [[(-1, -1)]*N for _ in range(N)]
for _ in range(M):
    u, v, a, b = mapint()
    query[u-1][v-1] = (a, b)
    query[v-1][u-1] = (a, b)
exchange = [list(mapint()) for _ in range(N)]

dp = [[0]+[-1]*(N*50) for _ in range(N)]

import heapq
queue = [(0, 0)]

while queue:
    t, now = heapq.heappop(queue)
    rate, time = exchange[now]
    for i in range(rate, N*50+1):
        if dp[now][i-rate]!=-1:
            dp[now][i] = min(dp[now][i], dp[now][i-rate]+time)
    for nx in range(N):
        a, b = query[now][nx]
        if a==-1:
            continue

Submission status: Wrong Answer

Solution code:
import sys 
import math
sys.setrecursionlimit(10**6)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N,M,S = map(int,readline().split())
graph = [[] for _ in range(N) ]
exchange = []
for _ in range(M):
    u,v,a,b = map(int,readline().split())
    graph[u-1].append((v-1,a,b))
    graph[v-1].append((u-1,a,b))
for _ in range(N):
    c,d = map(int,readline().split())
    exchange.append((c,d))

min_minute = [float('inf')]*N
reached = [0]
def dfs(v,p,total_s,total_t):
    for x,a,b in graph[v]:
        if x == p:
            continue
        if x in reached:
          continue
        total_s += a  
        total_t += b 
        if S >= total_s:
            min_minute[x] = min(min_minute[x],total_t)
        else:
            t = float('inf')
            for i in reached:
                c,d = exchange[i]
                t = min(t,int(math.ceil(total_s/c))*d)
            min_minute[x] = min(min_minute[x],total_t+t)
        reached.append(x)
        dfs(x,v,total_s,total_t)
        reached.remove(x)
        total_s -= a  
        total_t -= b 

dfs(0,0,0,0)
print(*min_minute[1:])