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:
n, m, s = map(int, input().split())
rail = [[] for _ in range(n)]
fare = [[] for _ in range(n)]
time = [[] for _ in range(n)]
rate = []
TIME = []
for _ in range(m):
    i, j, k, l = map(int, input().split())
    i -= 1
    j -= 1
    rail[i].append(j)
    rail[j].append(i)
    fare[i].append(k)
    fare[j].append(k)
    time[i].append(l)
    time[j].append(l)
for _ in range(n):
    i, j = map(int, input().split())
    rate.append(i)
    TIME.append(j)
    
# Dijkstra's algorithm
# 銀貨の枚数がlimit以上になったら捨てる
limit = [max(i) for i in fare]
limit = max(limit) * n
if s >= limit:
    s = limit - 1

# dp[i][j] = 都市iで銀貨j枚を持っているための必要最小時間
dp = [[float('inf')] * limit for _ in range(n)]

# candidateに(必要時間, 都市番号, 銀貨の枚数)を追加していく
import heapq
candidate = [(0, 0, s)]
heapq.heapify(candidate)

ans = [-1] * n
todo = n

while todo > 0:
    i, j, k = heapq.heappop(candidate)
    if dp[j][k] != float('inf'):
        continue
    dp[j][k] = i
    if ans[j] == -1:
        ans[j] = i
        todo -= 1

    # 鉄道移動をcandidateに追加
    for l in range(len(rail[j])):
        if fare[j][l] <= k and dp[rail[j][l]][k - fare[j][l]] == float('inf'):
            heapq.heappush(candidate, (i + time[j][l], rail[j][l], k - fare[j][l]))
    
    # 両替をcandidateに追加
    if k < limit - 1:
        heapq.heappush(candidate, (i + TIME[j], j, min([k + rate[j], limit - 1])))

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

Submission status: Accepted

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

input = sys.stdin.readline


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

row = []    #start
col = []    #end
data = []

for _ in range(M):
    u, v, a, b = map(int, input().split())
    u -= 1
    v -= 1
    for i in range(a, 2501):
        row.append(N * i + u)
        col.append(N * (i - a) + v)
        data.append(b)
        row.append(N * i + v)
        col.append(N * (i - a) + u)
        data.append(b)

for u in range(N):
    c, d = map(int, input().split())
    for i in range(1, c):
        row.append(N * (2500 - i) + u)
        col.append(N * 2500 + u)
        data.append(d)
    for i in range(c, 2501):
        row.append(N * (i - c) + u)
        col.append(N * i + u)
        data.append(d)

graph = csr_matrix((data, (row, col)), shape = (2501*N, 2501*N))

times = dijkstra(graph, directed  = True, indices = N * S)

for end in range(1, N):
    print(int(min(times[N * i + end] for i in range(2501))))

Submission status: Accepted

Solution code:
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
# @lru_cache(maxsize=None)
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp():
    '''
    一つの整数
    '''
    return int(input())
def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))


class Dijkstra():
    def __init__(self):
        self.e = collections.defaultdict(list)

    def add(self, u, v, d, directed=False):
        """
        Parameters
        ----------
        u:int
            from node
        v:int
            to node
        d:int
            cost
        directed:bool
            there is direction
        """
        if directed is False:
            self.e[u].append([v, d])
            self.e[v].append([u, d])
        else:
            self.e[u].append([v, d])

    def delete(self, u, v):
        """
        Parameters
        ----------
        u:int
            from node
        v:int
            to node
        """
        self.e[u] = [_ for _ in self.e[u] if _[0] != v]
        self.e[v] = [_ for _ in self.e[v] if _[0] != u]

    def Dijkstra_search(self, s):
        """
        Parameters
        ----------
        s:int
            start node

        Return
        ----------
        d:dict(int:int)
            shortest cost from start node to each node 
            {to : cost}

        prev:dict(int:int)
            previous node on the shortest path
            {from : to}
        """
        d = collections.defaultdict(lambda: float('inf'))
        prev = collections.defaultdict(lambda: None)
        d[s] = 0
        q = []
        heapq.heappush(q, (0, s)) # (cost, 探索候補ノード)
        v = collections.defaultdict(bool) # 確定済かどうか
        while len(q):
            # ノードuにおけるコストはk
            k, u = heapq.heappop(q)
            if v[u]:
                continue
            v[u] = True

            for uv, ud in self.e[u]: # cost is ud from u to uv
                if v[uv]:
                    continue
                vd = k + ud
                if d[uv] > vd:
                    d[uv] = vd
                    prev[uv] = u
                    heapq.heappush(q, (vd, uv))

        return d, prev

    def getDijkstraShortestPath(self, start, goal):
        """
        Parameters
        ----------
        start:int
            start node
        goal:int
            goal node

        Return
        ----------
        ShortestPath:list(int)
            shortest path
        """
        _, prev = self.Dijkstra_search(start)
        shortestPath = []
        node = goal
        while node is not None:
            shortestPath.append(node)
            node = prev[node]
        return shortestPath[::-1]

n, m, s = inpl()
LIMIT_SILVER = 2500
s=min(s,LIMIT_SILVER-1)
graph = Dijkstra()
for i in range(m):
    u,v,a,b = inpl()
    for j in range(a,LIMIT_SILVER):
        graph.add((u,j), (v,j-a), b, directed=True)
        graph.add((v,j), (u,j-a), b, directed=True)
for i in range(n):
    c,d = inpl()
    for j in range(c,LIMIT_SILVER):
        graph.add((i + 1, j - c), (i + 1, j), d, directed=True)
# print(graph.e)
costs,_ = graph.Dijkstra_search((1,s))
# print(costs)
for i in range(2, n + 1):
    ans=INF
    for j in range(2500):
        ans = min(ans, costs[(i, j)])
    print(ans)
# path = graph.getDijkstraShortestPath((1, s), (3, 0))
# print(path)

Submission status: Accepted

Solution code:
from heapq import *
import sys
input = sys.stdin.buffer.readline
n, m, s = map(int, input().split())
lim = 2510
di = [[float("inf")] * lim for _ in range(n)]
di[0][min(s,lim-1)] = 0
con = [[] for _ in range(n)]
for _ in range(m):
	u, v, a, b = map(int, input().split())
	con[u - 1].append((v - 1, a, b))
	con[v - 1].append((u - 1, a, b))
q = [(0, min(s,lim-1), 0)]
cd = [list(map(int, input().split())) for _ in range(n)]
while q:
	time, have, cur = heappop(q)
	if di[cur][have] < time:
		continue
	c, d = cd[cur]
	if have + c < lim and di[cur][have + c] > time + d:
		di[cur][have + c] = time + d
		heappush(q, (time + d, have + c, cur))
	for nxt, dh, dt in con[cur]:
		if have >= dh and di[nxt][have - dh] > time + dt:
			di[nxt][have - dh] = time + dt
			heappush(q, (time + dt, have - dh, nxt))
for p in di[1:]:
	print(min(p))

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    #from math import gcd

    inf = 10**17
    #mod = 10**9 + 7

    n,m,s = map(int, input().split())
    s = min(s, 2500)
    # edge[i]:頂点iからの[行先, 必要な銀貨, 時間]
    edge = [[] for _ in range(n)] #頂点数, 場合によって変える
    for _ in range(m):
        a,b,c,d = map(int, input().split())
        edge[a-1].append((b-1, c, d))
        edge[b-1].append((a-1, c, d))

    # 銀貨との交換を自己ループとする
    for i in range(n):
        c, d = map(int, input().split())
        edge[i].append((i, -c, d))

    dp = [[inf]*2501 for _ in range(n)]
    dp[0][s] = 0
    # [時間, 所持金, 頂点]
    hq = [(0, s, 0)]
    heapify(hq)

    while hq:
        t, ginka, v = heappop(hq)
        if dp[v][ginka] < t:
            continue
        for nv, a, b in edge[v]:
            if ginka < a:
                continue
            ng = ginka - a
            if ng > 2500:
                ng = 2500
            for i in range(ng, -1, -1):
                if dp[nv][i] > t+b:
                    dp[nv][i] = t+b
                    f = 1
                else:
                    break
            else:
                heappush(hq, (t+b, ng, nv))
            if i != ng:
                heappush(hq, (t+b, ng, nv))
    
    for i in range(1, n):
        print(min(dp[i]))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    #from math import gcd

    inf = 10**17
    #mod = 10**9 + 7

    n,m,s = map(int, input().split())
    s = min(s, 2500)
    # edge[i]:頂点iからの[行先, 必要な銀貨, 時間]
    edge = [[] for _ in range(n)] #頂点数, 場合によって変える
    for _ in range(m):
        a,b,c,d = map(int, input().split())
        edge[a-1].append((b-1, c, d))
        edge[b-1].append((a-1, c, d))

    # 銀貨との交換を自己ループとする
    for i in range(n):
        c, d = map(int, input().split())
        edge[i].append((i, -c, d))

    dp = [[inf]*2501 for _ in range(n)]
    dp[0][s] = 0
    # [時間, 所持金, 頂点]
    hq = [(0, s, 0)]
    heapify(hq)

    while hq:
        t, ginka, v = heappop(hq)
        if dp[v][ginka] < t:
            continue
        for nv, a, b in edge[v]:
            if ginka < a:
                continue
            ng = ginka - a
            if ng > 2500:
                ng = 2500
            f = 0
            for i in range(ng, -1, -1):
                if dp[nv][i] > t+b:
                    dp[nv][i] = t+b
                    f = 1
                else:
                    break
            if f:
                heappush(hq, (t+b, ng, nv))
    
    for i in range(1, n):
        print(min(dp[i]))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    #from math import gcd

    inf = 10**17
    #mod = 10**9 + 7

    n,m,s = map(int, input().split())
    s = min(s, 2500)
    # edge[i]:頂点iからの[行先, 必要な銀貨, 時間]
    edge = [[] for _ in range(n)] #頂点数, 場合によって変える
    for _ in range(m):
        a,b,c,d = map(int, input().split())
        edge[a-1].append((b-1, c, d))
        edge[b-1].append((a-1, c, d))

    # 銀貨との交換を自己ループとする
    for i in range(n):
        c, d = map(int, input().split())
        edge[i].append((i, -c, d))

    dp = [[inf]*2501 for _ in range(n)]
    dp[0][s] = 0
    # [時間, 所持金, 頂点]
    hq = [(0, s, 0)]
    heapify(hq)

    while hq:
        t, ginka, v = heappop(hq)
        if dp[v][ginka] < t:
            continue
        for nv, a, b in edge[v]:
            if ginka < a:
                continue
            ng = ginka - a
            if ng > 2500:
                ng = 2500
            if dp[nv][ng] > t+b:
                dp[nv][ng] = t+b
                heappush(hq, (t+b, ng, nv))
    
    for i in range(1, n):
        print(min(dp[i]))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    N, M, S = LI()
    G = [[[] for _ in range(2501)] for _ in range(N)]

    for i in range(M):
        u, v, a, b = LI()
        u -= 1
        v -= 1
        for money in range(2501):
            if money - a < 0 :
                continue
            G[u][money].append((b, v, money - a))
            G[v][money].append((b, u, money - a))

    for i in range(N):
        c, d = LI()
        for money in range(2501):
            new_money = min(2500, money + c)
            G[i][money].append((d, i, new_money))
    def dijkstra(u, s):
        q = []
        d = [[inf for __ in range(2501)] for _ in range(N)]
        visited = set()
        dist = 0
        money = min(2500, s)
        d[u][money] = dist
        heapq.heappush(q, (dist, u, money))
        while len(q) > 0:
            dist, u, u_money = heapq.heappop(q)

            if (u, u_money) in visited:
                continue
            visited.add((u, u_money))
            for next_node_tuple in G[u][u_money]:
                cost, v, v_money = next_node_tuple
                if dist + cost < d[v][v_money]:
                    d[v][v_money] = dist + cost
                    heapq.heappush(q, (d[v][v_money], v, v_money))
        return d
    d = dijkstra(0, S)
    for i in range(1, N):
        print(min(d[i]))

main()

Submission status: Accepted

Solution code:
from heapq import heappop, heappush
import sys
input = sys.stdin.readline
INF = 10**100
MAX = 2500
N, M, S = map(int, input().split())
S = min(S, MAX)
G = [[] for _ in [0]*N]
C = []
for _ in [0]*M:
    u, v, a, b = map(int, input().split())
    u -= 1
    v -= 1
    G[v].append((u, a, b))
    G[u].append((v, a, b))

for i in range(N):
    a, b = map(int, input().split())
    C.append((a, b))

# dijkstra
dp = [[INF]*MAX for _ in [0]*N]
q = []
def push(t, s, v):
    if s < 0:
        return
    if s >= MAX:
        s = MAX-1
    if dp[v][s] <= t:
        return
    dp[v][s] = t
    heappush(q, (t, s, v))

push(0, S, 0)

while q:
    t, s, v = heappop(q)
    if dp[v][s] != t:
        continue

    c, d = C[v]
    push(t+d, s+c, v)

    for u, a, b in G[v]:
        push(t+b, s-a, u)

# output
for d in dp[1:]:
    ans = INF
    for s in range(MAX):
        if ans > d[s]:
            ans = d[s]
    print(ans)

Submission status: Accepted

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


class Heap():
    def __init__(self, ):
        self.h = []

    def heapify(self, h):
        self.h = h
        heapify(self.h)

    def heappop(self,):
        return heappop(self.h)

    def heappush(self, x):
        heappush(self.h, x)


N, M, S = map(int, input().split())
INF = 10**100
G = [[] for _ in [0]*N]
C = []

for _ in [0]*M:
    u, v, a, b = map(int, input().split())
    u -= 1
    v -= 1
    G[v].append((u, a, b))
    G[u].append((v, a, b))

for i in range(N):
    a, b = map(int, input().split())
    C.append((a, b))


def push(t, s, v):
    if s < 0:
        return
    if s >= MAX:
        s = MAX-1
    if dp[v][s] <= t:
        return
    dp[v][s] = t
    heappush(q, (t, s, v))


MAX = 2500
S = min(S, MAX)
dp = [[INF]*MAX for _ in [0]*N]

q = []
push(0, S, 0)

while q:
    t, s, v = heappop(q)
    if dp[v][s] != t:
        continue

    c, d = C[v]
    push(t+d, s+c, v)

    for u, a, b in G[v]:
        push(t+b, s-a, u)

for d in dp[1:]:
    ans = INF
    for s in range(MAX):
        if ans > d[s]:
            ans = d[s]
    print(ans)

Submission status: Accepted

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

n, m, s = map(int, input().split())
g = [[] for _ in range(n)]
for i in range(m):
    u,v,a,b = map(int, input().split())
    g[u-1].append((v-1,a,b))
    g[v-1].append((u-1,a,b))
cd = [list(map(int, input().split())) for _ in range(n)]

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

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

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

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

Submission status: Accepted

Solution code:
import sys

input=sys.stdin.buffer.readline

N, M, S = map(int,input().split())
SMAX = 50 * (N-1)
S = min(S,SMAX)

INF=10**18
dp = [[INF]*2501 for _ in range(N)]
way=[[]for _ in range(N)]

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

CD = [tuple(map(int,input().split())) for _ in range(N)]

from heapq import heappush,heappop

q=[(0,0,S)]

while q:
    t, u, s = heappop(q)
    for nxt, a, b in way[u]:
        if s >= a:

            if dp[nxt][s-a] > t + b:
                dp[nxt][s-a] = t + b
                heappush(q,(t + b, nxt, s-a))
                
    c, d = CD[u]
    nc = min(SMAX, c + s)
    nt= t + d

    if nt < dp[u][nc]:
        dp[u][nc] = nt
        heappush(q, (nt, u, nc))

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

Submission status: Accepted

Solution code:
import sys
# sys.setrecursionlimit(10**7)  # ネスト回数制限（いる？）

# 入力値を扱いやすい形で格納していく

# input=sys.stdin.buffer.readline  # input の高速化（今回は外す）

N, M, S = map(int,input().split())  # 頂点数／辺数／初期所持金(state)
S=min(S,2500)  # 高々 2500 あれば良い（全都市を回るのに払いきれる回数）

INF=10**18
dp = [[INF]*2501 for _ in range(N)]
way=[[]for _ in range(N)]

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

# 両替比率と時間
# CD = [list(map(int,input().split())) for _ in range(N)]  # list化する意味は？
CD = [tuple(map(int,input().split())) for _ in range(N)]

from heapq import heappush,heappop

# q は 時間／都市名／所持金　の順番 <- 時間をキーに heapq を使うため

q=[(0,0,S)]  # スタート状態

while q:
    t, u, s = heappop(q)  # 最も到着時間の短い都市 u を選択
    for nxt, a, b in way[u]:  # u からたどり着ける都市 nxt に対して
        if s >= a:  # 交通費がある場合

            if dp[nxt][s-a] > t + b:  # 到着時間を検討
                dp[nxt][s-a] = t + b  # 早いので書き換え
                heappush(q,(t + b, nxt, s-a))  #  キューに次の都市候補として登録しておく
                # 同じ都市 & 同じ金額 が複数個登録されないか？ 計算回数は
                # 更新された = 周囲の都市（点）にたどり着く値を更新する必要があるかもしれないから
                # 検討対象になる

        # この時点では、u にいて、所持金 s でたどり着けないとしてはまだ更新されていない
                
    c, d = CD[u]
    nc = min(2500, c + s)  # 所持金を増やす
    nt= t + d  # 時間も掛かる

    if nt < dp[u][nc]:  # 交換後の金額と時間を見て、更新する（無限大だけが更新になる？）
        dp[u][nc] = nt
        heappush(q, (nt, u, nc))  # 同じ都市（点）だが、違う状態が登録されている

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

Submission status: Accepted

Solution code:
import sys
from heapq import heappush,heappop
sys.setrecursionlimit(10**7)
input=sys.stdin.buffer.readline
N,M,S=map(int,input().split())
S=min(S,2500)
INF=10**18
time=[[INF]*2501 for _ in range(N)]
way=[[]for _ in range(N)]
for _ in range(M):
  u,v,a,b=map(int,input().split())
  way[u-1].append((v-1,a,b))
  way[v-1].append((u-1,a,b))
CD=[list(map(int,input().split())) for _ in range(N)]
q=[(0,0,S)]
while q:
  ti,city,cur=heappop(q)
  for nxt,a,b in way[city]:
    if cur>=a:
      if time[nxt][cur-a]>ti+b:
        time[nxt][cur-a]=ti+b
        heappush(q,(ti+b,nxt,cur-a))
  c,d=CD[city]
  nc=min(2500,c+cur)
  nt=ti+d
  if nt<time[city][nc]:
    time[city][nc]=nt
    heappush(q,(nt,city,nc))
for i in range(1,N):
  print(min(time[i]))

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
from pprint import pprint
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

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

C, D = ZIP(N)
M = 2500
if S >= M: S = M-1
dist = [[INF]*M for _ in range(N)]
dist[0][S] = 0
q = [(0, S, 0)]

while q:
    d, coin, n = heappop(q)
    if coin + C[n] < M and d+D[n] < dist[n][coin+C[n]]:
        dist[n][coin+C[n]] = d+D[n]
        heappush(q, (d+D[n], coin + C[n], n))
    for node, cnode, dnode in graph[n]:
        nd = d + dnode
        if coin >= cnode and nd < dist[node][coin-cnode]:
            dist[node][coin-cnode] = nd
            heappush(q, (nd, coin-cnode, node))

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

Submission status: Accepted

Solution code:
import bisect
import sys
import math
from collections import deque
from heapq import heappush, heappop

def sRaw():
    return input().rstrip("\r")


def iRaw():
    return int(input())


def ssRaw():
    return input().split()


def isRaw():
    return list(map(int, ssRaw()))


INF = 1 << 29

DIV = (10**9) + 7


def mod_inv_prime(a, mod=DIV):
    return pow(a, mod-2, mod)


def mod_inv(a, b):
    r = a
    w = b
    u = 1
    v = 0
    while w != 0:
        t = r//w
        r -= t*w
        r, w = w, r
        u -= t*v
        u, v = v, u
    return (u % b+b) % b


def CONV_TBL(max, mod=DIV):
    fac, finv, inv = [0]*max, [0]*max, [0]*max
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, max):
        fac[i] = fac[i-1]*i % mod
        inv[i] = mod - inv[mod % i] * (mod//i) % mod
        finv[i] = finv[i-1]*inv[i] % mod

    class CONV:
        def __init__(self):
            self.fac = fac
            self.finv = finv
            pass

        def ncr(self, n, k):
            if(n < k):
                return 0
            if(n < 0 or k < 0):
                return 0
            return fac[n]*(finv[k]*finv[n-k] % DIV) % DIV

    return CONV()


def cumsum(As):
    s = 0
    for a in As:
        s += a
        yield s


sys.setrecursionlimit(200005)


def dijkstra(G,start=0):
    #calc shortest path costs by dijkstra
    #be careful edge definition
    #inputs
    #G is [[e for e in En for n in V]
    #  where as e is (cost,dest) and V is vertexes and En is n's edges
    #start is start vert
    #return
    #cost = [cn for n in V]
    #  where cn is shortest path cost from start to n
    heap = []
    cost = [INF]*len(G)
    heappush(heap,(0,start))
    while len(heap)!=0:
        c,n = heappop(heap)
        if cost[n] !=INF:
            continue
        cost[n]=c
        for e in G[n]:
            ec,v = e
            if cost[v]!=INF:
                continue
            heappush(heap,(ec+c,v))
    return cost


def main():
    N,M,S = isRaw()
    UVABs = [isRaw() for _ in range(M)]
    Smax = N*51 
    G = [[] for _ in range(N*Smax)]
    
    for uvab in UVABs:
        u,v,a,b = uvab
        for s in range(a*N,Smax*N,N):
            G[s+u-1].append((b,s-(a*N)+v-1))
            G[s+v-1].append((b,s-(a*N)+u-1))
    for n in range(N):
        c,d = isRaw()
        for s in range(N, Smax*N, N):
            G[s+n].append((0,s-N+n))
            if s>=c*N:
                G[s-c*N+n].append((d,s+n))
    cost = dijkstra(G,min(S,Smax-N)*N)
    return "\n".join([str(c) for c in cost[1:N]])


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

Submission status: Accepted

Solution code:
import bisect
import sys
import math
from collections import deque
from heapq import heappush, heappop

def sRaw():
    return input().rstrip("\r")


def iRaw():
    return int(input())


def ssRaw():
    return input().split()


def isRaw():
    return list(map(int, ssRaw()))


INF = 1 << 29

DIV = (10**9) + 7


def mod_inv_prime(a, mod=DIV):
    return pow(a, mod-2, mod)


def mod_inv(a, b):
    r = a
    w = b
    u = 1
    v = 0
    while w != 0:
        t = r//w
        r -= t*w
        r, w = w, r
        u -= t*v
        u, v = v, u
    return (u % b+b) % b


def CONV_TBL(max, mod=DIV):
    fac, finv, inv = [0]*max, [0]*max, [0]*max
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, max):
        fac[i] = fac[i-1]*i % mod
        inv[i] = mod - inv[mod % i] * (mod//i) % mod
        finv[i] = finv[i-1]*inv[i] % mod

    class CONV:
        def __init__(self):
            self.fac = fac
            self.finv = finv
            pass

        def ncr(self, n, k):
            if(n < k):
                return 0
            if(n < 0 or k < 0):
                return 0
            return fac[n]*(finv[k]*finv[n-k] % DIV) % DIV

    return CONV()


def cumsum(As):
    s = 0
    for a in As:
        s += a
        yield s


sys.setrecursionlimit(200005)


def dijkstra(G,start=0):
    heap = []
    cost = [INF]*len(G)
    heappush(heap,(0,start))
    while len(heap)!=0:
        c,n = heappop(heap)
        if cost[n] !=INF:
            continue
        cost[n]=c
        for e in G[n]:
            ec,v = e
            if cost[v]!=INF:
                continue
            heappush(heap,(ec+c,v))
    return cost


def main():
    N,M,S = isRaw()
    UVABs = [isRaw() for _ in range(M)]
    Smax = N*51 
    G = [[] for _ in range(N*Smax)]
    
    for uvab in UVABs:
        u,v,a,b = uvab
        for s in range(a*N,Smax*N,N):
            G[s+u-1].append((b,s-(a*N)+v-1))
            G[s+v-1].append((b,s-(a*N)+u-1))
    for n in range(N):
        c,d = isRaw()
        for s in range(N, Smax*N, N):
            G[s+n].append((0,s-N+n))
            if s>=c*N:
                G[s-c*N+n].append((d,s+n))
    cost = dijkstra(G,min(S,Smax-N)*N)
    return "\n".join([str(c) for c in cost[1:N]])


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