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
def dijkstra_heap(N,S,Smax,edge):
  d = [float('inf')]*(10**4*N) #始点0から各頂点への最短距離
  used = [False]*(10**4*N)
  d[S] = 0
  used[S] = True
  edgelist = []
  #edgelist : [(0,S)からの暫定(未確定)最短時間,頂点,銀貨の枚数]のリスト
  #edge[s] : sから出る枝の[重み,頂点,銀貨の枚数]のリスト
  for w,a in edge[0]:
    v,sil = a//10**4,a%10**4
    if v==0 and S+sil<=Smax:
      heapq.heappush(edgelist,[w,a+S]) #sの隣の点は枝の重さがそのまま暫定最短距離となる
    elif v>0 and S-sil>=0:
      heapq.heappush(edgelist,[w,v*10**4+(S-sil)]) #sの隣の点は枝の重さがそのまま暫定最短距離となる
  while len(edgelist):
    #まだ使われてない頂点の中から最小の距離のものを探す→確定させる
    min_w,min_a = heapq.heappop(edgelist)
    min_v,min_sil = min_a//10**4,min_a%10**4
    #min_w,min_v,min_sil : [0からの(確定)最短距離,頂点,銀貨の枚数]
    if used[min_a]:
      continue
    d[min_a] = min_w
    used[min_a] = True
    for w,a in edge[min_v]:
      v,sil = a//10**4,a%10**4
      if v==min_v and min_sil+sil<=Smax and not used[a+min_sil]:
        heapq.heappush(edgelist,[min_w+w,a+min_sil])
      elif v!=min_v and min_sil-sil>=0 and not used[v*10**4+(min_sil-sil)]:
        heapq.heappush(edgelist,[min_w+w,v*10**4+(min_sil-sil)])
  return d

def solve():
  N, M, S = map(int, input().split())
  edge = [[] for _ in range(N)]
  amax = 0
  for i in range(M):
    u,v,a,b = map(int, input().split())
    amax = max(amax,a)
    edge[u-1].append([b,(v-1)*10**4+a])
    edge[v-1].append([b,(u-1)*10**4+a])
  Smax = (N-1)*amax
  S = min(S,Smax)
  for i in range(N):
    c,d = map(int, input().split())
    edge[i].append([d,i*10**4+c])
  D = dijkstra_heap(N,S,Smax,edge)
  ans = [0]*N
  for i in range(1,N):
    ans[i] = min(D[i*10**4:(i+1)*10**4])
  return ans[1:]
print(*solve(),sep='\n')

Submission status: Accepted

Solution code:
import heapq
def dijkstra_heap(N,S,Smax,edge):
  d = [float('inf')]*(10**4*N) #始点0から各頂点への最短距離
  used = [False]*(10**4*N)
  d[S] = 0
  used[S] = True
  edgelist = []
  #edgelist : [(0,S)からの暫定(未確定)最短時間,頂点,銀貨の枚数]のリスト
  #edge[s] : sから出る枝の[重み,頂点,銀貨の枚数]のリスト
  for w,a in edge[0]:
    v,sil = a//10**4,a%10**4
    if v==0 and S+sil<=Smax:
      heapq.heappush(edgelist,[w,a+S]) #sの隣の点は枝の重さがそのまま暫定最短距離となる
    elif v>0 and S-sil>=0:
      heapq.heappush(edgelist,[w,v*10**4+(S-sil)]) #sの隣の点は枝の重さがそのまま暫定最短距離となる
  while len(edgelist):
    #まだ使われてない頂点の中から最小の距離のものを探す→確定させる
    min_w,min_a = heapq.heappop(edgelist)
    min_v,min_sil = min_a//10**4,min_a%10**4
    #min_w,min_v,min_sil : [0からの(確定)最短距離,頂点,銀貨の枚数]
    if used[min_a]:
      continue
    d[min_a] = min_w
    used[min_a] = True
    for w,a in edge[min_v]:
      v,sil = a//10**4,a%10**4
      if v==min_v and min_sil+sil<=Smax and not used[a+min_sil]:
        heapq.heappush(edgelist,[min_w+w,a+min_sil])
      elif v!=min_v and min_sil-sil>=0 and not used[v*10**4+(min_sil-sil)]:
        heapq.heappush(edgelist,[min_w+w,v*10**4+(min_sil-sil)])
  return d

def solve():
  N, M, S = map(int, input().split())
  edge = [[] for _ in range(N)]
  amax = 0
  for i in range(M):
    u,v,a,b = map(int, input().split())
    amax = max(amax,a)
    edge[u-1].append([b,(v-1)*10**4+a])
    edge[v-1].append([b,(u-1)*10**4+a])
  Smax = (N-1)*amax
  S = min(S,Smax)
  for i in range(N):
    c,d = map(int, input().split())
    edge[i].append([d,i*10**4+c])
  D = dijkstra_heap(N,S,Smax,edge)
  ans = [0]*N
  for i in range(1,N):
    ans[i] = min(D[i*10**4:(i+1)*10**4])
  return ans[1:]
print(*solve(),sep='\n')

Submission status: Accepted

Solution code:
import heapq

city_num, road_num, init_silver = map(int, input().split())
MAX_COST = 2500
init_silver  = min(MAX_COST, init_silver)

G = [[] for _ in range(city_num)]
for _ in range(road_num):
    A, B, cost, time_cost = map(int, input().split())
    A, B = A-1, B-1
    G[B].append([A, cost, time_cost])
    G[A].append([B, cost, time_cost])

for n in range(city_num):
    cost, time_cost = map(int, input().split())
    G[n].append([n, -cost, time_cost])

dp = [[float("inf")] * (MAX_COST+1) for _ in range(city_num)]
dp[0][init_silver] = 0
hq = [(0, 0, init_silver)]
while hq:
    time, node, silver = heapq.heappop(hq)
    for to, silver_cost, time_cost in G[node]:
        remain = min(silver - silver_cost, MAX_COST)
        if remain < 0:
            continue
        dp_next_value = time + time_cost
        if dp[to][remain] <= dp_next_value:
            continue
        dp[to][remain] = dp_next_value
        heapq.heappush(hq, (dp_next_value, to, remain))
print(*[min(d) for d in dp[1:]], sep="\n")

Submission status: Accepted

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

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

change_rate, change_cost = [], []
for i in range(N):
    rate, cost = map(int, input().split())
    G[i].append([i, -rate, cost])  # これを追加！
    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][init_silver] = 0

# 優先度付きキュー: (time, node, silver)
hq = [(0, 0, init_silver)]
while hq:
    time, node, silver = heapq.heappop(hq)

    for to, silver_cost, time_cost in G[node]:
        remain_silver = min(silver - silver_cost, MAX_COST)
        if remain_silver < 0:
            continue

        dp_next_value = time + time_cost
        if dp[to][remain_silver] <= dp_next_value:
            continue

        dp[to][remain_silver] = dp_next_value
        heapq.heappush(hq, (dp_next_value, to, remain_silver))

print(*[min(d) for d in dp[1:]], sep="\n")

Submission status: Accepted

Solution code:
import sys
from heapq import *
import numpy as np
import numba
from numba import njit
i8 = numba.int64

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@njit((i8, i8, i8[:, :], i8[:]), cache=True)
def main(N, S, G, CD):
    ind = np.searchsorted(G[:, 0], np.arange(N + 1), 'right')
    U = 2600
    C, D = CD[::2], CD[1::2]
    C = np.minimum(C, U)
    S = np.minimum(S, U)
    INF = 10**18
    dist = np.full((N + 1, U + 1), INF, np.int64)
    dist[1, S] = 0
    q = [(0, 1, S)]
    while q:
        d, v, coin = heappop(q)
        if dist[v, coin] < d:
            continue
        for i in range(ind[v - 1], ind[v]):
            w, a, b = G[i, 1:]
            if coin < a:
                continue
            if dist[w, coin - a] <= d + b:
                continue
            dist[w, coin - a] = d + b
            heappush(q, (d + b, w, coin - a))
        c = min(U, coin + C[v - 1])
        if dist[v, c] <= d + D[v - 1]:
            continue
        dist[v, c] = d + D[v - 1]
        heappush(q, (d + D[v - 1], v, c))
    return dist

N, M, S = map(int, readline().split())
nums = np.array(read().split(), np.int64)
UVAB = nums[:4 * M]
CD = nums[4 * M:]

U, V, A, B = UVAB.reshape(-1, 4).T

G = np.empty((M + M, 4), np.int64)
G[:, 0] = np.concatenate((U, V))
G[:, 1] = np.concatenate((V, U))
G[:, 2] = np.concatenate((A, A))
G[:, 3] = np.concatenate((B, B))
G = G[G[:, 0].argsort()]

ans = main(N, S, G, CD)[2:].min(axis=1)
print('\n'.join(map(str, ans.tolist())))

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,m,s = list(map(int, input().split()))
cd = [None]*n
from collections import defaultdict
ns = defaultdict(set)
nns = defaultdict(set)
uvab = [None]*m
for i in range(m):
    u,v,a,b = list(map(int, input().split()))
    u -= 1
    v -= 1
    uvab[i] = (u,v,a,b)
    ns[u].add((a,b,v))
    ns[v].add((a,b,u))
for i in range(n):
    cd[i] = list(map(int, input().split()))

ms = max(item[2] for item in uvab)*(n-1)
for u in range(n):
    for ss in range(ms+1):
        for a,b,v in ns[u]:
            if ss>=a:
                nns[u,ss].add((b, (v,ss-a)))
        c,d = cd[u]
        if ss+c<=ms:
            nns[u,ss].add((d, (u,ss+c)))
ns = nns
def dijkstra(start):
    import heapq
    vals = {}
    h = [(0, start)] # (距離, ノード番号)
    vals[start] = 0
    while h:
        val, u = heapq.heappop(h)
        for d, v in ns[u]:
            if v not in vals or vals[v]>val+d:
                vals[v] = val+d
                heapq.heappush(h, (vals[v], v))
    return vals
s = min(s, ms)
vals = dijkstra((0,s))
ans = [None]*(n-1)
for u in range(1,n):
    ans[u-1] = min(vals[u,s] for s in range(ms+1))
write("\n".join(map(str, ans)))

Submission status: Accepted

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

ways=[[] for _ in range(N)]
CD=[[0]*2 for _ in range(N)]

class Way:
  def __init__(self,t,f,ti):
    self.to=t
    self.fare=f
    self.time=ti 

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

for i in range(N):
  C,D=map(int,input().split())
  CD[i][0]=C
  CD[i][1]=D
  
#dp[i][j]:駅iにおいて銀貨をj枚所持するための最短時間
dp=[[float("inf")]*(50*N+1) for _ in range(N)]
S=min(S,50*N)
dp[0][S]=0
import heapq

#data型は(時間、駅、お金)
#q=heapq.heapify([(0,0,S)])
#q=heapq.heapify([])
q=[]
heapq.heappush(q,(0,0,S))
#print(q)
def Push(time,station,money):
  #print("called")
  global q,dp
  if money<0:
    return
  money=min(money,50*N)
  if dp[station][money] <= time:
    return
  dp[station][money] = time
  heapq.heappush(q,(time,station,money))

while q:
  #print("called!")
  dat = heapq.heappop(q)
  time,station,money=dat[0],dat[1],dat[2]
  
  if dp[station][money]!=time:
    continue
  #まず、両替。
  Push(time+CD[station][1],station,money+CD[station][0])
  #次に、各道について移動
  for w in ways[station]:
    Push(time+w.time,w.to,money-w.fare)

for i in range(1,N):
  ans=float("inf")
  for j in range(50*N+1):
    ans=min(ans,dp[i][j])
  print(ans)

Submission status: Accepted

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

N,M,S = list(map(int, input().rstrip().split()))
UVAB_list = [list(map(int, input().rstrip().split())) for i in range(M)]
CD_list = [list(map(int, input().rstrip().split())) for i in range(N)]
#-----

max_money = 2500
S = min(max_money, S)

# graph[current city][i] = [ (next city, coin, time) ]
graph = [None] + [ [] for _ in range(N) ]

# change[current city][i] = [ (coin, time) ]
change = [None] + [ () for _ in range(N) ]

# dp[city][money] = total time
dp = [None] + [ [float("inf")]*(max_money + 1) for _ in range(N) ]
dp[1][S] = 0


for u,v,a,b in UVAB_list:
    graph[u].append( (v,a,b) )
    graph[v].append( (u,a,b) )

for i,(c,d) in enumerate(CD_list):
    change[i+1] = (c,d)

# heap[i] = (current time, current city, current money)
heap = [ (0, 1, S) ]


while heap:
    cur_time, cur_city, cur_mone = heapq.heappop(heap)
    
    # change money at current city ---
    changed_money = cur_mone + change[cur_city][0]
    changed_time = cur_time + change[cur_city][1]
    
    if (changed_money <= max_money) and (changed_time < dp[cur_city][changed_money] ):
        dp[cur_city][changed_money] = changed_time
        heapq.heappush(heap, ( changed_time, cur_city, changed_money) )
    
    # move to next city ---
    for next_city, cost_coin, cost_time in graph[cur_city]:
        next_time = cur_time + cost_time
        next_money = min( max_money , cur_mone - cost_coin )
        
        if (cur_mone >= cost_coin) and ( next_time < dp[next_city][next_money] ):
            dp[next_city][next_money] = next_time
            heapq.heappush(heap, ( next_time, next_city, next_money) )


for row in dp[2:]:
    print( min(row) )

Submission status: Accepted

Solution code:
def examA():
    S, W = LI()
    if S<=W:
        print("unsafe")
    else:
        print("safe")
    return

def examB():
    A, B, C, D = LI()
    while(True):
        C -= B
        if C<=0:
            print("Yes")
            break
        A -= D
        if A<=0:
            print("No")
            break
    return

def examC():
    N = I()
    S = [SI()for _ in range(N)]
    Set = set(S)
    ans = len(Set)
    print(ans)
    return

def examD():
    S = SI()
    N = len(S)
    D = [0]*(N+1)
    for i in range(N):
        D[i+1] = (D[i]+int(S[N-1-i])*pow(10,i,2019))%2019
    #print(D)
    ans = 0
    C = Counter(D)
    #print(C)
    for c in C.values():
        ans += (c-1)*c//2
    print(ans)
    return

def examE():
    def dijkstra(n, edges, start, C, silver):
        maxC = (2*n-1)*50
        dist = [[inf]*(maxC+1) for _ in range(n)]
        dist[start][silver] = 0
        Q = [(0, (start, silver))]  # (dist,vertex)
        while (Q):
            d, (v, c) = heapq.heappop(Q)
            if dist[v][c]<d:continue
            loop = (maxC-c)//C[v][0] + 1
            for i in range(loop):
                nextc = c+i*C[v][0]
                nextd = d+i*C[v][1]
                if nextc>maxC:
                    nextc=maxC
                if dist[v][nextc] < nextd: continue  # 候補として挙がったd,vだが、他に短いのがある
                for u, cost, coin in edges[v]:
                    k = nextc-coin
                    if k<0:
                        continue
                    if dist[u][k] > nextd + cost:
                        dist[u][k] = nextd + cost
                        heapq.heappush(Q, (dist[u][nextc-coin], (u, k)))
        return dist
    N, M, S = LI()
    V = [[]for _ in range(N)]
    for _ in range(M):
        s, t, a, b = LI()
        s -= 1; t -= 1
        V[s].append((t,b,a))
        V[t].append((s,b,a))
    C = [LI()for _ in range(N)]
    D = dijkstra(N,V,0,C,min(S,(2*N-1)*50))
    for i in range(1,N):
        print(min(D[i]))
    return

def examE2():
    def dijkstra(edges, start=0):
        dist = [inf] * len(edges)
        dist[start] = 0
        Q = [(0, start)]  # (dist,vertex)
        while (Q):
            d, v = heapq.heappop(Q)
            if dist[v] < d: continue  # 候補として挙がったd,vだが、他に短いのがある
            for u, cost in edges[v]:
                if dist[u] > dist[v] + cost:
                    dist[u] = dist[v] + cost
                    heapq.heappush(Q, (dist[u], u))
        return dist
    maxS = 2501
    N, M, S = LI()
    V = [[]for _ in range(N*(maxS+1))]

    for _ in range(M):
        u, v, a, b = LI()
        u -= 1; v -= 1
        for i in range(a, maxS):
            V[u * maxS + i].append([v * maxS + i - a, b])
            V[v * maxS + i].append([u * maxS + i - a, b])
    for i in range(N):
        c, d = LI()
        for j in range(maxS-1):
            V[i * maxS + j].append([i * maxS + min(j + c, maxS-1), d])
    #print(V)
    D = dijkstra(V,min(maxS-1,S))
    #for i in range(N):
    #    print(D[i*maxS:(i+1)*maxS])

    for i in range(1,N):
        print(min(D[i*maxS:(i+1)*maxS]))
    return

def examF():
    N = I()
    S = LI()
    T = LI()
    U = LI()
    V = LI()

    ans = 0
    print(ans)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(readline())
def LI(): return list(map(int,readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examE2()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Submission status: Accepted

Solution code:
from heapq import heapify,heappush,heappop

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

# !!グラフの作成!! #
tmp = [list(map(int, input().split())) for _ in range(M)]

U = [0 for _ in range(M)]
V = [0 for _ in range(M)]
A = [0 for _ in range(M)]
B = [0 for _ in range(M)]

for i in range(M):
  U[i] = tmp[i][0] -1
  V[i] = tmp[i][1] -1
  A[i] = tmp[i][2]
  B[i] = tmp[i][3]
A_m = max(A)
S = min(N*A_m, S)
#print(A_m)

I = [[] for _ in range(N * (N*A_m+1))] 
# 隣接リスト(頂点iで銀貨j枚持ちのとき、i*N*(A_m+1)+jとおく)
for i in range(M):
  for j in range(A[i], N*A_m+1):
    I[U[i]*(N*A_m+1)+j].append((V[i]*(N*A_m+1)+j-A[i],B[i]))
    I[V[i]*(N*A_m+1)+j].append((U[i]*(N*A_m+1)+j-A[i],B[i]))

for i in range(N):
  C, D = map(int, input().split())
  for j in range(N*A_m+1):
    I[i*(N*A_m+1)+j].append((i*(N*A_m+1)+min(C+j,N*A_m),D))
#print(I)

def dijkstra(I):# I:隣接リスト(頂点、コスト、そのほか制約) 
  N = len(I)
  task = [] 
  visited = [0 for _ in range(N)]
  min_cost = [0 for _ in range(N)]
  cost = [10**20 for _ in range(N)]
  prev_points = [0 for _ in range(N)]
  heappush(task, (0, S, -1))
  # !!比較値がスカラーでないときは、一番左の0を適宜変更する!! #
  # !!最初の点番号が0でないときは、真ん中の0を変更する!! #
  
  flag = 0
  while task:
    while task:
      c, p, prev = heappop(task)    
      if visited[p] == 0:
        break  
      if len(task) == 0:
        flag = 1
    if flag == 1:
      break
    #print(task)
    visited[p] = 1
    min_cost[p] = c
    prev_points[p] = prev
  
    for j, c_ad in I[p]: #制約が入るときはここに追加
      if visited[j] == 1: continue
      #print(p//(N*A_m+1),p%(N*A_m+1),j//(N*A_m+1),j%(N*A_m+1),c_ad)
      cost_next = next_cost(I, p, j, c, c_ad)
      if cost[j] > cost_next:
        cost[j] = cost_next
        heappush(task, (cost_next, j, p))

  return (min_cost, prev_points)

def next_cost(I, p, j, c, c_ad): # !!現在の点pから次の点jへのコストを計算する方法を記入!! #  
#c:点pにつくまでに払ったコスト、c_ad:次回追加されるコスト#
  return c + c_ad

min_cost, prev_points = dijkstra(I)

for i in range(1, N):
  print(min(min_cost[i*(N*A_m+1):(i+1)*(N*A_m+1)]))

Submission status: Accepted

Solution code:
n,m,s = map(int,input().split())
import collections
g = [[] for _ in range(n+1)]
dic = {}
for _ in range(m):
    u,v,a,b = map(int,input().split())
    g[u].append(v)
    g[v].append(u)
    dic[(u,v)]=(a,b)
    dic[(v,u)]=(a,b)
arr = [[0,0]]+[list(map(int,input().split())) for _ in range(n)]
cost =[[float('inf')]*2501 for _ in range(n+1)]
for i in range(min(2500,s)+1):
    cost[1][i] = 0
q=collections.deque()
q.append(1)
while q:
    v = q.popleft()
    c,d = arr[v]
    for i in range(c,2501):
        cost[v][i] = min(cost[v][i],cost[v][i-c]+d)
    for u in g[v]:
        a,b = dic[(v,u)]
        flag = False
        for i in range(a,2501):
            if cost[u][i-a]>cost[v][i]+b:
                cost[u][i-a]=cost[v][i]+b
                flag = True
        if flag==True:
            q.append(u)
for i in range(2,n+1):
    print(min(cost[i]))

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    import heapq
    from collections import defaultdict

    n, m, s = map(int, readline().split())
    s_max = 0

    edge = defaultdict(list)
    for _ in range(m):
        u, v, a, b = map(int, readline().split())
        u, v = u - 1, v - 1
        edge[u].append((v, a, b))
        edge[v].append((u, a, b))
        s_max += a

    exchange = [[0] * 2 for _ in range(n)]
    for i in range(n):
        c, d = map(int, readline().split())
        exchange[i][0], exchange[i][1] = c, d

    s_start = min(s, s_max)

    hq = []
    heapq.heappush(hq, (0, s_start, 0))
    dist = [[INF] * (s_max + 1) for _ in range(n)]

    while hq:
        cost, s_cur, u = heapq.heappop(hq)

        s_rate, s_time = exchange[u][0], exchange[u][1]
        s_next = s_cur + s_rate
        s_next = min(s_next, s_max)
        if cost + s_time < dist[u][s_next]:
            heapq.heappush(hq, (cost + s_time, s_next, u))
            dist[u][s_next] = cost + s_time

        for v, a, b in edge[u]:
            if s_cur >= a and cost + b < dist[v][s_cur - a]:
                heapq.heappush(hq, (cost + b, s_cur - a, v))
                dist[v][s_cur - a] = cost + b

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
import heapq


class Dijkstra:
    """
    dijkstraの最短経路問題を解く
    input:
        S: start node
        adj: adj[a]=[(b,dist)]//なんとなく
    """

    def __init__(self, start, num_node, adj):
        """
        adj: adj[a]=[(b,dist)]
        num_node: num of nodes
        dist: dist from start_node
        prev: 最短経路において、一つ前のノードを記憶。経路復元に使う?
        """
        self.start_node = start
        self.adj= adj
        self.num_node = num_node
        self.dist = [float('inf')]*num_node
        self.prev = defaultdict(lambda: None)

        # dist form S to S = 0
        self.dist[start] = 0

    def calc_dist(self):
        """
        最短経路 distを計算する
        Q: content (dist_from_start,node)
        Qはheapqとして使う。dist_from_startの小さい順になる
        Qには、dist*N+nodeを入れることで高速化
        """
        Q = []
        heapq.heappush(Q, self.start_node)
        while Q:
            dist_to_node, node = divmod(heapq.heappop(Q),self.num_node)
            # 現在の値よりも大きくて、更新にならない場合
            if self.dist[node] < dist_to_node:
                continue

            # 次のホップを計算する
            for nex,weight in self.adj[node]:
                cand = dist_to_node + weight

                if self.dist[nex] > cand:  # update
                    self.dist[nex] = cand
                    self.prev[nex] = node
                    heapq.heappush(Q, cand*self.num_node+nex)

    def get_dist(self, d):
        """
            startからdまでの距離を返す
            これの前にcalc()を実行しておく
            たどり着けない場合は、float('inf')がかえる
        """
        return self.dist[d]
    def get_path(self,dst):
        """
        startからdstまでのpathをlistでreturn
        valifyしてないので怪しい
        """
        cur=dst
        ret=[cur]
        while cur!=self.start_node:
            cur=self.prev[cur]
            ret.append(cur)
        return list(reversed(ret))
N,M,S = map(int,input().split())
edges=[list(map(int,input().split())) for _ in range(M)]
C=[list(map(int,input().split())) for _ in range(N)]

max_c=2501


def toId(node,cur):
    return node*max_c+cur

def revId(id):
    return id//max_c,id%max_c


states=N*max_c
adj=[[] for _ in range(states)]


for a,b,c,d in edges:
    a-=1
    b-=1
    for cc in range(max_c-c):
        adj[toId(a,cc+c)].append((toId(b,cc),d))
        adj[toId(b,cc+c)].append((toId(a,cc),d))

for i,(c,d) in enumerate(C):
    for cc in range(max_c-c):
        adj[toId(i,cc)].append(((toId(i,cc+c),d)))


#for i,a in enumerate(adj):
#    print("from {}".format(revId(i)))
#    for v,d in a:
#        print("\t: {} cost:{}".format(revId(v),d))
    
S=min(S,max_c-1)
start=toId(0,S)

D=Dijkstra(start,states,adj)
D.calc_dist()
for i in range(1,N):
    ans=float("inf")
    path=None
    for cc in range(max_c):
        if ans>D.get_dist(toId(i,cc)):
            ans=D.get_dist(toId(i,cc))
            path=D.get_path(toId(i,cc))
    print(ans)

Submission status: Accepted

Solution code:
import heapq
import sys
from collections import defaultdict
readline = sys.stdin.readline

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

ls = [[] for _ in range(n)]
ms = []
for _ in range(m):
    u, v, a, b = map(int, input().split())
    ls[u - 1].append((v - 1, a, b))
    ls[v - 1].append((u - 1, a, b))
for _ in range(n):
    c, d = map(int, input().split())
    ms.append((c, d))

visited = defaultdict(int)
ans = [-1] * n
count = 0

q = [(0, 0, s)]
while q:
    t, i, s = heapq.heappop(q)
    if visited[(i, s)]:
        continue
    visited[(i, s)] = 1
    if ans[i] == -1:
        ans[i] = t
        count += 1
        if count == n:
            break

    if s <= 2500:
        tc, td = ms[i]
        heapq.heappush(q, (t + td, i, s + tc))
    for ni, a, b in ls[i]:
        if not visited[(ni, s - a)] and s >= a:
            heapq.heappush(q, (t + b, ni, s - a))

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

Submission status: Accepted

Solution code:
from heapq import heappop, heappush


def main():
    N, M, S = map(int, input().split())
    adj = [{} for _ in range(N)]
    amax = 0
    for _ in range(M):
        u, v, a, b = map(int, input().split())
        adj[u-1][v-1] = (a, b)
        adj[v-1][u-1] = (a, b)
        amax = max(amax, a)
    C = [0] * N
    D = [0] * N
    for i in range(N):
        C[i], D[i] = map(int, input().split())
    MAX = amax * N
    dp = [[float("inf")] * (MAX+1) for _ in range(N)]
    q = [[0, min(S, MAX), 0, -1]]
    ans = [None] * N
    remain = N
    while len(q) and remain:
        time, coin, cur, prev = heappop(q)
        if dp[cur][coin] <= time:
            continue
        if ans[cur] is None:
            ans[cur] = time
            remain -= 1
        dp[cur][coin] = time
        if coin < MAX:
            heappush(q, [time + D[cur], min(coin + C[cur], MAX), cur, cur])
        for nxt in adj[cur]:
            dcost, dtime = adj[cur][nxt]
            if nxt != prev and dcost <= coin:
                heappush(q, [time + dtime, coin - dcost, nxt, cur])
    for i in range(1, N):
        print(ans[i])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, M, S = mapint()
S = min(S, N*50)
query = [[[] for _ in range(N*50+1)] for _ in range(N)]
for _ in range(M):
    u, v, a, b = mapint()
    for coin in range(a, N*50+1):
        query[u-1][coin].append((v-1, a, b))
        query[v-1][coin].append((u-1, a, b))
for i in range(N):
    c, d = mapint()
    for coin in range(N*50+1):
        query[i][coin].append((i, -c, d))

inf = 10**18
dp = [[inf]*(N*50+1) for _ in range(N)]
dp[0][0] = 0

import heapq
queue = [(0, 0, S)]
checked = [0]*N
cnt = 0

while queue:
    t, now, coin = heapq.heappop(queue)
    if cnt==N:
        break
    if not checked[now]:
        checked[now] = 1
        cnt += 1
    qlis = query[now][coin]
    for nx, a, b in qlis:
        if 0<=coin-a:
            coin = min(coin, N*50+a)
            if t+b<dp[nx][coin-a]:
                dp[nx][coin-a] = t+b
                heapq.heappush(queue, (t+b, nx, coin-a))

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

Submission status: Accepted

Solution code:
import sys
from heapq import *
I=sys.stdin.readlines()
N,M,S=map(int,I[0].split())
S=min(S,2499)
G=[[] for i in range(2500*N)]
u,v,a,b=0,0,0,0
for i in range(M):
  u,v,a,b=map(int,I[i+1].split())
  u,v=u-1,v-1
  for j in range(a,2500):
    G[u+j*N].append((v+(j-a)*N,b))
    G[v+j*N].append((u+(j-a)*N,b))
for i in range(N):
  a,b=map(int,I[M+i+1].split())
  for j in range(a,2500):
    G[i+(j-a)*N].append((i+j*N,b))
D=[0]*(2500*N)
INF=10**15
def ijk(s):
  global D,INF,G
  for i in range(len(G)):
    D[i]=INF
  D[s]=0
  Q=[]
  heapify(Q)
  heappush(Q,(0,s))
  p,v,e=0,0,0
  while len(Q):
    p=heappop(Q)
    v=p[1]
    if D[v]<p[0]:
      continue
    for i in range(len(G[v])):
      e=G[v][i]
      if D[e[0]]>D[v]+e[1]:
        D[e[0]]=D[v]+e[1]
        heappush(Q,(D[e[0]],e[0]))

ijk(S*N)
for i in range(1,N):
  print(min(D[i::N]))