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:
from heapq import heappop, heappush
n, m, s = map(int, input().split())
edges = [[[] for _ in range(2501)] for _ in range(n)]

for _ in range(m):
    u, v, a, b = map(int, input().split())
    for x in range(2501):
        if x - a >= 0:
            edges[u-1][x].append((b, v-1, x-a))
            edges[v-1][x].append((b, u-1, x-a))

for i in range(n):
    c, d = map(int, input().split())
    for x in range(2500):
        edges[i][x].append((d, i, min(2500, x+c)))

inf = 1e15
d = [[inf for _ in range(2501)] for _ in range(n)]
s = min(s, 2500)
def dijkstra():
    que = []
    d[0][s] = 0
    heappush(que, (0, 0, s))

    while len(que):
        dist, city, coins = heappop(que)

        if d[city][coins] < dist:
            continue
        for cost, to_city, to_coins in edges[city][coins]:
            if d[to_city][to_coins] > dist + cost:
                d[to_city][to_coins] = dist + cost
                heappush(que, (d[to_city][to_coins], to_city, to_coins))


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

Submission status: Accepted

Solution code:
import heapq
n,m,s = map(int,input().split())
lst_graph = [list(map(int,input().split())) for _ in range(m)]
lst_cd = [list(map(int,input().split())) for _ in range(n)]
graph = [[] for _ in range(2501*n)]

#頂点番号と残金から拡張した頂点番号に変換
def f(x,c):
    if c >= 2500:
        c = 2500
    return (x-1)*2501+c


#拡張グラフ作成
for i in range(m):
    u,v,a,b = lst_graph[i]
    for c in range(2501):
        if c >= a:
            graph[f(u,c)].append((b,f(v,c-a)))
            graph[f(v,c)].append((b,f(u,c-a)))
for i in range(1,n+1):
    x,time = lst_cd[i-1]
    for c in range(2500):
        graph[f(i,c)].append((time, f(i,c+x)))


#ダイクストラ
def dijkstra_heap(s,edge):
    d = [float("inf")]*(2501*n)
    used = [True]*(2501*n)
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v],e[1]))
    return d

ans = dijkstra_heap(f(1,s),graph)
for i in range(1,n):
    print(min(ans[(2501*i):(2501*i+2501)]))

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
from heapq import heapify, heappop, heappush

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# 銀貨を何枚持っているかの状態数、N*2501の都市, dijkstra
N, M, S = lr()
limit = 2500
S = min(S, limit)
graph = [[] for _ in range((N+1) * (limit+1))]  # 1-indexed
for _ in range(M):
    u, v, a, b = lr()
    for x in range(a, limit+1):
        graph[u*(limit+1) + x].append(((v*(limit+1)+x-a), b))
        graph[v*(limit+1) + x].append(((u*(limit+1)+x-a), b))

for i in range(N):
    i += 1
    c, d = lr()
    for x in range(limit-c+1):
        graph[i*(limit+1) + x].append((i*(limit+1) + x + c, d))

def dijkstra(start):
    INF = 10 ** 15
    dist = [INF] * ((N+1) * (limit+1))
    dist[start] = 0
    que = [(0, start)]
    while que:
        d, prev = heappop(que)
        if dist[prev] < d:
            continue
        for next, time in graph[prev]:
            d1 = d + time
            if dist[next] > d1:
                dist[next] = d1
                heappush(que, (d1, next))
    return dist

dist = dijkstra(1*(limit+1)+S)
for i in range(2, N+1):
    answer = min(dist[i*(limit+1):(i+1)*(limit+1)])
    print(answer)

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
from heapq import heapify, heappop, heappush

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# 同じ地点で銀貨の枚数によって別の状態として扱う（最大max(A)*(N-1))
N, M, S = lr()
UVAB = [lr() for _ in range(M)]
CD = [lr() for _ in range(N)]  # 0-indexed
Amax = 0
for i in range(M):
    a = UVAB[i][2]
    if a > Amax:
        Amax = a

limit = Amax*(N-1)
S = min(S, limit)
graph = [[] for _ in range(N+1)] # 1-indexed
for u, v, a, b in UVAB:
    graph[u].append((v, a, b))
    graph[v].append((u, a, b))

def dijkstra(start):
    # 時間、銀貨の枚数、現在地をqueへ
    INF = 10 ** 15
    dist = [[INF for _ in range(limit+1)] for _ in range(N+1)]
    dist[1][S] = 0
    que = [(0, S, 1)]
    while que:
        time, silver, prev = heappop(que)
        if dist[prev][silver] < time:
            continue
        for next, a, b in graph[prev]:
            t = time + b
            si = silver - a
            if si < 0:
                continue
            if dist[next][si] > t:
                dist[next][si] = t
                heappush(que, (t, si, next))
        c, d = CD[prev-1]
        si = min(limit, silver+c)
        while dist[prev][si] > time + d:
            dist[prev][si] = time + d
            heappush(que, (time+d, si, prev))
            si += c; si = min(limit, si)
            time += d
            
    return dist

dist = dijkstra(1)
for i in range(2, N+1):
    d = dist[i]
    answer = min(d)
    print(answer)

# 前解いたものをPyPyで

Submission status: Accepted

Solution code:
import heapq as hq
N,M,S = list(map(int, input().split()))
#Edge
E = [[] for _ in range(N)]
  
for _ in range(M):
  # U <-> V, A coins, B mins
  u,v,a,b = list(map(int, input().split()))
  # 0-indexed
  E[u-1].append([v-1, a, b])
  E[v-1].append([u-1, a, b])

# City
C = []
for _ in range(N):
  # C coins, D mins
  C.append(list(map(int, input().split())))
  
# dp[p][i] 点Pにたどり着いた時、i円持っている時の最小時間
MAXYEN = 50 * N
dp = [[ 1e18 for i in range(MAXYEN + 5) ] for _ in range(N)]
S = min(MAXYEN, S)
dp[0][S] = 0

# 状態は点とお金と時間. time, pointindex, money
Q = []
hq.heapify(Q)
hq.heappush(Q, [0,0,S])

while len(Q) > 0:
  nowt, nowi, nowm = hq.heappop(Q)
  #print("Pop :", nowt, nowi, nowm)
  # Edgeをわたる。a yen払ってB時間かけて、Vに移動する。
  for e in E[nowi]:
    to_i, costm, costt = e
    #print("Edge:", to_i, costm, costt)
    if nowm - costm < 0:
      # unreachable 
      continue
    if dp[to_i][nowm-costm] > dp[nowi][nowm] + costt:
      dp[to_i][nowm-costm] = dp[nowi][nowm] + costt
      hq.heappush(Q, [dp[nowi][nowm] + costt, to_i, nowm-costm])
      
  # その場でお金を1回買う。移動せず、CYenGetして、D時間かける
  getm, costt = C[nowi]
  targetm = min(MAXYEN, nowm + getm)
  #print("Buy :", getm, targetm, costt)
  if dp[nowi][targetm] > dp[nowi][nowm] + costt:
    dp[nowi][targetm] = dp[nowi][nowm] + costt
    hq.heappush(Q, [dp[nowi][targetm], nowi, targetm])
  
for i in range(1,N):
  print(min(dp[i]))

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict, Counter, namedtuple, deque
import itertools
import functools
import bisect
import heapq
import math

# MOD = 10 ** 9 + 7
MOD = 998244353
# sys.setrecursionlimit(10**8)

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

G = [[] for _ in range(N)]
for i in range(M):
    u, v, s, t = map(int, input().split())
    G[u-1].append([v-1, s, t])
    G[v-1].append([u-1, s, t])

change_rate, change_cost = [], []
for i in range(N):
    rate, cost = map(int, input().split())
    change_rate.append(rate)
    change_cost.append(cost)

# dp[i][silver] = 頂点iにいて、銀貨をsilver枚持つときの最小時間
dp = [[float('inf')] * (MAX_COST + 1) for _ in range(N)]
dp[0][S] = 0

# time,node,silver
pq = [(0, 0, S)]
while pq:
    time, node, silver = heapq.heappop(pq)

    # going through exchange station
    next_silver = min(silver + change_rate[node], MAX_COST)
    next_time = time + change_cost[node]
    if next_time < dp[node][next_silver]:
        dp[node][next_silver] = next_time
        heapq.heappush(pq, (next_time, node, next_silver))

    for nei, ns, nt in G[node]:
        remain_silver = min(silver - ns, MAX_COST)
        next_time = time + nt
        if remain_silver >= 0 and next_time < dp[nei][remain_silver]:
            dp[nei][remain_silver] = next_time
            heapq.heappush(pq, (next_time, nei, remain_silver))

for d in dp[1:]:
    print(min(d))

Submission status: Accepted

Solution code:
import heapq
N,M,S = map(int,input().split())
MAX_COST = 2500
S = min(S, MAX_COST)

G = [ [] for _ in range(N) ]
for i in range(M):
  u,v,s,t = map(int,input().split())
  u, v = u-1, v-1
  G[u].append([v, s, t])
  G[v].append([u, s, t])

change_rate, change_cost = [], []
for i in range(N):
  rate, cost = map(int,input().split())
  change_rate.append(rate)
  change_cost.append(cost)

# dp[i][silver] = 頂点iにいて、銀貨をsilver枚持つときの最小時間
dp = [ [float('inf')]*(MAX_COST+1) for _ in range(N) ]
dp[0][S] = 0

# time,node,silver
pq = [(0,0,S)]
while pq:
  time,node,silver = heapq.heappop(pq)

  # going through exchange station
  next_silver = min(silver + change_rate[node], MAX_COST)
  next_time = time + change_cost[node]
  if next_time < dp[node][next_silver]:
    dp[node][next_silver] = next_time
    heapq.heappush(pq, (next_time, node, next_silver))

  for nei, ns, nt in G[node]:
    remain_silver = min(silver - ns, MAX_COST)
    if remain_silver < 0: continue

    next_time = time + nt
    if dp[nei][remain_silver] > next_time:
      dp[nei][remain_silver] = next_time
      heapq.heappush(pq, (next_time, nei, remain_silver))

for d in dp[1:]:
  print(min(d))

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
import sys
n, m, s = map(int, input().split())
edges = list()
for _ in range(m):
  new_u, new_v, new_a, new_b = map(int, input().split())
  edges.append((new_u-1, new_v-1, new_a, new_b))
coins_range = (n-1)*max(edges,key=lambda item:item[2])[2]+1
c, d = list(), list()
for _ in range(n):
  new_c, new_d = map(int, input().split())
  c.append(new_c)
  d.append(new_d)
adjacency = {(i, j): [] for i in range(n) for j in range(coins_range)}
for (node, coins) in adjacency.keys():
  new_coins = coins+c[node]
  if new_coins<=coins_range-1:
    adjacency[(node, coins)].append(((node, coins+c[node]), (d[node])))
for edge in edges:
  node1, node2, cost, weight = edge
  for coins in range(cost, coins_range):
    adjacency[(node1, coins)].append(((node2, coins-cost), weight))
    adjacency[(node2, coins)].append(((node1, coins-cost), weight))
def dijkstra():
  while state_heap:
    distance, state = heappop(state_heap)
    if visited[state]:
      continue
    visited[state] = True
    for (new_state, weight) in adjacency[state]:
      if not visited[new_state]:
        distances[new_state] = min(distances[new_state], distance+weight)
        heappush(state_heap, (distances[new_state], new_state))
distances = {(i, j): float("inf") for i in range(n) for j in range(coins_range)}
initial_state = (0, min(s, coins_range-1))
distances[initial_state] = 0
state_heap = []
heappush(state_heap, (distances[initial_state], initial_state))
visited = {(i, j): False for i in range(n) for j in range(coins_range)}
dijkstra()
final_distances = [float("inf")]*n
for ((node, _), distance) in distances.items():
  final_distances[node] = min(final_distances[node], distance)
[print(distance) for distance in final_distances[1:]]

Submission status: Accepted

Solution code:
from collections import defaultdict
from heapq import heappop, heappush


class Graph(object):
    """
    隣接リストによる有向グラフ
    """

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    """
    ダイクストラ法（二分ヒープ）による最短経路探索
    計算量: O((E+V)logV)
    """

    def __init__(self, graph, start):
        self.g = graph.graph

        # startノードからの最短距離
        # startノードは0, それ以外は無限大で初期化
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        # 最短経路での1つ前のノード
        self.prev = defaultdict(lambda: None)

        # startノードをキューに入れる
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            # 優先度（距離）が最小であるキューを取り出す
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        """
        startノードからgoalノードまでの最短距離
        """
        return self.dist[goal]

    def shortest_path(self, goal):
        """
        startノードからgoalノードまでの最短経路
        """
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]


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

G = Graph()
for u,v,a,b in uvab:
    u-=1
    v-=1
    u*=2501
    v*=2501
    for i in range(2500,a-1,-1):
        G.add_edge(u+i,v+i-a,b)
        G.add_edge(v+i,u+i-a,b)
for i,(c,d) in enumerate(cd):
    i*=2501
    for j in range(2501-c):
        G.add_edge(i+j,i+j+c,d)

s = min(s,2500)
dist = Dijkstra(G, s)
for i in range(1,n):
    ans = 10 ** 18
    for j in range(2501):
        goal = i * 2501 + j
        D = dist.shortest_distance(goal)
        ans = min(ans, D)
    print(ans)

Submission status: Accepted

Solution code:
import collections
import heapq

INF = 10 ** 18
MAX_S = 50*50+5

def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

class edge:
    def __init__(self, to, cost, t): self.to, self.cost, self.t = to, cost, t

def main():
    N, M, S = ZZ()
    C, D = [0]*(N+1), [0]*(N+1)
    E = collections.defaultdict(list)
    dist = [[INF] * (MAX_S+1) for _ in range(N+1)]

    for _ in range(M):
        u, v, a, b = ZZ()
        E[u].append(edge(v, a, b))
        E[v].append(edge(u, a, b))

    for i in range(1, N+1): C[i], D[i] = ZZ()

    S = min(S, MAX_S)
    dist[1][S] = 0

    que = list()
    heapq.heapify(que)
    heapq.heappush(que, [dist[1][S], 1, S])

    while que:
        x, v, s = heapq.heappop(que)
        if dist[v][s] < x: continue

        #遷移
        ns = min(s+C[v], MAX_S)
        if dist[v][ns] > x + D[v]:
            dist[v][ns] = x + D[v]
            heapq.heappush(que, [x+D[v], v, ns])

        #遷移
        for e in E[v]:
            if s - e.cost < 0: continue
            if dist[e.to][s-e.cost] > x + e.t:
                dist[e.to][s-e.cost] = x + e.t
                heapq.heappush(que, [x+e.t, e.to, s-e.cost])

    for i in range(2, N+1):
        output = INF
        for j in range(MAX_S+1): output = min(output, dist[i][j])
        print(output)
    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from heapq import heappop,heappush

def main():
    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])
    C=[]
    D=[]
    for _ in range(N):
        c,d=map(int,input().split())
        C.append(c)
        D.append(d)

    MaxMoney=2500

    dp=[[float('inf') for __ in range(MaxMoney+1)] for _ in range(N)]

    cost=0
    money=min(S,MaxMoney)
    que=[]
    heappush(que,(cost,0,money)) #cost,node,money
    dp[0][money] = 0

    while len(que)>0:
        cost,node,money=heappop(que)

        stop_money=min(money+C[node],MaxMoney)
        stop_cost=cost+D[node]
        if stop_cost<dp[node][stop_money]:
            dp[node][stop_money]=stop_cost
            heappush(que,(stop_cost,node,stop_money))

        for to_node,to_money,to_cost in G[node]:
            money_=min(money-to_money,MaxMoney)
            if money_<0:
                continue
            cost_=cost+to_cost
            if dp[to_node][money_]<=cost_:
                continue

            dp[to_node][money_]=cost_
            heappush(que,(cost_,to_node,money_))

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




if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
def main():
  n,m,s=map(int,input().split())
  uvab=[list(map(int,input().split())) for _ in range(m)]
  cd=[list(map(int,input().split())) for _ in range(n)]
  g=[[]for _ in range(n)]
  for u,v,a,b in uvab:
    g[u-1].append((v-1,a,b))
    g[v-1].append((u-1,a,b))
  import heapq
  inf=pow(10,21)
  max_s=50*50
  dp=[[inf]*(max_s+1)for _ in range(n)]
  kakutei=[[0]*(max_s+1)for _ in range(n)]
  dp[0][min(s,max_s)]=0
  todo=[[0,0,min(s,max_s)]] # [dp[v][i],v,i]
  heapq.heapify(todo)
  flgs=[0]*n
  flg=0
  ans=[inf]*n
  while flg<n:
    _,v,i=heapq.heappop(todo)
    if kakutei[v][i]==1:
      continue
    kakutei[v][i]=1
    if flgs[v]==0:
      flg+=1
      flgs[v]=1
    c,d=cd[v]
    ans[v]=min(ans[v],_)
    # 両替
    j=min(max_s,i+c)
    if kakutei[v][j]==0:
      dp[v][j]=min(dp[v][j],dp[v][i]+d)
      heapq.heappush(todo,[dp[v][j],v,j])
    # 鉄道
    l=g[v]
    for u,a,b in l:
      if i-a>=0 and kakutei[u][i-a]==0:
        dp[u][i-a]=min(dp[u][i-a],dp[v][i]+b)
        heapq.heappush(todo,[dp[u][i-a],u,i-a])
  print(*ans[1:],sep='\n')
if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
from heapq import heappop, heappush
import sys
def main():
    input = sys.stdin.readline
    N, M, S = map(int, input().split())
    G1 = [[] for _ in range(N)]
    for _ in range(M):
        u, v, a, b = map(int, input().split())
        u, v = u - 1, v - 1
        G1[u].append((b, a, v))
        G1[v].append((b, a, u))
    G2 = [tuple(map(int, input().split())) for _ in range(N)]

    q = [(0, (0, S))]
    T = [-1] * N
    lenT = 0
    visited = set()
    MX = 50 * (N - 1)
    while q:
        t, V = heappop(q)
        v, s = V
        if T[v] < 0:
            T[v] = t
            lenT += 1
            if lenT >= N: break
        if V in visited: continue
        visited.add(V)
        for dt, ds, to in G1[v]:
            if s < ds: continue
            nV = (to, s - ds)
            if nV in visited: continue
            heappush(q, (t + dt, nV))
        c, d = G2[v]
        if s + c <= MX:
            heappush(q, (t + d, (v, s + c)))
    for i in range(1, N):
        print(T[i])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding:utf-8 -*-

def solve():
    """解説実装"""
    import sys
    import heapq

    MAX_S = 50*50
    N, M, S = list(map(int, sys.stdin.readline().split()))
    graph = [[] for _ in range(N)]

    for _ in range(M):
        u, v, a, b = list(map(int, sys.stdin.readline().split()))
        u, v = u-1, v-1
        graph[u].append((v, a, b))
        graph[v].append((u, a, b))

    ryogae = []
    for _ in range(N):
        c, d = list(map(int, sys.stdin.readline().split()))
        ryogae.append((c, d))

    # dp[v][s] := 頂点vに所持金sで訪れるときの最小時間
    dp = [[float("inf") for _ in range(MAX_S+1)] for __ in range(N)]

    # ダイクストラ
    s = min(S, MAX_S)
    que = []
    heapq.heappush(que, (0, 0, s))  # (時刻t, 頂点番号v, 所持金s)

    while len(que) != 0:
        t, v, s = heapq.heappop(que)

        # if dp[v][s] != t: continue  # なにこれ？

        # 両替する場合
        c, d = ryogae[v]
        ns = min(s+c, MAX_S)
        if dp[v][ns] > t+d:
            dp[v][ns] = t+d
            heapq.heappush(que, (t+d, v, ns))

        # 移動する場合(v -> uに移動)
        for u, a, b in graph[v]:
            if s-a < 0: continue
            if dp[u][s-a] > t+b:
                dp[u][s-a] = t+b
                heapq.heappush(que, (t+b, u, s-a))

    for v in range(1, N):
        ans = float("inf")
        for s in range(MAX_S+1):
            ans = min(ans, dp[v][s])
        print(ans)


if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
# -*- coding:utf-8 -*-

def solve():
    import sys
    import heapq

    MAX_S = 50*50
    N, M, S = list(map(int, sys.stdin.readline().split()))
    graph = [[] for _ in range(N)]

    for _ in range(M):
        u, v, a, b = list(map(int, sys.stdin.readline().split()))
        u, v = u-1, v-1
        graph[u].append((v, a, b))
        graph[v].append((u, a, b))

    ryogae = []
    for _ in range(N):
        c, d = list(map(int, sys.stdin.readline().split()))
        ryogae.append((c, d))

    # dp[v][s] := 頂点vに所持金sで訪れるときの最小時間
    dp = [[float("inf") for _ in range(MAX_S+1)] for __ in range(N)]

    # ダイクストラ
    s = min(S, MAX_S)
    que = []
    heapq.heappush(que, (0, 0, s))  # (時刻t, 頂点番号v, 所持金s)
    # heapq.heappush(que, (0, s, 0))  # (頂点番号v, 所持金s, 時刻t)

    while len(que) != 0:
        t, v, s = heapq.heappop(que)
        # v, s, t = heapq.heappop(que)

        # if dp[v][s] != t: continue  # なにこれ？

        # 両替する場合
        c, d = ryogae[v]
        ns = min(s+c, MAX_S)
        if dp[v][ns] > t+d:
            dp[v][ns] = t+d
            heapq.heappush(que, (t+d, v, ns))
            # heapq.heappush(que, (v, ns, t+d))

        # 移動する場合(v -> uに移動)
        for u, a, b in graph[v]:
            if s-a < 0: continue
            if dp[u][s-a] > t+b:
                dp[u][s-a] = t+b
                heapq.heappush(que, (t+b, u, s-a))
                # heapq.heappush(que, (u, s-a, t+b))

    for v in range(1, N):
        ans = float("inf")
        for s in range(MAX_S+1):
            ans = min(ans, dp[v][s])
        print(ans)


if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import math
import fractions
from collections import deque
import itertools
import pprint
from heapq import *
N,M,S=map(int,input().split())
costtree={}                                                     #cost情報を格納costtree[頂点][coin数]
path=[[] for _ in range(N)]                                     #道情報
pathtime=[list(map(int,input().split())) for _ in range(M)]     #u,v,a,b(path情報と要するcoin,time)
cointime=[list(map(int,input().split())) for _ in range(N)]     #c,d(頂点ごとの一斉交換枚数,時間)
needtime=[[float("inf") for _ in range(N)] for _ in range(N)]   #path間の移動に必要な時間
needcoin=[[float("inf") for _ in range(N)] for _ in range(N)]   #path間の移動に必要なcoin数
change=[]
for i in range(N):
    costtree[i]={}
    for j in range(2501):
        costtree[i][j]=float("inf")
#print(costtree[0])
for i in pathtime:
    u,v,a,b=i
    needcoin[u-1][v-1]=a
    needcoin[v - 1][u - 1] = a
    needtime[u-1][v-1]=b
    needtime[v - 1][u - 1] = b
    path[u-1].append(v-1)
    path[v-1].append(u-1)
for i in cointime:
    c,d=i
    change.append([c,d])                                        #各点の[一度に両替するcoin数,時間]を格納
#print(needcoin,needtime,change,path)
costtree[0][min(S,2500)]=0                                      #costtreeは頂点0、min(S,2500)枚のコイン所持で0コストスタート
q=[(0,0,min(S,2500))]                                           #[cost,頂点,coin数]の組
heapify(q)
#print("ok")
#input()
value=0
nextcoin=0
while len(q)>0:
    cost,u,coin=heappop(q)                                      #[現時点の最小コスト,頂点,所持コイン数]をパージ
    if costtree[u][coin]<cost: continue                         #popしたコストが現存するコストを超えるなら無視
    if coin>0:                                                  #coinが0枚以上で
        if costtree[u][coin-1]>cost:                            #(cost0で)1枚捨てた時のコストが現存コストを下回るなら
            costtree[u][coin-1]=cost                            #捨てるようcost更新
            heappush(q,[cost,u,coin-1])                         #捨てた状態をqにpush
    nextcoin=min(coin+change[u][0],2500)                        #続いて、ここでコイン交換することを考え、交換した後の枚数を求める(2500枚を超えるなら明らかに2500枚で切って問題ないことに注意)
    value=costtree[u][nextcoin]                                 #交換あとの現存コスト
    if value>cost+change[u][1]:                                 #現存コストが、ここで交換する時より高いなら
        costtree[u][nextcoin]=cost+change[u][1]                 #ここで交換するようcostを更新し
        heappush(q,[cost+change[u][1],u,nextcoin])              #交換あとの状態をqにpush
    for j in path[u]:                                           #uから出るpathでたどりつく頂点jを考えます
        nextcoin=coin-needcoin[u][j]                            #jにたどり着いたときのコイン数
        if nextcoin>=0:                                         #コインが残っているなら
            value=costtree[j][nextcoin]                         #行き先の現存costを算出
            if value > cost + needtime[u][j]:                   #現存コストが、ここへ移動する時より高いなら
                costtree[j][nextcoin]=cost+needtime[u][j]       #ここで移動するようcostを更新し
                heappush(q,[cost+needtime[u][j],j,nextcoin])    #移動あとの状態をqにpush
for i in range(1,N):
    print(costtree[i][0])                                       #最小コストは下に流れるようになっているので、それぞれの頂点でcoin=0の時のcostが答え

Submission status: Accepted

Solution code:
from collections import defaultdict
import heapq

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

max_money=max([a for _,_,a,_ in Edges])*N

Graph=defaultdict(lambda :[])

#nodeと状態は tupleで管理する。(node,money)
#Graph[cur_state]=[ (cost,next_state),...]


for u,v,a,b in Edges:
    u-=1;v-=1
    for cur_money in range(max_money+1):
        if cur_money-a<0:#お金が足りなくて移動できない
            continue
        from_state_u=(u,cur_money)
        to_state_v=(v,cur_money-a)
        Graph[from_state_u].append((b,to_state_v))

        from_state_v=(v,cur_money)
        to_state_u=(u,cur_money-a)
        Graph[from_state_v].append((b,to_state_u))

for n,[c,d] in enumerate(Exchanges):
    for cur_money in range(max_money+1):
        after_money=min(max_money,cur_money+c)#両替後のお金(money_max以上は同じにする)
        from_state=(n,cur_money)
        to_state=(n,after_money)
        Graph[from_state].append((d,to_state))



# Dijksttra する
#startの状態(Sがmax_moneyより大きいならmax_moneyにする)
start=(0,min(max_money,S))

Q=[(0,start)]

dist=defaultdict(lambda :float('inf'))
dist[start]=0

while Q:
    q = heapq.heappop(Q)
    cur_time,cur_state=q

    if dist[cur_state]<cur_time:
        continue
    for cost,next_state in Graph[cur_state]:
        next_time = cost+cur_time

        if dist[next_state]>next_time:
            dist[next_state]=next_time
            heapq.heappush(Q,(next_time,next_state))

for dest in range(1,N):
    ans=float("inf")
    #goal次の所持金は関係ないので、ある頂点のあらゆる所持金に対してminをとる
    for a in range(max_money+1):
        state=(dest,a)
        ans=min(ans,dist[state])
    print(ans)