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 collections import defaultdict
import heapq
N,M,S = map(int,input().split())
E=[list(map(int,input().split())) for _ in range(M)]

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

A_max=max([a for _,_,a,_ in E])*N

D=defaultdict(lambda :[])

for u,v,a,b in E:
    u-=1;v-=1
    for from_a in range(A_max+1):
        if from_a-a<0:
            continue
        from_state_u=(u,from_a)
        to_state_v=(v,from_a-a)
        D[from_state_u].append((b,to_state_v))

        from_state_v=(v,from_a)
        to_state_u=(u,from_a-a)
        D[from_state_v].append((b,to_state_u))

for n,[c,d] in enumerate(C):
    for a in range(A_max+1):
        a_after=min(A_max,a+c)
        from_state=(n,a)
        to_state=(n,a_after)
        D[from_state].append((d,to_state))


start=(0,min(A_max,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 D[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")
    for a in range(A_max+1):
        state=(dest,a)
        ans=min(ans,Dist[state])
    print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
import heapq
N,M,S = map(int,input().split())
E=[list(map(int,input().split())) for _ in range(M)]

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

A_max=max([a for _,_,a,_ in E])*N

D=defaultdict(lambda :[])

for u,v,a,b in E:
    u-=1;v-=1
    for from_a in range(A_max+1):
        if from_a-a<0:
            continue
        from_state_u=(u,from_a)
        to_state_v=(v,from_a-a)
        D[from_state_u].append((b,to_state_v))

        from_state_v=(v,from_a)
        to_state_u=(u,from_a-a)
        D[from_state_v].append((b,to_state_u))

for n,[c,d] in enumerate(C):
    for a in range(A_max+1):
        a_after=min(A_max,a+c)
        from_state=(n,a)
        to_state=(n,a_after)
        D[from_state].append((d,to_state))


start=(0,min(A_max,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 D[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")
    for a in range(A_max+1):
        state=(dest,a)
        ans=min(ans,Dist[state])
    print(ans)

Submission status: Accepted

Solution code:
#拡張ダイクストラ 
#weight,point
N,M,S=map(int,input().split())
graph={(i,j):[] for i in range(1,51) for j in range(2501)}
for _ in range(M):
    u,v,a,b=map(int,input().split())
    for i in range(a,2501):
        graph[(u,i)].append((b,(v,i-a)))
        graph[(v,i)].append((b,(u,i-a)))
for i in range(N):
    c,d=map(int,input().split())
    for j in range(2501):
        graph[(i+1,j)].append((d,(i+1,min(2500,j+c))))

dist={(i,j):float("inf")  for i in range(1,51) for j in range(2501)}

dist[(1,min(2500,S))]=0
pq=[]
import heapq
heapq.heapify(pq)
heapq.heappush(pq,(0,(1,min(2500,S))))
while pq:
    mini_dis,node=heapq.heappop(pq)
    if dist[node]<mini_dis: continue
    for w,point in graph[node]:
        if dist[point]<w:continue
        newlen=dist[node]+w
        if newlen<dist[point]:
            heapq.heappush(pq,(newlen,point))
            dist[point]=newlen
for i in range(2,N+1):
    ans=10**20
    for j in range(2501):
        ans=min(ans,dist[(i,j)])
    print(ans)

Submission status: Accepted

Solution code:
#拡張ダイクストラ 
#weight,point
N,M,S=map(int,input().split())
graph={(i,j):[] for i in range(1,51) for j in range(2501)}
for _ in range(M):
    u,v,a,b=map(int,input().split())
    for i in range(a,2501):
        graph[(u,i)].append((b,(v,i-a)))
        graph[(v,i)].append((b,(u,i-a)))
for i in range(N):
    c,d=map(int,input().split())
    for j in range(2501):
        graph[(i+1,j)].append((d,(i+1,min(2500,j+c))))

dist={(i,j):float("inf")  for i in range(1,51) for j in range(2501)}

dist[(1,min(2500,S))]=0
pq=[]
import heapq
heapq.heapify(pq)
heapq.heappush(pq,(0,(1,min(2500,S))))
while pq:
    mini_dis,node=heapq.heappop(pq)
    if dist[node]<mini_dis: continue
    for w,point in graph[node]:
        if dist[point]<w:continue
        newlen=dist[node]+w
        if newlen<dist[point]:
            heapq.heappush(pq,(newlen,point))
            dist[point]=newlen
for i in range(2,N+1):
    ans=10**20
    for j in range(2501):
        ans=min(ans,dist[(i,j)])
    print(ans)

Submission status: Accepted

Solution code:
import heapq


n,m,s=map(int,input().split())
#隣接行列[金額,時間]
graph=[[] for i in range(n)]
#銀貨リスト
A=[]
for i in range(m):
    u,v,a,b=map(int,input().split())
    A.append(a)
    graph[u-1].append((v-1,a,b))
    graph[v-1].append((u-1,a,b))

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

A_max=max(A)
max_money=(n-1)*A_max

s=min(s,max_money)

width=max_money+1
N=n*width
#新しい隣接リスト;(時間,行き先)
system=[[] for i in range(N)]
for index in range(N):
    #頂点
    city=index//width
    #持ち金
    money=index%width

    #頂点の移動
    for next in graph[city]:
        #移動可能か
        if money>=next[1]:
            next_index=next[0]*width+(money-next[1])
            system[index].append((next[2],next_index))

    #持ち金の移動(最大n*A_max回かかる)→1回分でよい
    if money+change[city][0]<max_money:
        system[index].append((change[city][1],index+change[city][0]))
    else:
        system[index].append((change[city][1],max_money))


def dijkstra_heap(s,n,edge):
    #頂点数のオーダーでscaleは変更せよ
    scale=10**6

    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*scale+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(scale)]:
            continue
        v = minedge%(scale)
        d[v] = minedge//(scale)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*scale+e[1])
    return d


D=dijkstra_heap(s,N,system)
for i in range(1,n):
    ans=float('inf')
    for index in range(i*width,(i+1)*width):
        ans=min(ans,D[index])

    print(ans)

Submission status: Accepted

Solution code:
import heapq
import sys
input = sys.stdin.readline
 
INF = 10 ** 18
 
class Edge():
    def __init__(self, end, cost, time):
        self.end = end
        self.cost = cost
        self.time = time
 
dp = []
h = []
 
def push(t, v, x):
    if x < 0:
        return
    if dp[v][x] <= t:
        return
    dp[v][x] = t
    heapq.heappush(h, (t, v, x))
 
def dijkstra(n, G, cd, start, s, max_s):
    global dp
    dp = [[INF for j in range(max_s+1)] for i in range(n)] 
    push(0, start, s)
 
    while h:
        # 使っていない頂点のうち、現時点で最も到達短時間が短いものを選びvとする
        t, v, x = heapq.heappop(h)
        if dp[v][x] < t:
            continue
        # 両替
        if x < max_s:
            push(t+cd[v][1], v, min(x+cd[v][0], max_s))
        # vから到達可能な頂点について、到達時間が短くなれば更新
        for e in G[v]:
            push(t+e.time, e.end, x-e.cost)
 
 
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)]
 
es = [[] for i in range(n)]
max_s = 50 * (n-1)
 
for u, v, a, b in uvab:
    es[u-1].append(Edge(v-1,a,b))
    es[v-1].append(Edge(u-1,a,b))
 
dijkstra(n, es, cd, 0, min(max_s,s), max_s)
 
for i in range(1, n):
    print(min(dp[i]))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys, heapq, math
sys.setrecursionlimit(300000)


def solve(N: int, M: int, S: int, U: "List[int]", V: "List[int]", A: "List[int]", B: "List[int]", C: "List[int]", D: "List[int]"):
    conns = [[] for _ in range(N)]
    for i in range(M):
        conns[U[i] - 1].append((V[i] - 1, A[i], B[i])) # cost, duration
        conns[V[i] - 1].append((U[i] - 1, A[i], B[i])) # cost, duration

    INF = float('inf')
    MAX_M = max(A) * N
    costs = [[None] * N for _ in range(N)]
    dp = [[INF] * (MAX_M + 1) for _ in range(N)]
    S = min(S, MAX_M)
    dp[0][S] = 0
    q = [(0, 0, S)] # time, idx, silver
    while q:
        t, i, m = heapq.heappop(q)
        if dp[i][m] < t:
            continue

        if m + C[i] <= MAX_M:
            if t + D[i] < dp[i][m + C[i]]:
                dp[i][m + C[i]] = t + D[i]
                heapq.heappush(q, (t + D[i], i, m + C[i]))

        for j, c, d in conns[i]:
            if m >= c:
                if t + d < dp[j][m - c]:
                    dp[j][m - c] = t + d
                    heapq.heappush(q, (t + d, j, m - c))

    for i in range(1, N):
        tmp = INF
        for v in dp[i]:
            tmp = min(tmp, v)
        print(tmp)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    S = int(next(tokens))  # type: int
    U = [int()] * (M)  # type: "List[int]"
    V = [int()] * (M)  # type: "List[int]"
    A = [int()] * (M)  # type: "List[int]"
    B = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        U[i] = int(next(tokens))
        V[i] = int(next(tokens))
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    C = [int()] * (N)  # type: "List[int]"
    D = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        C[i] = int(next(tokens))
        D[i] = int(next(tokens))
    solve(N, M, S, U, V, A, B, C, D)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from operator import mul
from functools import reduce
from fractions import gcd
import math
import bisect
import itertools
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
INF = float("inf")


#O(ElogV)
import heapq
def dijkstra_heap(G, si, sj, h, w):
    #始点sから各頂点への最短距離
    d = [[INF] * w for _ in range(h)]
    used = [[False] * w for _ in range(h)]
    d[si][sj] = 0
    used[si][sj] = True

    edgelist = []
    for edge in G[si][sj]:
        cost, i, j = edge[0], edge[1], edge[2]
        heapq.heappush(edgelist, [cost, i, j])
    
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        cost, i, j = minedge[0], minedge[1], minedge[2]
        # print([cost, i, j])
        if used[i][j]:
            continue
        d[i][j] = cost
        used[i][j] = True

        for edge in G[i][j]:
            cost, ni, nj = edge[0], edge[1], edge[2]
            if used[ni][nj]:
                continue
            heapq.heappush(edgelist, [cost + d[i][j], ni, nj])
    return d


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

    U = [0] * M
    V = [0] * M
    A = [0] * M
    B = [0] * M
    for i in range(M):
        U[i], V[i], A[i], B[i] = map(int, input().split())
        U[i] -= 1; V[i] -= 1
    
    L = max(A) * N
    G = [[[] for _ in range(L+1)] for _ in range(N)]
    for i in range(M):
        u, v, a, b = U[i], V[i], A[i], B[i]
        for money in range(L):
            if money - a >= 0:
                G[u][money].append([b, v, money - a])
                G[v][money].append([b, u, money - a])
    
    for station in range(N):
        c, d = map(int, input().split())
        for money in range(L):
            nmoney = money + c
            if nmoney > L:
                nmoney = L
            G[station][money].append([d, station, nmoney])
            G[station][nmoney].append([0, station, money])
    
    if S > L:
        S = L
    ans = dijkstra_heap(G, 0, S, N, L+1)
    for i in range(1, N):
        print(min(ans[i]))
    

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input=lambda: sys.stdin.readline().rstrip()
import heapq
n,m,s=map(int,input().split())
s=min(s,2499)
E=[]
for _ in range(m):
  E.append(tuple(map(int,input().split())))
CD=[]
for _ in range(n):
  CD.append(tuple(map(int,input().split())))
nn=n*2500
edge=[[] for i in range(nn)]
for u,v,a,b in E:
  u-=1
  v-=1
  for i in range(a,2500):
    edge[u*2500+i].append(b*10**6+v*2500+i-a)
    edge[v*2500+i].append(b*10**6+u*2500+i-a)
for i in range(n):
  c,d=CD[i]
  for j in range(2500):
    if j+c<2500:
      edge[i*2500+j].append(d*10**6+i*2500+j+c)

def dijkstra_heap(s):
  d=[float("inf")]*nn
  used=[True]*nn
  d[s]=0
  used[s]=False
  edgelist=[]
  for e in edge[s]:
    heapq.heappush(edgelist,e)
  while edgelist:
    minedge=heapq.heappop(edgelist)
    minedge_cost=minedge//(10**6)
    minedge_v=minedge%(10**6)
    if not used[minedge_v]:
      continue
    d[minedge_v] = minedge_cost
    used[minedge_v] = False
    for e in edge[minedge_v]:
      e_cost=e//(10**6)
      e_v=e%(10**6)
      if used[e_v]:
        heapq.heappush(edgelist,e+minedge_cost*10**6)
  return d
D=dijkstra_heap(s)
for i in range(1,n):
  ans=D[i*2500]
  for j in range(1,2500):
    ans=min(ans,D[i*2500+j])
  print(ans)

Submission status: Accepted

Solution code:
import heapq

MAX = 2500

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

# 頂点リスト : [node, silver, time]
edge = [[] for i in range(n)]
for i in range(m):
    u, v, a, b = map(int, input().split())
    edge[u-1].append([v-1, a, b])
    edge[v-1].append([u-1, a, b])
for i in range(n):
    c, d = map(int, input().split())
    edge[i].append([i, -c, d])

# dp[i][silver] : 頂点iにいて銀貨をsilver枚持っているような状況を作るために必要な最小時間
dp = [[float("inf")]*(MAX+1) for _ in range(n)]
dp[0][s] = 0

# 優先度付きキュー : (time, node, silver)
edgelist = [(0, 0, s)]

while edgelist:
    time, node, silver = heapq.heappop(edgelist)

    for to, silver_cost, time_cost in edge[node]:
        res_silver = min(silver - silver_cost, MAX)
        if res_silver < 0:
            continue
        
        dp_next_value = time + time_cost
        if dp[to][res_silver] <= dp_next_value:
            continue

        dp[to][res_silver] = dp_next_value
        heapq.heappush(edgelist, (dp_next_value, to, res_silver))

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# Generated by https://github.com/kyuridenamida/atcoder-tools
import sys
import heapq

INF = float('inf')


def solve(N: int, M: int, S: int, U: "List[int]", V: "List[int]", A: "List[int]", B: "List[int]", C: "List[int]", D: "List[int]"):
    MAX = max(A) * (N-1)
    S = min(S, MAX)

    G = [[] for _ in range(N)]
    for u, v, a, b in zip(U, V, A, B):
        G[u-1].append([v-1, [a, b]])
        G[v-1].append([u-1, [a, b]])

    dp = [[INF for _ in range(MAX + 1)] for _ in range(N)]
    dp[0][S] = 0

    Q = []
    heapq.heapify(Q)
    heapq.heappush(Q, [0, [0, S]])

    while len(Q) != 0:
        time, [v, s] = heapq.heappop(Q)
        if time > dp[v][s]:
            continue

        if s + C[v] <= MAX:
            ns = s + C[v]
            ntime = time + D[v]
            if dp[v][ns] > ntime:
                dp[v][ns] = ntime
                heapq.heappush(Q, [ntime, [v, ns]])

        for nv, [ns, ntime] in G[v]:
            if s < ns:
                continue
            ns = s - ns
            ntime += time
            if dp[nv][ns] > ntime:
                dp[nv][ns] = ntime
                heapq.heappush(Q, [ntime, [nv, ns]])

    ans = [min(dp[i]) for i in range(1, N)]
    return "\n".join(map(str, ans))


def main():

    sys.setrecursionlimit(10 ** 6)

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    S = int(next(tokens))  # type: int
    U = [int()] * (M)  # type: "List[int]"
    V = [int()] * (M)  # type: "List[int]"
    A = [int()] * (M)  # type: "List[int]"
    B = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        U[i] = int(next(tokens))
        V[i] = int(next(tokens))
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    C = [int()] * (N)  # type: "List[int]"
    D = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        C[i] = int(next(tokens))
        D[i] = int(next(tokens))
    print(solve(N, M, S, U, V, A, B, C, D))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

INF = 10 ** 18

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)]

sumA = 0
for u, v, a, b in UVAB:
    sumA += a

def dijkstra(start, graph) -> list:
    dist = [[INF for _ in range(N + 1)] for _ in range(sumA + 1)]
    dist[start][1] = 0
    heap = []
    heappush(heap, (0, (start, 1)))
    while heap:
        v, (i, j) = heappop(heap)
        for w, (ni, nj) in graph[i][j]:
            if dist[ni][nj] > v + w:
                dist[ni][nj] = v + w
                heappush(heap, (dist[ni][nj], (ni, nj)))
    return dist

graph = [[[] for _ in range(N + 1)] for _ in range(sumA + 1)]

for u, v, a, b in UVAB:
    for i in range(a, sumA + 1):
        graph[i][u].append((b, (i - a, v)))
        graph[i][v].append((b, (i - a, u)))

for j in range(1, N + 1):
    c, d = CD[j - 1]
    for i in range(sumA):
        graph[i][j].append((d, (min(i + c, sumA), j)))

dist = dijkstra(min(S, sumA), graph)

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

Submission status: Accepted

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

from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict
from itertools import combinations, permutations, combinations_with_replacement
from itertools import accumulate
from math import ceil, sqrt, pi

MOD = 10 ** 9 + 7
INF = 10 ** 18

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)]

sumA = 0
for u, v, a, b in UVAB:
    sumA += a
#print(sumA)

def dijkstra(s, graph) -> list:
    dist = [[INF for _ in range(N + 1)] for _ in range(sumA + 1)]
    dist[s][1] = 0
    hp = []
    heappush(hp, (0, (s, 1)))
    while hp:
        #print(hp)
        t, (i, j) = heappop(hp)
        for dt, (ni, nj) in graph[i][j]:
            if dist[ni][nj] > t + dt:
                dist[ni][nj] = t + dt
                heappush(hp, (dist[ni][nj], (ni, nj)))
    #print("")
    return dist

graph = [[[] for _ in range(N + 1)] for _ in range(sumA + 1)]
# graph[i][j] = [(dt, (ni, nj)), ...]
#都市Ajにいるときに、銀貨をi枚持っている
#この時(i, j)から(ni, nj)への遷移にかかる時間はdt

for j in range(1, N + 1):
    c, d = CD[j - 1]
    for i in range(sumA + 1):
        graph[i][j].append((d, (min(i + c, sumA), j)))
#for g in graph[1:][::-1]:
#   print(*g)

for u, v, a, b in UVAB:
    for i in range(a, sumA + 1):
        if i >= a:
            graph[i][u].append((b, (i - a, v)))
            graph[i][v].append((b, (i - a, u)))
#for g in graph[1:]:
#    print(*g)

#print("")
dist = dijkstra(min(S, sumA), graph)

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

Submission status: Accepted

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

INF = 10 ** 18

class Edge():
    def __init__(self, end, cost, time):
        self.end = end
        self.cost = cost
        self.time = time

dp = []
h = []

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

def dijkstra(n, G, cd, start, s, max_s):
    global dp
    dp = [[INF for j in range(max_s+1)] for i in range(n)] 
    push(0, start, s)

    while h:
        # 使っていない頂点のうち、現時点で最も到達短時間が短いものを選びvとする
        t, v, x = heapq.heappop(h)
        if dp[v][x] < t:
            continue
        # 両替
        if x < max_s:
            push(t+cd[v][1], v, min(x+cd[v][0], max_s))
        # vから到達可能な頂点について、到達時間が短くなれば更新
        for e in G[v]:
            push(t+e.time, e.end, x-e.cost)


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)]

es = [[] for i in range(n)]
max_s = 50 * (n-1)

for u, v, a, b in uvab:
    es[u-1].append(Edge(v-1,a,b))
    es[v-1].append(Edge(u-1,a,b))

dijkstra(n, es, cd, 0, min(max_s,s), max_s)

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

Submission status: Accepted

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

INF = 10 ** 18

class Edge():
    def __init__(self, end, cost, time):
        self.end = end
        self.cost = cost
        self.time = time

dp = []
h = []

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

def dijkstra(n, G, cd, start, s, max_s):
    global dp
    dp = [[INF for j in range(max_s+1)] for i in range(n)] 
    push(0, start, s)

    while h:
        # 使っていない頂点のうち、現時点で最も距離の近いものを選びvとする
        t, v, x = heapq.heappop(h)
        if dp[v][x] < t:
            continue
        # 両替
        if x < max_s:
            push(t+cd[v][1], v, min(x+cd[v][0], max_s))

        # vから到達可能な頂点について、距離が短くなれば更新
        for e in G[v]:
            push(t+e.time, e.end, x-e.cost)


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)]

es = [[] for i in range(n)]
max_s = 50 * (n-1)

for u, v, a, b in uvab:
    es[u-1].append(Edge(v-1,a,b))
    es[v-1].append(Edge(u-1,a,b))

dijkstra(n, es, cd, 0, min(max_s,s), max_s)

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

Submission status: Accepted

Solution code:
import sys
from heapq import heappop, heappush

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    N, M, S = map(int, rl().split())
    init_s = min(2500, S)
    graph = [[] for _ in range(N)]
    for _ in range(M):
        u, v, a, b = map(int, rl().split())
        u, v = u - 1, v - 1
        graph[u].append((v, a, b))
        graph[v].append((u, a, b))
    C, D = [0] * N, [0] * N
    for i in range(N):
        C[i], D[i] = map(int, rl().split())
    
    costs = [[10 ** 18] * 2501 for _ in range(N)]
    costs[0][init_s] = 0
    
    que = [(0, 0, init_s)]
    while que:
        t, cur, s = heappop(que)
        self_roop_s = min(s + C[cur], 2500)
        self_roop_t = t + D[cur]
        if self_roop_t < costs[cur][self_roop_s]:
            costs[cur][self_roop_s] = self_roop_t
            heappush(que, (self_roop_t, cur, self_roop_s))
        for child, s_cost, t_cost in graph[cur]:
            if s < s_cost:
                continue
            nt = t + t_cost
            ns = s - s_cost
            if nt < costs[child][ns]:
                costs[child][ns] = nt
                heappush(que, (nt, child, ns))
    
    for costs_i in costs[1:]:
        print(min(costs_i))


if __name__ == '__main__':
    solve()

Submission status: Accepted

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

def dijkstra(edge, start):
    n = len(edge)
    dist = [float("inf")]*n
    dist[start] = 0
    que = [(0, start)]
    while que:
        d, v = heapq.heappop(que)
        if dist[v] < d:
            continue
        for nv, nd in edge[v]:
            if dist[nv] > d + nd:
                dist[nv] = d + nd
                heapq.heappush(que, (dist[nv], nv))
    return dist

n, m, s = map(int, input().split())
G = [[] for _ in range(n)]
if s >= 2500:
  for _ in range(m):
    u, v, a, b = map(int, input().split())
    u -= 1
    v -= 1
    G[u].append((v, b))
    G[v].append((u, b))
  L = dijkstra(G, 0)
else:
  for _ in range(m):
    u, v, a, b = map(int, input().split())
    u -= 1
    v -= 1
    G[u].append((v, a, b))
    G[v].append((u, a, b))
  CD = [list(map(int, input().split())) for _ in range(n)]
  edge = [[] for _ in range(n*2500)]
  for i in range(n):
    c, d = CD[i]
    for k in range(2500):
      for v, a, b in G[i]:
        if k >= a:
          edge[2500*i+k].append((2500*v+(k-a), b))
      if k+c < 2500:
        edge[2500*i+k].append((2500*i+(k+c), d))
  dist = dijkstra(edge, s)
  L = [0]*n
  for i in range(n):
    L[i] = min(dist[2500*i:2500*(i+1)])
print(*L[1:], sep="\n")

Submission status: Accepted

Solution code:
from heapq import heappop, heappush
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

# グラフを拡張してダイクストラ法を使う

def main():
    N,M,S = map(int, readline().split())

    E = [[] for _ in range(N+1)]
    for _ in range(M):
        u,v,a,b = map(int, readline().split())
        E[u].append((v, a, b))
        E[v].append((u, a, b))

    cd = map(int, read().split())
    CD = []
    for c, d in zip(*[iter(cd)]*2):
        CD.append((c, d))

    # Dijkstra
    # d[v][s] := 頂点vで,所持金sとなる最小の所要時間
    if S > 2500:
        S = 2500 - 1
    INF = 10**15
    d = [[INF] * 2500 for _ in range(N+1)]
    d[1][S] = 0

    Q = []
    heappush(Q, (0, S, 1))  # (所要時間, 所持金, 頂点)
    
    while Q:
        time, s, u = heappop(Q)
        if time > d[u][s]:
            continue
        
        c_u, d_u = CD[u-1]
        if s + c_u < 2500 and time + d_u < d[u][s + c_u]:
            d[u][s + c_u] = time + d_u
            heappush(Q, (time + d_u, s + c_u, u))
        
        for v, a, b in E[u]:
            if s >= a and time + b < d[v][s - a]:
                d[v][s - a] = time + b
                heappush(Q, (time + b, s - a, v))

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


if __name__ == "__main__":
    main()