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

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from heapq import heappush, heappop

N,M,S = map(int,readline().split())
ABC = [list(map(int,readline().split())) for _ in range(M)]
m = map(int,read().split())
CD = list(zip(m,m))

graph = [[] for _ in range(N)]
for u,v,a,b in ABC:
    graph[u-1].append((v-1,a,b))
    graph[v-1].append((u-1,a,b))

def f():
  INF = 10 ** 18
  arrive = [False]*N
  ans = []
  qq = 2500
  dist = [[INF] * qq for _ in range(N)]
  dist[0][min(qq-1,S)] = 0
  q = [(0,min(qq-1,S),0)]
  while q:
      st,ss,v = heappop(q) # 総時間、銀貨、今いる頂点
      if dist[v][ss] < st:
        continue
      if not arrive[v]:
        arrive[v] = True
        ans.append((v,st))
        if all(arrive):
          break
      c,d = CD[v]
      # 銀貨の購入
      if ss < qq-1:
          ns = min(ss + c, qq-1)
          nt = st + d
          if dist[v][ns] > nt:
              dist[v][ns] = nt
              heappush(q,(nt,ns,v))
      # 移動
      for nex,g,tt in graph[v]:
          if ss-g < 0:
              continue
          dt = st + tt
          if dist[nex][ss-g] <= dt:
              continue
          dist[nex][ss-g] = dt
          heappush(q,(dt,ss-g,nex))
  return ans

ab = f()
from operator import itemgetter
ab = sorted(ab,key=itemgetter(0))
for i in range(1,N):
  print(ab[i][1])

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix

N, M, S, *I = map(int, open(0).read().split())
UVAB, CD = I[:4 * M], I[4 * M:]

R, C, V = [], [], []
for u, v, a, b in zip(*[iter(UVAB)] * 4):
    for i in range(2501 - a):
        R += [(i + a) * 51 + u, (i + a) * 51 + v]
        C += [i * 51 + v, i * 51 + u]
        V += [b, b]

for i, (c, d) in enumerate(zip(*[iter(CD)] * 2), 1):
    for j in range(2501 - c):
        R.append(j * 51 + i)
        C.append((j + c) * 51 + i)
        V.append(d)

D = dijkstra(
    csr_matrix((V, (R, C)), [2500 * 60] * 2),
    indices=min(2500, S) * 51 + 1
)

for i in range(2, N + 1):
    print(int(D[i::51].min()))

Submission status: Accepted

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

DEBUG = False
INF = float('inf')
MAX_N = 50
MAX_A = 50

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

connect = [[] for _ in range(N)]
for _ in range(M):
    u, v, a, b = map(int, input().split())
    U.append(u)
    V.append(v)
    A.append(a)
    B.append(b)
    connect[u-1].append([v-1, a, b])
    connect[v-1].append([u-1, a, b])
for _ in range(N):
    c, d = map(int, input().split())
    C.append(c)
    D.append(d)

if DEBUG:
    print("U: {}".format(U))
    print("V: {}".format(V))
    print("A: {}".format(A))
    print("B: {}".format(B))
    print("C: {}".format(C))
    print("D: {}".format(D))
    print("connect: {}".format(connect))

MAX_N = N
MAX_A = max(A)
MAX_MONEY = MAX_N * MAX_A
S = min(S, MAX_MONEY-1)

node = [INF for _ in range(MAX_MONEY * N)]
hq = []
heappush(hq, (0, S))
while hq:
    time, current_node = heappop(hq)
    if DEBUG:
        print("time: {}, current_node: {}, len(hq): {}".format(time, current_node, len(hq)))
    if time < node[current_node]:
        node[current_node] = time
    else:
        continue
    index_city = current_node // MAX_MONEY
    money = current_node % MAX_MONEY
    if DEBUG:
        print("money: {}".format(money))

    for index_next_city, a, b in connect[index_city]:
        if money >= a and time+b < node[index_next_city*MAX_MONEY + money-a]:
            heappush(hq, (time+b, index_next_city*MAX_MONEY + money-a))
    if money < MAX_MONEY-1:
        heappush(hq, (time+D[index_city], min(money+C[index_city], MAX_MONEY-1)+MAX_MONEY*index_city))

for i in range(1,N):
    if DEBUG:
        print("node{}: {}".format(i, node[MAX_MONEY*i:MAX_MONEY*(i+1)]))
    print(min(node[MAX_MONEY*i:MAX_MONEY*(i+1)]))

Submission status: Accepted

Solution code:
import heapq

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

for i in range(M):
    uvab[i][0] -= 1
    uvab[i][1] -= 1

railways = [[] for _ in range(N)]
max_a = 0
for u, v, a, b in uvab:
    railways[u].append((v, a, b))
    railways[v].append((u, a, b))
    max_a = max(max_a, a)
del uvab

max_silver = max_a * (N - 1)

ans = [-1] * N
d = dict()
d[(S, 0)] = 0  # silver, station
Q = [(0, S, 0)]  # time, silver, station
sum_reached = 0
reached = [False] * N

while Q:
    t, sv, st = heapq.heappop(Q)
    if not reached[st]:
        ans[st] = t
        reached[st] = True
        sum_reached += 1
        if sum_reached == N:
            break

    new_key = (min(max_silver, sv + cd[st][0]), st)
    new_value = t + cd[st][1]
    if new_key not in d or d[new_key] > new_value:
        d[new_key] = t + cd[st][1]
        heapq.heappush(Q, (new_value, *new_key))

    for dist, a, b in railways[st]:
        if sv >= a:
            new_key = (sv - a, dist)
            new_value = t + b
            if new_key not in d or d[new_key] > new_value:
                d[new_key] = new_value
                heapq.heappush(Q, (new_value, *new_key))

print(*ans[1:], sep="\n")

Submission status: Accepted

Solution code:
n,m,s=map(int,input().split())
s=min(s,2500)

# 2501×nの[]行列
# 0~2500枚 × 頂点数
edge=[[[] for i in range(50*50+1)] for i in range(n)]

# (頂点, コスト)→(頂点, コスト)へ辺を渡っての遷移（頂点が変わる）
# u,v,a,bが与えられるたびに、edgeを更新
for i in range(m):
    u,v,a,b=map(int,input().split())
    
    # jは、保有銀貨枚数
    # j:a→2500なのは、jがa未満であれば、隣の頂点に行けないから
    for j in range(a,2501):
        edge[u-1][j].append((v-1,j-a,b))
        edge[v-1][j].append((u-1,j-a,b))

# (頂点, コスト)→(頂点, コスト)へ、その頂点に留まって両替の遷移（頂点変わらない）
# c,dが与えられるたびに、edgeを更新
for i in range(n):
    c,d=map(int,input().split())
      
    # 銀貨を捨てるのはノーコスト
    # 2500枚以上持ってたら、2500枚持ってることと同値と考える
    for j in range(2500):
        if j+c>=2500:
            edge[i][j].append((i,2500,d))
        elif j+c<2500:
            edge[i][j].append((i,j+c,d))
        
from heapq import heappush,heappop,heapify

# dはn×2501のすべての状態の最小コストの表
d=[[float('inf')  for i in range(50*50+1)] for i in range(n)]

# 初期値。頂点0, 銀貨Sには、コスト0で到達
d[0][s]=0

pq = []
heappush(pq,(0,0,s))

while len(pq):
    # [コスト, 頂点, 銀貨数]で、コストをkeyとして、heapソートして、一番コストが低いリストを先頭に持ってくる
    _,u,g = heappop(pq)
    
    # 頂点までのコストが更新できれば更新してヒープに登録
    # edge[u][g]は、頂点u, 銀貨g枚の状態から、行ける状態のtuple(頂点, 銀貨数, コスト)を呼び出す
    # pqには、[コスト, 頂点, 銀貨数]の順で入れている
    for tuple in edge[u][g]:
        if d[tuple[0]][tuple[1]]>d[u][g]+tuple[2]:
            d[tuple[0]][tuple[1]]=d[u][g]+tuple[2]
            heappush(pq,[d[u][g]+tuple[2],tuple[0],tuple[1]])
            
# d[i]で、頂点iにおける保有銀貨数に応じたコストが入ったリストを呼び出せる
# リストの中で、一番小さいコストのやつを呼び出せば、その頂点に行ける最小コストと同値である
for i in range(1,n):
    print(min(d[i]))

Submission status: Accepted

Solution code:
from heapq import heappop, heappush
INF = float('inf')

N, M, S = map(int,input().split())
graph = [[] for _ in range(N)]
for _ in range(M):
	U, V, A, B = map(int,input().split())
	graph[U-1].append((V-1, A, B))
	graph[V-1].append((U-1, A, B))

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

def Extdijkstra(start):
    global S
    N_d = len(graph)
    M = 2500

    if S >= M:
        S = M-1
    
    dist = [[INF]*M for _ in range(N_d)]
    dist[start][S] = 0
    q = [(0, S, start)]

    while q:
        d, num, v = heappop(q)
        if num+C[v] < M and d+D[v] < dist[v][num+C[v]]:  # 自己ループ
            dist[v][num+C[v]] = d+D[v]
            heappush(q, (d+D[v], num+C[v], v))
        for node, c, t in graph[v]:
            if num >= c and d + t < dist[node][num-c]:
                dist[node][num-c] = d+t
                heappush(q, (d+t, num-c, node))
    return dist

d = Extdijkstra(0)
for i in range(1, N):
	print(min(d[i]))

Submission status: Accepted

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

def dijkstra(Route,v,start):
    Dist=[float('inf')]*v
    Dist[start]=0
    Visited=[False]*v
    hq=[(0,start)]
    while hq:
        dist,fr=heapq.heappop(hq)
        Visited[fr]=True
        for to,cost in Route[fr]:
            if (not Visited[to]) and Dist[to]>dist+cost:
                Dist[to]=dist+cost
                heapq.heappush(hq,(Dist[to],to))
    return Dist

def main():
    n,m,s=map(int,input().split())
    s_max=2500
    Edges=[[] for _ in range(n*s_max)]
    for _ in range(m):
        u,v,cost,time=map(int,input().split())
        u-=1; v-=1
        for i in range(cost,s_max):
            Edges[u*s_max+i].append((v*s_max+i-cost,time))
            Edges[v*s_max+i].append((u*s_max+i-cost,time))
    Change=[None]*n
    for i in range(n):
        change,time=map(int,input().split())
        for j in range(s_max-change):
            Edges[i*s_max+j].append((i*s_max+j+change,time))
    Dist=dijkstra(Edges,n*s_max,min(s,s_max-1))
    for i in range(1,n):
        print(min(Dist[i*s_max:(i+1)*s_max]))
    
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
from collections import defaultdict
from heapq import heappop, heappush
def resolve():
    N, M, S = lr()
    uvab = [[] for i in range(N)]
    amax = 0
    for i in range(M):
        u, v, a, b = lr()
        uvab[u-1].append([v-1, a, b])
        uvab[v-1].append([u-1, a, b])
        amax = max(amax, a)
    cd = []
    for i in range(N):
        cd.append(lr())
    dp = defaultdict(lambda: float('inf'))
    A = amax*(N-1)
    dp[0, min(S, A)] = 0
    s = [[0, 0, min(S, A)]]
    while len(s) > 0:
        x, u, i  = heappop(s)
        if dp[u, i] != x:
            continue
        c, d = cd[u]
        ni = min(i+c, A)
        if dp[u, ni] > dp[u, i]+d:
            dp[u, ni] = dp[u, i]+d
            heappush(s, [dp[u, ni], u, ni])
        for vab in uvab[u]:
            v, a, b = vab
            if i >= a and i < A and dp[v, i-a] > dp[u, i] + b:
                dp[v, i-a] = dp[u, i] + b
                heappush(s, [dp[v, i-a], v, i-a])
            elif i == A and dp[v, i] > dp[u, i] + b:
                dp[v, i] = dp[u, i] + b
                heappush(s, [dp[v, i], v, i])
    for i in range(1, N):
        ans = float('inf')
        for j in range(A+1):
            ans = min(dp[i, j], ans)
        print(ans)
resolve()

Submission status: Accepted

Solution code:
# snuke解説板
from heapq import heappush, heappop

infi = 10 ** 20
n, m, s = map(int, input().split())

s = min(s, n * 50)

edges = [[] for _ in range(n + 1)]
# edge:1-50, max silver=0-2500

for _ in range(m):  # a円, b分
    u, v, a, b = map(int, input().split())
    edges[v].append((u, a, b))
    edges[u].append((v, a, b))

exchange = [(0, 0)] * (n + 1)

for edge_num in range(1, n + 1):  # c円, d分
    c, d = map(int, input().split())
    exchange[edge_num] = (c, d)

start = 1
# dp[i][j], 頂点iにお金jを持って到達する最低時間→時間に関してDAG
dp = [[infi] * (n * 50 + 1) for _ in range(n + 1)]


def dijkstra(edges, start, s, dp):
    dp[start][s] = 0
    edgelist = []
    heappush(edgelist, (0, s, start))  # 時間, お金, 頂点
    while edgelist:
        nowtime, nowmoney, nowedge = heappop(edgelist)
        # 遷移させる条件はedge,moneyの組み合わせに対してその時の最小値が出てきたときのみ→最小値以外は飛ばす。
        if dp[nowedge][nowmoney] != nowtime:
            continue
        # 両替
        deltamoney, deltatime = exchange[nowedge]
        nextmoney = min(nowmoney + deltamoney, n * 50)
        nexttime = nowtime + deltatime
        if dp[nowedge][nextmoney] > nexttime:
            dp[nowedge][nextmoney] = nexttime
            heappush(edgelist, (nexttime, nextmoney, nowedge))
        # 移動
        for v, vmoney, vtime in edges[nowedge]:
            nexttime = nowtime + vtime
            nextmoney = nowmoney - vmoney
            if nextmoney < 0:
                continue
            if dp[v][nextmoney] > nexttime:
                dp[v][nextmoney] = nexttime
                heappush(edgelist, (nexttime, nextmoney, v))
    return dp


time = dijkstra(edges, start, s, dp)

ans = [infi] * (n + 1)
for i in range(1, n + 1):
    for j in range(n * 50 + 1):
        ans[i] = min(ans[i], dp[i][j])

print(*ans[2 : (n + 1)], sep="\n")

Submission status: Accepted

Solution code:
from heapq import *

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

T = [[10**18 for _ in range(2451)] for _ in range(N)]

act = [[] for _ in range(N)]

for i in range(M):
  U, V, A, B = map(int, input().split())
  U -= 1
  V -= 1
  act[U] += [(V, A, B)]
  act[V] += [(U, A, B)]

for i in range(N):
  C, D = tuple(map(int, input().split()))
  act[i] += [(i, -C, D)]

que = [(0, 0, S)]

while que:
  (currentT, n, coins) = heappop(que)
  for m, cost, t in act[n]:
    # もし「払える金額で」「最小時間T[移動先][所持金]を更新できるとき」に値を更新、キューに状態を追加。
    # 両替の結果2450枚を超えるなら2450枚として扱って問題なし。
    if coins >= cost and currentT + t < T[m][min(2450, coins - cost)]:
      T[m][min(2450, coins - cost)] = currentT + t
      heappush(que, (currentT + t, m, min(2450, coins - cost)))

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

Submission status: Accepted

Solution code:
def Int():
    return int(input())
def Ints():
    return map(int,input().split())
def IntList():
    return list(Ints())
def IntMat(N):
    return [IntList() for i in range(N)]

N,M,S = Ints()
from collections import defaultdict
Graph  = defaultdict(list)

for i in range(M):
    u,v,a,b = Ints()
    Graph[u-1].append([v-1,a,b])
    Graph[v-1].append([u-1,a,b])

City = [0]*N
for i in range(N):
    c,d = Ints()
    City[i] = [c,d]

import heapq
que = []
# [time, nowhere, money, flag, visited]
heapq.heappush(que, [0, 0, min(S,5000)])
ans = [[10**16]*5001 for i in range(N)]
#Min = [[10**16]*5001 for i in range(N+1)]
#print(Graph)
while que != []:
    time, nowhere, money = heapq.heappop(que)
    #print('here',time,nowhere,money)
    if time <= ans[nowhere][money]:
        ans[nowhere][money] = time
        c,d = City[nowhere]
        if time+d < ans[nowhere][min(5000,money+c)]:
            ans[nowhere][min(5000,money+c)] = time+d
            #print('to',time+d, nowhere, min(5000,money+c))
            heapq.heappush(que, [time+d, nowhere, min(5000,money+c)])
        for (to,a,b) in Graph[nowhere]:
            if 0 <= money - a and time+b < ans[to][min(5000,money-a)]:
                ans[to][min(5000,money-a)] = time+b
                #print('to',time+b, to, min(5000,money-a))
                heapq.heappush(que, [time+b, to, min(5000,money-a)])

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

Submission status: Accepted

Solution code:
from heapq import *

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

T = [[10**18 for _ in range(2451)] for _ in range(N)]

act = [[] for _ in range(N)]

for i in range(M):
  U, V, A, B = tuple(map(int, input().split()))
  U -= 1
  V -= 1
  act[U] += [(V, A, B)]
  act[V] += [(U, A, B)]

for i in range(N):
  C, D = tuple(map(int, input().split()))
  act[i] += [(i, -C, D)]

que = [(0, 0, S)]

while que:
  (currentT, n, coins) = heappop(que)
  for m, cost, t in act[n]:
    # もし「払える金額で」「最小時間T[移動先][所持金]を更新できるとき」に値を更新、キューに状態を追加。
    if coins >= cost and currentT + t < T[m][min(2450, coins - cost)]:
      T[m][min(2450, coins - cost)] = currentT + t
      heappush(que, (currentT + t, m, min(2450, coins - cost)))

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N,M,S=map(int,input().split())
    
    X=2500
    edge=[[] for _ in range(N*X)]
    for _ in range(M):
        U,V,A,B=map(int,input().split())
        U-=1
        V-=1
        for i in range(A,X):
            edge[U*X+i].append((B,V*X+i-A))
            edge[V*X+i].append((B,U*X+i-A))
    for i in range(N):
        C,D=map(int,input().split())
        for j in range(X-C):
            edge[i*X+j].append((D,i*X+j+C))

    from heapq import heappop,heappush
    def dijkstra(start,n,edges):
        d=[INF]*n
        used=[False]*n
        d[start]=0
        used[start]=True
        edgelist=[]
        for edge in edges[start]:
            heappush(edgelist,edge)
        while edgelist:
            minedge=heappop(edgelist)
            if used[minedge[1]]:
                continue
            v=minedge[1]
            d[v]=minedge[0]
            used[v]=True
            for edge in edges[v]:
                if not used[edge[1]]:
                    heappush(edgelist,(edge[0]+d[v],edge[1]))
        return d
    
    d=dijkstra(min(S,X-1),N*X,edge)
    for i in range(1,N):
        print(min(d[i*X:(i+1)*X]))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,m,s=map(int,input().split())

# 所持銀が2500超えたら、2500になるまで銀貨捨てる
# 2500枚以上のDP表を作ると、かなりのメモリ消費するし、このケースでは2500枚あればどこでも行けるので意味ない
s=min(s,2500)

# 2501×nの[]行列
# 0~2500枚 × 頂点数
edge=[[[] for i in range(50*50+1)] for i in range(n)]

# (頂点, コスト)→(頂点, コスト)へ辺を渡っての遷移（頂点が変わる）
# u,v,a,bが与えられるたびに、edgeを更新
for i in range(m):
    u,v,a,b=map(int,input().split())
    
    # jは、保有銀貨枚数
    # j:a→2500なのは、jがa未満であれば、隣の頂点に行けないから
    for j in range(a,2501):
        edge[u-1][j].append((v-1,j-a,b))
        edge[v-1][j].append((u-1,j-a,b))
        
# (頂点, コスト)→(頂点, コスト)へ、その頂点に留まって両替の遷移（頂点変わらない）
# c,dが与えられるたびに、edgeを更新
for i in range(n):
    c,d=map(int,input().split())
      
    # 銀貨を捨てるのはノーコスト
    # 2500枚以上持ってたら、2500枚持ってることと同値と考える
    # range(2501)にしない理由は、2500枚あったら、両替はしないから
    for j in range(2500):
        if j+c>=2500:
            edge[i][j].append((i,2500,d))
        elif j+c<2500:
            edge[i][j].append((i,j+c,d))
        
from heapq import heappush,heappop,heapify

# dはn×2501のすべての状態の最小コストの表
d=[[float('inf')  for i in range(50*50+1)] for i in range(n)]

# 初期値。頂点0, 銀貨Sには、コスト0で到達
d[0][s]=0

pq = []
heappush(pq,(0,0,s))

while len(pq):
    # [コスト, 頂点, 銀貨数]で、コストをkeyとして、heapソートして、一番コストが低いリストを先頭に持ってくる
    _,u,g = heappop(pq)
    
    # 頂点までのコストが更新できれば更新してヒープに登録
    # edge[u][g]は、頂点u, 銀貨g枚の状態から、行ける状態のtuple(頂点, 銀貨数, コスト)を呼び出す
    # pqには、[コスト, 頂点, 銀貨数]の順で入れている
    for tuple in edge[u][g]:
        if d[tuple[0]][tuple[1]]>d[u][g]+tuple[2]:
            d[tuple[0]][tuple[1]]=d[u][g]+tuple[2]
            heappush(pq,[d[u][g]+tuple[2],tuple[0],tuple[1]])
        
# d[i]で、頂点iにおける保有銀貨数に応じたコストが入ったリストを呼び出せる
# リストの中で、一番小さいコストのやつを呼び出せば、その頂点に行ける最小コストと同値である
for i in range(1,n):
    print(min(d[i]))

Submission status: Accepted

Solution code:
from heapq import heappop, heappush, heapify

MAX_MONEY = 2500
INF = float("inf")
n, m, s = map(int, input().split())
s = min(s, MAX_MONEY)
graph = [[] for _ in range(n)]
for _ in range(m):
    u, v, a, b = map(int, input().split())
    u -= 1; v -= 1
    graph[u].append((v, a, b))
    graph[v].append((u, a, b))
cd = [tuple(map(int, input().split())) for _ in range(n)]

dp = [[INF] * (MAX_MONEY+10) for _ in range(n)]
dp[0][s] = 0

q = [(0, 0, s)]
while q:
    dist, v, money = heappop(q)
    if dp[v][money] < dist: continue
    for nv, fare, cost in graph[v]:
        nm = money - fare
        if nm < 0: continue
        if dp[nv][nm] > dp[v][money] + cost:
            dp[nv][nm] = dp[v][money] + cost
            heappush(q, (dp[nv][nm], nv, nm))
    
    nm = min(money+cd[v][0], MAX_MONEY)
    if dp[v][nm] > dp[v][money] + cd[v][1]:
        dp[v][nm] = dp[v][money] + cd[v][1]
        heappush(q, (dp[v][nm], v, nm))

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

Submission status: Accepted

Solution code:
from heapq import *

def dijkstra(sta):
    dist = [10**18]*(N*2510)
    dist[sta] = 0
    pq = []
    heappush(pq, (dist[sta], sta))
    
    while pq:
        d, v = heappop(pq)
        
        if dist[v]<d:
            continue
        
        for nv, w in G[v]:
            if dist[nv]>dist[v]+w:
                dist[nv] = dist[v]+w
                heappush(pq, (dist[nv], nv))
    
    return dist

N, M, S = map(int, input().split())
serial = [[0]*2510 for _ in range(N)]
c = 0

for i in range(N):
    for j in range(2510):
        serial[i][j] = c
        c += 1

G = [[] for _ in range(N*2510)]

for _ in range(M):
    U, V, A, B = map(int, input().split())
    U -= 1
    V -= 1
    
    for i in range(A, 2510):
        G[serial[U][i]].append((serial[V][i-A], B))
        G[serial[V][i]].append((serial[U][i-A], B))

for v in range(N):
    C, D = map(int, input().split())
    
    for i in range(2510):
        if i+C>=2510:
            break
        
        G[serial[v][i]].append((serial[v][i+C], D))

dist = dijkstra(serial[0][min(S, 2509)])

for i in range(1, N):
    ans = 10**18
    
    for j in range(2510):
        ans = min(ans, dist[serial[i][j]])
    
    print(ans)

Submission status: Accepted

Solution code:
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)]
chg=10**5

from collections import defaultdict
link = defaultdict(list)
for node in range(n):
    cmai,dmin = cd[node]

    for frm in range(2600):
        link[node*chg + frm].append([node*chg + frm+cmai, dmin])

for i in range(m):
    u,v,a,b = uvab[i]
    u-=1
    v-=1
    for sil in range(2600):
        link[u*chg + sil+a].append([v*chg + sil,b])
        link[v*chg + sil+a].append([u*chg + sil,b])

from heapq import heappush, heappop,heappushpop,heapify
from collections import defaultdict
def dks(g,start):
    INF=float('inf')
    visited = set()
    hq = []
    heappush(hq, (0,start))

    cost = defaultdict(lambda: float("inf"))
    while hq:
        shortest, i = heappop(hq)
        if i in visited:
            continue
        visited.add(i)
        cost[i] = shortest
        for j, t in g[i]:
            if j in visited:
                continue
            heappush(hq, (shortest + t, j))
    return cost

f_sil = min(s,2555)
res=dks(link,f_sil)

for node in range(1,n):
    ans=float("inf")
    for sil in range(2600):
        ans=min(ans,res[node*chg + sil])
    print(ans)

Submission status: Accepted

Solution code:
from scipy.sparse import coo_matrix
from scipy.sparse.csgraph import dijkstra
import numpy as np

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

Us=[0]*M
Vs=[0]*M
As=[0]*M
Bs=[0]*M
for i in range(M):
    Us[i],Vs[i],As[i],Bs[i] = map(int,input().split())
    Us[i] -= 1
    Vs[i] -= 1

# ---
V={}
Ns = max(As)*N
Nv=N*(Ns+1)
cnt=0
for i in range(N):
    for ns in range(Ns+1):
        V[(i,ns)]=cnt
        cnt+=1

row=[]
col=[]
data=[]

if S > Ns:
    S = Ns

# U <-> V
for _ in range(M):
    u = Us.pop()
    v = Vs.pop()
    a = As.pop()
    b = Bs.pop()
    #
    for i in range(Ns+1): # i = 0,..,Ns
        ns_s = Ns - i
        ns_g = ns_s - a
        if ns_g >= 0:
            # U -> V
            row.append( V[(u,ns_s) ])
            col.append( V[(v,ns_g)] )
            data.append( b )
            # V -> U
            row.append( V[(v,ns_s) ])
            col.append( V[(u,ns_g)] )
            data.append( b )

# -----

for i in range(N):
    c,d = map(int,input().split())
    for j in range(Ns): # j = 0,...,Ns-1
        ns_s = j
        ns_g = j + c
        if ns_g > Ns:
            ns_g = Ns
        row.append( V[(i,ns_s) ])
        col.append( V[(i,ns_g)] )
        data.append( d )

graph=coo_matrix((data, (row, col)), shape=(Nv,Nv))

s=V[(0,S)]
dist_matrix = dijkstra(csgraph=graph, directed=True, indices = s)

for i in range(1,N):
    ans = min([dist_matrix[i*(Ns+1)+v] for v in range(Ns+1)])
    print(int(ans))

Submission status: Accepted

Solution code:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import time
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
N,M,S=map(int,input().split())
UVAB=[list(map(int,input().split())) for i in range(M)]
CD=[[0,0]]+[list(map(int,input().split())) for i in range(N)]
data=[defaultdict(list) for i in range(N+1)]

for u,v,a,b in UVAB:
    data[u][v]=[a,b]
    data[v][u]=[a,b]
idel_max=10**18
visited=[[idel_max for i in range(2501)] for n in range(N+1)]
visited2=[[0 for i in range(2501)] for n in range(N+1)]
stack=[]
t=0
c,d=CD[1]
flag=0
s=min(S,2500)
"""while not flag:
    if s>2500:
        s=2500
        flag=1
    visited[1][s]=t
    stack.append([t,s,1])
    t+=d
    s+=c"""

stack=[[t,s,1]]
visited[1][s]=t
while stack:
    #print(len(stack))
    #print(stack[-1])
    #print(stack[0])
    t,s,q=heappop(stack)
    c,d=CD[q]
    flag=0
    if not visited2[q][s]:
        visited2[q][s]=1
        if s<2500:
            _s=min(s+c,2500)
            _t=t+d

            if _t<visited[q][_s]:
                #print("a")
                visited[q][_s]=_t
                heappush(stack,[_t,_s,q])

        for p in data[q]:
            a,b=data[q][p]
            _s=s-a
            if _s>=0:
                _t=t+b
                if _t<visited[p][_s]:
                    visited[p][_s]=_t
                    heappush(stack,[_t,_s,p])
#print(visited[1])
for i in range(2,N+1):
    print(min(visited[i]))

Submission status: Accepted

Solution code:
from heapq import heappop, heappush

n,m,s = map(int,input().split())
e = [[] for _ 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))
c = []
d = []
for i in range(n):
  x,y = map(int,input().split())
  c.append(x)
  d.append(y)

INF = float('inf')
def dijkstra(s,n,g): # sからの最短距離 頂点数n g[v]=[(u1,w1),(u2,w2)....]:vからuへの有向辺があり、重みw
  que = []
  d = [INF for _ in range(n)]
  d[s] = 0
  heappush(que,(0,s))
  while len(que) > 0:
    p = heappop(que)
    v = p[1]
    if d[v] < p[0]:
      continue
    for u,w in g[v]:
      if d[u] > d[v]+w:
        d[u] = d[v]+w
        heappush(que,(d[u],u))
  return d

def newv(v,s):
  return v*2500+s

s = min(s,2499)
e2 = [[] for _ in range(n*2500)]
for u in range(n):
  for j in range(2500):
    if j+c[u] < 2500:
      e2[newv(u,j)].append((newv(u,j+c[u]),d[u]))
    #e2[newv(u,j)].append((newv(u,min(j+c[u],2499)),d[u]))
    for v,a,b in e[u]:
      if j >= a:
        e2[newv(u,j)].append((newv(v,j-a),b))

l = dijkstra(newv(0,s),n*2500,e2)
for i in range(1,n):
  ans = INF
  for j in range(2500):
    ans = min(l[newv(i,j)],ans)
  print(ans)