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 heapq

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

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

u,v,a,b = [0]*m,[0]*m,[0]*m,[0]*m 
c,d = [0]*n,[0]*n 
for i in range(m):
    u[i],v[i],a[i],b[i] = list(map(int,input().split()))
for i in range(n):
    c[i],d[i] = list(map(int,input().split()))

maA = max(a)
maxsilver = maA*(n-1)
p = (maxsilver+1) * n
# 都市i(0~)で銀貨j枚持っている時,i*(maxsilver+1)+j番目
e = [[] for i in range(p)]
# 金貨交換
for i in range(n):
    for j in range(maxsilver+1):
        e[i*(maxsilver+1) + j].append((d[i], i*(maxsilver+1) + min(j+c[i], maxsilver)))
# 移動
for i in range(m):
    for j in range(a[i],maxsilver+1):
        e[(u[i]-1)*(maxsilver+1) + j].append((b[i], (v[i]-1)*(maxsilver+1) + j-a[i]))
        e[(v[i]-1)*(maxsilver+1) + j].append((b[i], (u[i]-1)*(maxsilver+1) + j-a[i]))

# print(e)
# 初期地点は0+min(s,maxsilver)
d = dijkstra(min(s,maxsilver))
for i in range(1,n):
    ans = float("inf")
    x = [0]*(maxsilver+1)
    for j in range(maxsilver+1):
        x[j] =  d[i*(maxsilver+1)+j]
    heapq.heapify(x)
    ans = heapq.heappop(x)
    print(ans)

Submission status: Accepted

Solution code:
#! /usr/bin/env python3
from collections import defaultdict
import heapq
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))
def make_array(dim, type=int): return defaultdict(lambda: defaultdict(type))


INF=10**20
def main():
    N,M,S=mi()
    
    G = [[] for _ in range(N+1) ]
    T = [None] * M
    for i in range(M):
        u,v,a,b=mi()
        T[i] = (u,v,a,b)
        G[u].append((i,v,a,b)) # i番目の路線
        G[v].append((i,u,a,b))
        

    
    C = []
    D = []
    for i in range(N):
        c,d = mi()
        C.append(c)
        D.append(d)
    
    cost = defaultdict(lambda: defaultdict(int))
    E = defaultdict(lambda: [])
    for i in range(0,2501):
        for track in T:
            u,v,a,b = track
            if i-a < 0: continue
            cost[(u,i)][(v,i-a)] = b
            cost[(v,i)][(u,i-a)] = b
            E[(u,i)].append((v,i-a))
            E[(v,i)].append((u,i-a))
            
        
        for j in range(N):
            c,d = C[j],D[j]
            cost[(j+1,i)][(j+1,i+c)] = d
            E[(j+1,i)].append((j+1,i+c))





    if S > 2500: S = 2500

    s = (1,S)
    hq = [(0,s)]
    heapq.heapify(hq)

    dist = defaultdict(lambda: INF)
    dist[s] = 0
    while hq: 
        d,x = heapq.heappop(hq) # sからxまでの最短経路を探索する
        if dist[x] < d: continue

        for e in E[x]:
            # print(dist[e] , dist[x] , cost[x][e])
            if dist[e] > dist[x] + cost[x][e]:
                dist[e] = dist[x] + cost[x][e]
                heapq.heappush(hq,(dist[e],e))
    
    for t in range(2,N+1):
        ans = INF
        for i in range(0,2501):
            ans = min(ans,dist[(t,i)])
        print(ans)

    # if dist[t] == INF: return -1
    # return dist[t]






if __name__ == "__main__":
    main()

Submission status: Accepted

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**15
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 or v<2:continue
  ans[v] = min(ans[v],d[i])
  
print(*ans[2:])

Submission status: Accepted

Solution code:
from heapq import heappop, heappush

max2 = lambda x,y: x if x > y else y
min2 = lambda x,y: x if x < y else y

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

def solve(cities,trains,S):
    N = len(cities)
    adj = [[] for _ in range(N)]

    for u,v,a,b in trains:
        u,v = u-1,v-1
        adj[u].append((v,a,b))
        adj[v].append((u,a,b))

    M = 2500
    S = min2(S,M-1)

    encode = lambda v,c: v*M+c
    decode = lambda i: (i//M,i%M)

    dist = [10**18]*(N*M)
    dist[S] = 0

    q = [(0, S)]

    while q:
        d,i = heappop(q)
        if dist[i] < d:
            continue

        v,c = decode(i)
        C,D = cities[v]

        nc = min2(c+C,M-1)
        ni = encode(v,nc)
        nd = d+D
        if dist[ni] > nd:
            dist[ni] = nd
            heappush(q, (nd, ni))

        for u,a,b in adj[v]:
            if c < a:
                continue
            ni = encode(u,c-a)
            nd = d+b
            if dist[ni] > nd:
                dist[ni] = nd
                heappush(q, (nd, ni))

    return [min(dist[v*M:v*M+M]) for v in range(N)][1:]



if __name__ == '__main__':
    N,M,S = map(int,readline().split())

    m = map(int,read().split())

    trains = list(t for _,t in zip(range(M), zip(m,m,m,m)))
    cities = list(zip(m,m))

    print(*solve(cities,trains,S), sep='\n')

Submission status: Accepted

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


def main():
    n, m, s = map(int, input().split())
    
    s = min(s, 2500)
    
    railway = [[] for _ in range(n)]
    for i in range(m):
        u, v, a, b = map(int, input().split())
        railway[u-1].append((v-1, a, b))
        railway[v-1].append((u-1, a, b))
    
    exchange = [None]*n
    for i in range(n):
        exchange[i] = tuple(map(int, input().split()))
    
    
    judge = [(0, 0, s)]
    heapify(judge)
    time = [[-1]*2501 for _ in range(n+1)]*n
    
    while judge:
        t, now, money = heappop(judge)
        if time[now][money] == -1:
            time[now][money] = t
        elif time[now][money] <= t:
            continue
        else:
            time[now][money] = min(time[now][money], t)
        
        if money < 2500:
            c, d = exchange[now]
            if time[now][min(2500, money+c)] == -1:
                heappush(judge, (t+d, now, min(2500, money+c)))
        for (v, a, b) in railway[now]:
            if money-a < 0:
                continue
            if time[v][money-a] == -1:
                heappush(judge, (t+b, v, money-a))
    
    for i in range(1, n):
        print(min(time[i]))
    
    
if __name__ == "__main__":
    main()

Submission status: Accepted

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 cut(self, x):
        return min2(x, self.fare_max * (self.n - 1))

    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 = self.cut(S)
        res[start][money] = 0
        next_set = [(0, start, money)]
        while next_set:
            dist, p, money = heappop(next_set)
            if res[p][money] < dist:
                continue
            for edge in self.edges[p]:
                q, cost, fare = edge.to, edge.cost, edge.fare
                temp_d = dist + cost
                if temp_d < res[q][self.cut(money-fare)] and money >= fare:
                    res[q][self.cut(money-fare)] = temp_d
                    heappush(next_set, (temp_d, q, self.cut(money - fare)))
        if self.decrement:
            return [[0]] + res
        else:
            return res

def max2(x,y):
    return x if x > y else y

def min2(x,y):
    return x if x < y else y



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

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 i in range(1,N+1):
    fare, cost = map(int, input().split())
    graph.add_edge(i,i, cost, -fare)
d = graph.dijkstra(1,S,INF=INF)
for i in range(2,N+1):
    print(min(d[i]))

Submission status: Accepted

Solution code:
import math
import heapq

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

road = []
for i in range(m):
    u,v,a,b = map(int,input().split())
    road.append([u,v,a,b])

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

tree = [[] for _ in range(n+1)]

for i in range(m):  
    r = road[i]
    tree[r[0]].append([r[0],r[1],r[2],r[3]])
    tree[r[1]].append([r[1],r[0],r[2],r[3]])

least_cost = [[] for _ in range(n+1)]
for l in range(n+1):
    least_cost[l] = [math.inf]*2501

queue = []

#hwd [location, money, time]
def dijakstra(q):
    while q != []:
        hwd = heapq.heappop(q)

        if least_cost[hwd[1]][hwd[2]] > hwd[0]:
            least_cost[hwd[1]][hwd[2]] = hwd[0]
            
            for node in tree[hwd[1]]:
                # from node, to node , money, time
                if hwd[2] - node[2] >= 0:
                    heapq.heappush(q,(hwd[0]+node[3],node[1],hwd[2]-node[2]))
            if hwd[2] + change[hwd[1]-1][0] <= 2500:
                heapq.heappush(q,(hwd[0]+change[hwd[1]-1][1],hwd[1],hwd[2]+change[hwd[1]-1][0]))
    return least_cost

if s > 2500:
    s = 2500
queue.append((0,1,s))

ans = dijakstra(queue)

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

Submission status: Accepted

Solution code:
import math

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

road = []
for i in range(m):
    u,v,a,b = map(int,input().split())
    road.append([u,v,a,b])

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

tree = [[] for _ in range(n+1)]

for i in range(m):  
    r = road[i]
    tree[r[0]].append([r[0],r[1],r[2],r[3]])
    tree[r[1]].append([r[1],r[0],r[2],r[3]])

least_cost = [[] for _ in range(n+1)]
for l in range(n+1):
    least_cost[l] = [math.inf]*2501


def insort_queue(q,v):
    len_a = len(q)    
    if len_a == 0:
        q.append(v)
        return
    
    min = 0
    max_1 = len_a

    if max_1 == 1:
        if v[2] > q[0][2]:
            min = 1
        else:
            min = 0
    while max_1 - min > 1:
        mid = (max_1 + min) //2
        if v[2] > q[mid][2]:
            min = mid
        else:
            max_1 = mid
    index = max_1
    q.insert(index,v)

queue = []

#hwd [location, money, time]
def dijakstra(q):
    while q != []:
        hwd = q.pop(0)

        if least_cost[hwd[0]][hwd[1]] > hwd[2]:
            least_cost[hwd[0]][hwd[1]] = hwd[2]
            
            for node in tree[hwd[0]]:
                # from node, to node , money, time
                if hwd[1] - node[2] >= 0:
                    insort_queue(q,[node[1],hwd[1]-node[2],hwd[2]+node[3]])
            if hwd[1] + change[hwd[0]-1][0] <= 500:
                insort_queue(q,[hwd[0],hwd[1]+change[hwd[0]-1][0],hwd[2]+change[hwd[0]-1][1]])
    return least_cost

if s > 2500:
    s = 2500
queue.append([1,s,0])

ans = dijakstra(queue)

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

Submission status: Accepted

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

def input(): return sys.stdin.readline().rstrip()
def ii(): return int(input())
def mi(): return map(int, input().split())
def li(): return list(mi())


def main():

    def dijkstra(xs, ss):
        def push(v, s, x):
            if s < 0: 
                return
            if dist[v, s] <= x:
                return
            dist[v, s] = x
            heappush(que, (x, v, s))
        
        inf = 10**18
        dist = np.full((n, MAX_S+1), inf, dtype=int)
        # time, remain, node
        que = []
        push(xs, ss, 0)
        while que:
            x, v, s = heappop(que)
            if dist[v, s] < x:
                continue
            ns = min(s+c[v], MAX_S)
            push(v, ns, x+d[v])
            for nv, a, b in adj[v]:
                push(nv, s-a, x+b)
        return np.min(dist, axis=1)

    n, m, s = mi()
    adj = [[] for i in range(n)]
    MAX_S = 0
    for i in range(m):
        u, v, a, b = mi()
        u -= 1
        v -= 1
        adj[u].append((v, a, b))
        adj[v].append((u, a, b))
        MAX_S = max(MAX_S, a)
    MAX_S *= n-1
    s = min(s, MAX_S)
    c, d = [0]*n, [0]*n
    for i in range(n):
        c[i], d[i] = mi()
    ans = dijkstra(0, s)
    print(*ans[1:], sep='\n')


if __name__ == '__main__':
    main()

Submission status: Accepted

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

def input(): return sys.stdin.readline().rstrip()
def ii(): return int(input())
def mi(): return map(int, input().split())
def li(): return list(mi())


def main():

    def dijkstra(s):
        def push(v, s, x):
            if s < 0: 
                return
            if dist[v, s] <= x:
                return
            dist[v, s] = x
            heappush(que, (x, v, s))
        
        inf = 10**18
        dist = np.full((n, MAX_S+1), inf, dtype=int)
        # time, remain, node
        que = []
        push(0, s, 0)
        while que:
            x, v, s = heappop(que)
            if dist[v, s] < x:
                continue
            ns = min(s+c[v], MAX_S)
            push(v, ns, x+d[v])
            for nv, a, b in adj[v]:
                push(nv, s-a, x+b)
        return np.min(dist, axis=1)

    n, m, s = mi()
    adj = [[] for i in range(n)]
    MAX_S = 0
    for i in range(m):
        u, v, a, b = mi()
        u -= 1
        v -= 1
        adj[u].append((v, a, b))
        adj[v].append((u, a, b))
        MAX_S = max(MAX_S, a)
    MAX_S *= n-1
    s = min(s, MAX_S)
    c, d = [0]*n, [0]*n
    for i in range(n):
        c[i], d[i] = mi()
    ans = dijkstra(s)
    print(*ans[1:], sep='\n')


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import heapq
import collections


def main():
    INF = 10 ** 15
    # 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: Accepted

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 = 2501
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 ** 20
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: Accepted

Solution code:
import heapq


UNVISITED = -1

def construct_incidence_list(tail, head):
    n=2500*N
    m=len(head)

    edge_first = [0] * n
    edge_next = [0] * m

    for i in range(m, 0, -1):
        v = tail[i-1]
        edge_next[i-1] = edge_first[v-1]
        edge_first[v-1] = i

    return edge_first, edge_next


def main():
    tail=[]
    head=[]
    length=[]
    for i in range(M):
      u,v,a,b=map(int,input().split())
      for j in range(2499,a-1,-1):
        tail.append(2500*(u-1)+j)
        head.append(2500*(v-1)+j-a)
        length.append(b)
        head.append(2500*(u-1)+j-a)
        tail.append(2500*(v-1)+j)
        length.append(b)
    for i in range(N):
      c,d=map(int,input().split())
      for j in range(2499):
        tail.append(2500*(i)+j)
        head.append(2500*(i)+min(j+c,2499))
        length.append(d)

    start = min(S,2499)

    edge_first, edge_next = construct_incidence_list(tail, head)
    
    n = 2500*N
    distance = [0] * (n+1)
    path = [0] + [UNVISITED for v in range(1, n+1)]
    distance[start] = 0
    path[start] = 0
    hq = [(0, start)]
    heapq.heapify(hq)

    while len(hq) > 0:
        _, v1 = heapq.heappop(hq)

        edge_to_v2 = edge_first[v1-1]
        while edge_to_v2 != 0:
            v2 = head[edge_to_v2-1]
            dist_candidate = distance[v1] + length[edge_to_v2-1]
            if path[v2] == UNVISITED or distance[v2] > dist_candidate:
                distance[v2] = dist_candidate
                path[v2] = edge_to_v2
                heapq.heappush(hq, (distance[v2], v2))

            edge_to_v2 = edge_next[edge_to_v2-1]

    for i in range(1,N):
      ans=10**18
      for j in range(2500):
        if distance[i*2500+j]==0:
          continue
        if distance[i*2500+j]<ans:
          ans=distance[i*2500+j]
      print(ans)
    


if __name__ == '__main__':
    N,M,S=map(int,input().split())
    main()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools, bisect
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def S(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]

alphabets = "abcdefghijklmnopqrstuvwxyz"
ALPHABETS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"

sys.setrecursionlimit(1000000)
dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
MOD = 1000000007
INF = float("inf")

def main():
    N, M, S = LI()
    UVAB = LIR(M)
    CD = LIR(N)

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

    dist = [[INF] * 2500 for _ in range(N)]
    heap = [(0, 0, min(2500, S))]

    while heap:
        cost, u, s = heappop(heap)
        c, d = CD[u]

        if s + c < 2500 and dist[u][s + c] > cost + d:
            dist[u][s + c] = cost + d
            heappush(heap, (cost + d, u, s + c))
        for v, a, b in edge[u]:
            if s - a >= 0 and dist[v][s - a] > cost + b:
                dist[v][s - a] = cost + b
                heappush(heap, (cost + b, v, s - a))

        # print(heap)

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

if __name__ == '__main__':
    main()

Submission status: Accepted

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, -S, 0)]  # 時間、現在地、銀貨の数
while que:
    time, silver, now = heapq.heappop(que)
    silver = -silver
    if dist[now][silver] < time:
        continue
    # 両替する
    c, d = CD[now]
    n = 1
    while silver + c * n <= U:
        if dist[now][silver + c * n] > time + n * d:
            dist[now][silver + c * n] = time + n * d
            heapq.heappush(que, (time + n * d, -(silver + c * n), now))
            n += 1
        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, -(silver - s), nxt))

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

Submission status: Accepted

Solution code:
from heapq import heappop,heappush
n,m,s=map(int,input().split())
g=[[]for i in range(n)]
x=0
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])
    x=max(x,a)
for i in range(n):
    c,d=map(int,input().split())
    g[i].append([i,-c,d])
x*=(n-1)
t=[[2**64 for i in range(x+1)]for i in range(n)]
q=[]
heappush(q,(0,0,s))
while q:
    a,b,c=heappop(q)
    for i,j,h in g[b]:
        if c>=j and a+h<t[i][min(x,c-j)]:
            t[i][min(x,c-j)]=a+h
            heappush(q,(a+h,i,c-j))
for i in range(1,n):
    print(min(t[i]))

Submission status: Accepted

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 = 1<<61
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]))