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


n, m, s = map(int, input().split())
if s >= 2500:
    s = 2499

edges = [[] for _ in range(n)]
for _ in range(m):
    from_, to, cost, time = map(int, input().split())
    edges[from_-1].append((to-1, cost, time))
    edges[to-1].append((from_-1, cost, time))

banks = [(0, 0) for _ in range(n)]
for i in range(n):
    coin, time = map(int, input().split())
    banks[i] = (coin, time)

INF = float('INF')
DP = [INF] * (n * 2500)
ans = [INF] * n


def to_one_dimension(node, coin):
    return node * 2500 + coin


def push_todo(node, coin, time):
    if coin < 0:
        return
    if time >= DP[to_one_dimension(node, coin)]:
        return
    heapq.heappush(todo, (time, node, coin))


def charge(node, current_coin, current_time):
    coin, time = banks[node]
    new_coin = current_coin + coin
    if new_coin >= 2500:
        new_coin = 2499
    push_todo(node, new_coin, current_time+time)


todo = [(0, 0, s)]
while todo:
    current_time, node, current_coin = heapq.heappop(todo)
    if current_time < ans[node]:
        ans[node] = current_time

    one_d_idx = to_one_dimension(node, current_coin)
    if current_time >= DP[one_d_idx]:
        continue

    DP[one_d_idx] = current_time
    charge(node, current_coin, current_time)

    for to, cost, time in edges[node]:
        push_todo(to, current_coin-cost, current_time+time)

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

Submission status: Accepted

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate, product
import sys
import bisect
import string
import math
import time

def I(): return int(input())
def S(): return input()
def MI(): return map(int, input().split())
def MS(): return map(str, input().split())
def LI(): return [int(i) for i in input().split()]
def LI_(): return [int(i)-1 for i in input().split()]
def StoI(): return [ord(i)-97 for i in input()]
def ItoS(nn): return chr(nn+97)
def input(): return sys.stdin.readline().rstrip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]

class NeighborList():
    def __init__(self):
        self.neighbor = {}


class Dijkstra(object):
    def dijkstra(self, adj, start, goal=None):
        '''
        ダイクストラアルゴリズムによる最短経路を求めるメソッド
        入力
        adj: adj[i][j]の値が頂点iから頂点jまでの距離(頂点iから頂点jに枝がない場合，値はfloat('inf'))となるような2次元リスト(正方行列)
        start: 始点のID
        goal: オプション引数．終点のID
        出力
        goalを引数に持つ場合，startからgoalまでの最短経路を格納したリストを返す
        持たない場合は，startから各頂点までの最短距離を格納したリストを返す
        '''
        dist = {} # 始点から各頂点までの最短距離を格納する
        prev = {} # 最短経路における，その頂点の前の頂点のIDを格納する

        dist[start] = 0
        prev[start] = 0
        q = []                  # プライオリティキュー．各要素は，(startからある頂点vまでの仮の距離, 頂点vのID)からなるタプル
        heappush(q, (0, start)) # 始点をpush

        while len(q) != 0:
            prov_cost, src = heappop(q) # pop

            # プライオリティキューに格納されている最短距離が，現在計算できている最短距離より大きければ，distの更新をする必要はない
            if dist[src] < prov_cost:
                continue

            # 他の頂点の探索
            for dest in adj[src].neighbor.keys():
                cost = adj[src].neighbor[dest]#src→destのチェック

                if dest in dist.keys():
                    if dist[dest] > dist[src] + cost:#先のコスト(仮決定) > 今のコスト+移動するのにかかるコスト
                        dist[dest] = dist[src] + cost # distの更新
                        heappush(q, (dist[dest], dest)) # キューに新たな仮の距離の情報をpush
                        prev[dest] = src                      # 前の頂点IDを記録
                else:#訪れたことが無ければ
                    dist[dest] = dist[src] + cost # distの更新
                    heappush(q, (dist[dest], dest)) # キューに新たな仮の距離の情報をpush
                    prev[dest] = src                      # 前の頂点IDを記録

        if goal is not None:
            return self.get_path(start,goal, prev)
        else:
            return dist

    def get_path(self, start, goal, prev):
        '''
        始点startから終点goalまでの最短経路を求める
        '''
        path = [goal]           # 最短経路
        dest = goal

        # 終点から最短経路を逆順に辿る
        while prev[dest] != start:
            path.append(prev[dest])
            dest = prev[dest]

        path.append(start)

        # 経路をreverseして出力
        return list(reversed(path))


yn = {False: 'No', True: 'Yes'}
YN = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**19
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']

show_flg = False
# show_flg = True

MX = 2500

def trans(e, s):
    return MX * e + s


def main():
    N, M, S = MI()
    U = [0] * M
    V = [0] * M
    A = [0] * M
    B = [0] * M
    C = [0] * N
    D = [0] * N
    edges = [[] for i in range(N)]
    # cost = [[] for i in range(N * MX)]
    adj = {i:NeighborList() for i in range(N * MX)}

    for i in range(M):
        U[i], V[i], A[i], B[i] = MI()
        U[i] -= 1
        V[i] -= 1
        edges[U[i]].append((V[i], i))
        edges[V[i]].append((U[i], i))

    for i in range(N):
        C[i], D[i] = MI()

    for i in range(N):
        for j in range(0, MX):
            to = min(j + C[i], MX-1)
            # cost[trans(i, j)][trans(i, to)] = D[i]
            adj[trans(i, j)].neighbor[trans(i, to)] = D[i]
            for pair in edges[i]:
                to = pair[0]
                idx = pair[1]
                if j - A[idx] >= 0:
                    # cost[trans(i, j)][trans(to, j - A[idx])] = B[idx]
                    adj[trans(i, j)].neighbor[trans(to, j - A[idx])] = B[idx]

    S = min(2499, S)
    # print('S', S)
    d = Dijkstra()
    ret = d.dijkstra(adj, trans(0, S))
    # ret = dijkstra(cost, trans(0, S))

    # print()
    # for i in range(1, N):
    #     print(i, *['IINF' if v == IINF else "{:0=4}".format(v) for v in cost[i]])

    for i in range(1, N):
        ans = IINF
        for j in range(MX):
            # if j <= 4:
            #     print(i, j, cost[i][j])
            ans = min(ans, ret[trans(i, j)])
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import heapq
import sys

input = sys.stdin.readline

inf = 10**13

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

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

sumA = 0

for i in range(M):
    U,V,A,B = map(int,input().split())
    sumA += A
    U -= 1
    V -= 1
    data[U].append((B,V,A))###(距離, 行き先, 費用)
    data[V].append((B,U,A))###(距離, 行き先, 費用)

P = sumA

C = [0]*N
D = [0]*N

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

dist = [[inf]*(P+1) for _ in range(N)]
#visit = [[0]*(P+1) for _ in range(N)]
###heapにぶち込んだことがあるかないか

q = [(0,0,min(S,P))]###(仮の最短距離, 頂点番号, 所持金)
heapq.heapify(q)

while q:
    v = heapq.heappop(q)
    if v[0] >= dist[v[1]][v[2]]:
        continue
    dist[v[1]][v[2]] = v[0]

    if v[2] + C[v[1]] <= P:
        if dist[v[1]][v[2]+C[v[1]]] == inf:
            heapq.heappush(q,(v[0]+D[v[1]],v[1],v[2]+C[v[1]]))

    for x in data[v[1]]:
        if x[2] > v[2]:
            continue
        if dist[x[1]][v[2]-x[2]] == inf:
            heapq.heappush(q,(v[0]+x[0],x[1],v[2]-x[2]))
    
    ###
    #print(P)
    #print(q)
    #print(v)
    ###

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

Submission status: Accepted

Solution code:
from heapq import heappop, heappush
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline


phi = lambda city, silver: city * 2501 + silver
psi = lambda x: (x//2501, x % 2501)


n, m, s = map(int, input().split())
g = [[] for _ in range(n*2501+1)]

for i in range(m):
    u, v, a, b = map(int, input().split())
    for j in range(2501):
        if j-a >= 0:
            g[phi(u-1, j)].append((phi(v-1, j-a), b))
            g[phi(v-1, j)].append((phi(u-1, j-a), b))

for i in range(n):
    c, d = map(int, input().split())
    for j in range(2501):
        if j + c <= 2500:
            g[phi(i, j)].append((phi(i, j+c), d))


def dijkstra(s, n, g):
    # g[i][j] : the cost of i→j  or g[i] = [(target, cost), ...]
    # must import heapq
    # sys.stdin.readline is recommended
    d = [10**18] * n
    d[s] = 0
    q = [(0, s)]
    while q:
        dist_u, u = heappop(q)
        if d[u] < dist_u:
            continue
        for v, c in g[u]:  # 'in g[u]' if g is an adj list.
            if d[v] > dist_u + c:
                d[v] = dist_u + c
                heappush(q, (d[v], v))
    return d


s = min(s, 2500)
d = dijkstra(phi(0, s), n*2501+1, g)

for i in range(1, n):
    print(min(d[phi(i, 0):phi(i+1, 0)]))

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from operator import mul


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n, m, s = LI()
G = [[] for _ in range(n)]
for _ in range(m):
    u, v, a, b = LI()
    G[u - 1] += [(v - 1, a, b)]
    G[v - 1] += [(u - 1, a, b)]

change = LIR(n)

def dijkstra(s):
    hq = [(0, 0, s)]
    dist = [[INF] * 2451 for _ in range(n)]
    dist[0][s] = 0
    while hq:
        t, u, coin = heappop(hq)
        if t > dist[u][coin]:
            continue
        if t + change[u][1] < dist[u][min(2450, coin + change[u][0])]:
            dist[u][min(2450, coin + change[u][0])] = t + change[u][1]
            heappush(hq, (t + change[u][1], u, min(2450, coin + change[u][0])))
        for v, c, d in G[u]:
            if coin - c >= 0 and t + d < dist[v][coin - c]:
                dist[v][coin - c] = t + d
                heappush(hq, (t + d, v, coin - c))
    return dist

D = dijkstra(min(2450, s))
for t in range(1, n):
    print(min(D[t]))

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from operator import mul


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n, m, s = LI()
G = [[] for _ in range(n)]
for _ in range(m):
    u, v, a, b = LI()
    G[u - 1] += [(v - 1, a, b)]
    G[v - 1] += [(u - 1, a, b)]

change = LIR(n)

def dijkstra(s):
    hq = [(0, 0, s)]
    dist = [[INF] * 2451 for _ in range(n)]
    dist[0][s] = 0
    while hq:
        t, u, coin = heappop(hq)
        if t > dist[u][coin]:
            continue
        dist[u][coin] = t
        if t + change[u][1] < dist[u][min(2450, coin + change[u][0])]:
            dist[u][min(2450, coin + change[u][0])] = t + change[u][1]
            heappush(hq, (t + change[u][1], u, min(2450, coin + change[u][0])))
        for v, c, d in G[u]:
            if coin - c >= 0 and t + d < dist[v][coin - c]:
                dist[v][coin - c] = t + d
                heappush(hq, (t + d, v, coin - c))
    return dist

D = dijkstra(min(2450, s))
for t in range(1, n):
    print(min(D[t]))

Submission status: Accepted

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

INF = 10**19
n, m, s = map(int, input().split())
edges = defaultdict(lambda: defaultdict(lambda: [INF, INF]))
cd = []
max_a = 0

for i in range(m):
    u, v, a, b = map(int, input().split())
    max_a = max(max_a, a)
    edges[u-1][v-1] = [a, b]
    edges[v-1][u-1] = [a, b]

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

# 解答ACする
# Dijakstraの状態を(頂点、所持している銀貨の枚数, cost)で持つ
SIZE = max_a * n + 1
# SIZE = 2550
if s > SIZE:
    s = SIZE
nodes = [[INF for _ in range(SIZE+1)] for _ in range(n)]
nodes[0][s] = 0

def dijakstra():
    goals = set({0})
    que = [(0, 0, s)]
    heapify(que)
    while 10**6 > len(que) > 0:
        if len(goals) >= n:
            break
        cost, num, silver = heappop(que)
        if num not in goals:
            goals.add(num)
        c, d = cd[num]
        s_tmp = min(SIZE, silver+c)
        if silver < SIZE and s_tmp != silver:
            if nodes[num][s_tmp] > cost + d:
                heappush(que, (cost + d, num, s_tmp))
                nodes[num][s_tmp] = min(nodes[num][s_tmp], cost + d)
        for v in edges[num].keys():
            a, b = edges[num][v]
            if silver >= a:
                if nodes[v][silver-a] > cost + b:
                    heappush(que, (cost + b, v, silver - a))
                    nodes[v][silver - a] = min(nodes[v][silver - a], cost + b)

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

Submission status: Accepted

Solution code:
from heapq import heappop, heappush

import sys
def input():return sys.stdin.readline().strip()

def main():
    N, M, S = map(int, input().split())
    to = [{} for _  in range(N)]
    for _ in range(M):
        u, v, a, b = map(int, input().split())
        u -= 1
        v -= 1
        to[u][v] = (a, b)
        to[v][u] = (a, b)
    info = tuple(tuple(map(int, input().split())) for _ in range(N))

    MAX_SILVER = 50 * (N-1)
    INF = 10 ** 18
    # dijkstra (time, vertex, money)
    visited = [[False]*(MAX_SILVER+1) for _ in range(N)]
    cost = [[INF]*(MAX_SILVER+1) for _ in range(N)]
    q = []
    S = min(S, MAX_SILVER)
    heappush(q, (0, 0, S)) # (time, vertex, silver)

    while q:
        t, now, s = heappop(q)
        if visited[now][s]:continue
        visited[now][s] = True
        cost[now][s] = t

        # next node
        for nv, (a, b) in to[now].items():
            nt = t + b
            rest = s - a
            if rest >= 0:
                if cost[nv][rest] <= nt : continue 
                heappush(q, (nt, nv, rest))
        
        # exchange gold with silver
        rate, time = info[now]
        nt = t + time
        ns = min(s+rate, MAX_SILVER)
        if cost[now][ns] <= nt : continue
        heappush(q, (nt, now, ns))
        
    
    for i in range(1, N):
        print(min(cost[i]))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from heapq import heappop, heappush

import sys
def input():return sys.stdin.readline().strip()

def main():
    N, M, S = map(int, input().split())
    to = [{} for _  in range(N)]
    for _ in range(M):
        u, v, a, b = map(int, input().split())
        u -= 1
        v -= 1
        to[u][v] = (a, b)
        to[v][u] = (a, b)
    info = tuple(tuple(map(int, input().split())) for _ in range(N))

    MAX_SILVER = 50 * (N-1)
    INF = 10 ** 18
    # dijkstra (time, vertex, money)
    visited = [[False]*(MAX_SILVER+1) for _ in range(N)]
    cost = [[INF]*(MAX_SILVER+1) for _ in range(N)]
    q = []
    S = min(S, MAX_SILVER)
    heappush(q, (0, 0, S)) # (time, vertex, silver)

    while q:
        t, now, s = heappop(q)
        if visited[now][s]:continue
        visited[now][s] = True
        cost[now][s] = t

        # next node
        for nv, (a, b) in to[now].items():
            nt = t + b
            rest = s - a
            if rest >= 0:
                if cost[nv][rest] <= nt : continue 
                heappush(q, (nt, nv, rest))
        
        # exchange gold with silver
        rate, time = info[now]
        nt = t + time
        ns = min(s+rate, MAX_SILVER)
        heappush(q, (nt, now, ns))
        
    
    for i in range(1, N):
        print(min(cost[i]))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# 解説と提出#12551970を参考に作成
# 今いる都市と銀貨の所持数を状態として、
#   ①その都市から移動可能な別の都市に移動する
#   ②金貨を銀貨に交換する
# のどちらかを行い、実施後の(同都市・同所持銀貨枚数での)最小時間を計測していく。
# 最小時間が更新された場合、さらにその状態から①・②を行う。
# これによって全都市・全銀貨所持枚数毎の最小時間を割り出す。
# 都市の銀貨所持枚数毎の最小時間の中での最小時間がその都市へ行くための最小時間になる。
#   ※1: 都市への移動は移動可能な枚数の銀貨を持っている場合のみ可能
#   ※2: 銀貨の最大所持枚数は (N - 1) * max(Ai) とする
#        -> 一番遠い都市に移動する場合にかかりうる最大の銀貨枚数

from heapq import heappop, heappush


def solve():
    n, m, s = map(int, input().split())
    graph = [[] for _ in range(n)]
    # グラフ作製
    max_a = 0
    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])
        max_a = max(max_a, a)
    ce = [[int(i) for i in input().split()] for _ in range(n)]
    # 初期値マップ作製
    maxSilver = max_a * (n - 1)  # max(a) * (n - 1)
    inf = float('inf')
    ns_map = [[inf] * (maxSilver + 1) for _ in range(n)]
    # スタート時の値設定と探索
    q = [[0, 0, min(maxSilver, s)]]  # 累計時間, 都市, 所持銀貨
    ns_map[0][min(maxSilver, s)] = 0  # スタート地点の時刻は0
    while q:
        ti, ni, si = heappop(q)
        # 移動
        for g in graph[ni]:
            n2, ai, bi = g
            if si >= ai and ns_map[n2][si - ai] > ti + bi:
                ns_map[n2][si - ai] = ti + bi
                # ★heapq で累計時間が少ない情報から先に処理するようにする.
                # これによって処理速度が全然違う
                heappush(q, [ti + bi, n2, si - ai])
        # 換金
        ci, di = ce[ni]
        ti += di
        si = min(si + ci, maxSilver)
        if ns_map[ni][si] > ti:
            ns_map[ni][si] = ti
            heappush(q, [ti, ni, si])
    for i in range(1, n):
        print(min(ns_map[i]))


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
# 解説と提出#12551970を参考に作成
# 今いる都市と銀貨の所持数を状態として、
#   ①その都市から移動可能な別の都市に移動する
#   ②金貨を銀貨に交換する
# のどちらかを行い、実施後の(同都市・同所持銀貨枚数での)最小時間を計測していく。
# 最小時間が更新された場合、さらにその状態から①・②を行う。
# これによって全都市・全銀貨所持枚数毎の最小時間を割り出す。
# 都市の銀貨所持枚数毎の最小時間の中での最小時間がその都市へ行くための最小時間になる。
#   ※1: 都市への移動は移動可能な枚数の銀貨を持っている場合のみ可能
#   ※2: 銀貨の最大所持枚数は (N - 1) * max(Ai) とする
#        -> 一番遠い都市に移動する場合にかかりうる最大の銀貨枚数

from heapq import heappop, heappush


def solve():
    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])
    ce = [[int(i) for i in input().split()] for _ in range(n)]
    # 初期値マップ作製
    maxSilver = 50 * 49  # max(a) * (n - 1)
    inf = float('inf')
    ns_map = [[inf] * (maxSilver + 1) for _ in range(n)]
    # スタート時の値設定と探索
    q = [[0, 0, min(maxSilver, s)]]  # 累計時間, 都市, 所持銀貨
    ns_map[0][min(maxSilver, s)] = 0  # スタート地点の時刻は0
    while q:
        ti, ni, si = heappop(q)
        # 移動
        for g in graph[ni]:
            n2, ai, bi = g
            if si >= ai and ns_map[n2][si - ai] > ti + bi:
                ns_map[n2][si - ai] = ti + bi
                # ★heapq で累計時間が少ない情報から先に処理するようにする.
                # これによって処理速度が全然違う
                heappush(q, [ti + bi, n2, si - ai])
        # 換金
        ci, di = ce[ni]
        ti += di
        si = min(si + ci, maxSilver)
        if ns_map[ni][si] > ti:
            ns_map[ni][si] = ti
            heappush(q, [ti, ni, si])
    for i in range(1, n):
        print(min(ns_map[i]))


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
from heapq import heappop, heappush
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline


def phi(city, silver):
    return city*2501+silver


def psi(x):
    city = x//2501
    silver = x % 2501
    return city, silver


n, m, s = map(int, input().split())
g = [[] for _ in range(n*2501+1)]

for i in range(m):
    u, v, a, b = map(int, input().split())
    for j in range(2501):
        if j-a >= 0:
            g[phi(u-1, j)].append((phi(v-1, j-a), b))
            g[phi(v-1, j)].append((phi(u-1, j-a), b))

for i in range(n):
    c, d = map(int, input().split())
    for j in range(2501):
        if j + c <= 2500:
            g[phi(i, j)].append((phi(i, j+c), d))


def dijkstra(s, n, g):
    # g[i][j] : the cost of i→j  or g[i] = [(target, cost), ...]
    # must import heapq
    # sys.stdin.readline is recommended
    d = [10**18] * n
    d[s] = 0
    q = [(0, s)]
    while q:
        dist_u, u = heappop(q)
        if d[u] < dist_u:
            continue
        for v, c in g[u]:  # 'in g[u]' if g is an adj list.
            if d[v] > dist_u + c:
                d[v] = dist_u + c
                heappush(q, (d[v], v))
    return d


s = min(s, 2500)
d = dijkstra(phi(0, s), n*2501+1, g)

for i in range(1, n):
    print(min(d[phi(i, 0):phi(i+1, 0)]))

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
inf = 1 << 60
mod = 1000000007
 
ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

from heapq import *

n, m, s = na()
uvab = nan(m)
cd = nan(n)
maxS = 5007
s = min(s, maxS)

g = [[] for _ in range(n)]
for i in range(m):
    u, v, a, b = uvab[i]
    u -= 1
    v -= 1
    g[u].append((v, (a, b)))
    g[v].append((u, (a, b)))

def dijkstra(g, x):
    dist = [[inf] * (maxS + 1) for _ in range(len(g))]
    dist[x][s] = 0
    q = []
    # proc = [False for _ in range(len(g))]
    heappush(q, (0, (x, s)))
    while len(q):
        p = heappop(q)
        a = p[1][0]
        cost = p[0]
        curS = p[1][1]
        # if proc[a]:
        #	  continue
        # proc[a] = True
        for b in g[a]:
            to = b[0]
            ncost = cost + b[1][1]
            nS = curS - b[1][0]
            if nS >= 0:
                if dist[to][nS] > ncost:
                    dist[to][nS] = ncost
                    heappush(q, (ncost, (to, nS)))
        
        c, d = cd[a]
        cost += d
        curS += c
        curS = min(curS, maxS)
        if dist[a][curS] > cost:
            dist[a][curS] = cost
            heappush(q, (cost, (a, curS)))
    
    return dist

dist = dijkstra(g, 0)
for i in range(1, n):
    ans = inf
    for j in range(maxS):
        ans = min(ans, dist[i][j])
    print(ans)

Submission status: Accepted

Solution code:
N, M, S = map(int,input().split())
ubab = [list(map(int, input().split())) for _ in range(M)]
cd = [list(map(int, input().split())) for _ in range(N)]

from heapq import heappush, heappop

routes = [[] for _ in range(N)]
max_money = 0
for u, v, a, b in ubab:
    routes[u-1].append([b, -a, v-1]) #★注意★[コスト、お金、要素]
    routes[v-1].append([b, -a, u-1])
    if a > max_money:
        max_money = a

for i, (c, d) in enumerate(cd):
    routes[i].append([d,+c,i])

max_pocessing = max_money * (N-1)

minimum = [[10e+1000 for _ in range(max_pocessing+1)] for _ in range(N)] 
if S>max_pocessing:
    S = max_pocessing
minimum[0][S] = 0
last_num = 0
last_money = S # [地点番号、所持金]
hp = []


while True:
    for cost, money, num in routes[last_num]:
        if last_money+money >= max_pocessing:
            money = max_pocessing - last_money
        if minimum[num][last_money+money] == 10e+1000:
            heappush(hp, (minimum[last_num][last_money]+cost, last_money+money, num))    
    while len(hp)>0:
        candidate_cost, candidate_money, candidate_num = heappop(hp)
        if minimum[candidate_num][candidate_money] == 10e+1000 and candidate_money >= 0:
            break
    else:
        break
    last_num = candidate_num
    last_money = candidate_money
    minimum[candidate_num][candidate_money] = candidate_cost

for each_minimum in minimum[1:]:
    print(min(each_minimum))

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.buffer.readline
from heapq import heappop,heappush,heapify
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))
cd=[tuple(map(int,input().split())) for _ in range(N)]
INF=1e18
S=min(S,2500)
time=[[INF]*2501 for _ in range(N)]
q=[(0,0,S)]
heapify(q)
while q:
  now_time,cur_city,cur_coin=heappop(q)
  for nxt_city,cost,dt in graph[cur_city]:
    if cur_coin>=cost and time[nxt_city][cur_coin-cost]>now_time+dt:
      time[nxt_city][cur_coin-cost]=now_time+dt
      heappush(q,(now_time+dt,nxt_city,cur_coin-cost))
  c,d=cd[cur_city]
  new_coin=min(2500,cur_coin+c)
  nxt_time=now_time+d
  if nxt_time<time[cur_city][new_coin]:
    time[cur_city][new_coin]=nxt_time
    heappush(q,(nxt_time,cur_city,new_coin))
for i in range(1,N):
  print(min(time[i]))