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 sys
from heapq import*
input = sys.stdin.readline
def main():
    N,M,S = map(int,input().split())
    edges = [[]for _ in range(N)]
    for _ in range(M):
        u,v,a,b = map(int,input().split())
        u -= 1
        v -= 1
        edges[u].append((v,a,b))
        edges[v].append((u,a,b))
    ex = [tuple(map(int,input().split()))for _ in range(N)]

    M = 2500
    dist = [[2**60]*M for _ in range(N)]
    if S >= M:S = M-1
    dist[0][S] = 0
    q = [(0,S,0)]
    while q:
        cost,sil,u = heappop(q)
        if dist[u][sil] < cost:continue
        if sil+ex[u][0] < M and cost+ex[u][1] < dist[u][sil+ex[u][0]]:
            dist[u][sil+ex[u][0]] = cost + ex[u][1]
            heappush(q,(dist[u][sil+ex[u][0]],sil+ex[u][0],u))
        for v,a,b in edges[u]:
            if sil >= a and cost+b < dist[v][sil-a]:
                dist[v][sil-a] = cost+b
                heappush(q,(dist[v][sil-a],sil-a,v))
    for t in range(1,N):
        print(min(dist[t]))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from heapq import*
input = sys.stdin.readline
def main():
    N,M,S = map(int,input().split())
    edges = [[]for _ in range(N)]
    d = {}
    A = 0
    for _ in range(M):
        u,v,a,b = map(int,input().split())
        u -= 1
        v -= 1
        A = max(A,a)
        edges[u].append((v,a,b))
        edges[v].append((u,a,b))
    ex = [tuple(map(int,input().split()))for _ in range(N)]

    M = 2500
    dist = [[2**60]*M for _ in range(N)]
    prev = [-1]*N
    if S >= M:S = M-1
    dist[0][S] = 0
    q = [(0,S,0)]
    while q:
        cost,sil,u = heappop(q)
        if dist[u][sil] < cost:continue
        if sil+ex[u][0] < M and cost+ex[u][1] < dist[u][sil+ex[u][0]]:
            dist[u][sil+ex[u][0]] = cost + ex[u][1]
            heappush(q,(dist[u][sil+ex[u][0]],sil+ex[u][0],u))
        for v,a,b in edges[u]:
            if sil >= a and cost+b < dist[v][sil-a]:
                dist[v][sil-a] = cost+b
                heappush(q,(dist[v][sil-a],sil-a,v))
    for t in range(1,N):
        print(min(dist[t]))





if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
INF=1000000000000000 # 1e15
MAX=50*50 # 2500

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

dp=[[INF] * (MAX + 1) for _ in range(n)]
#dp[i][j]=k <=> 最短k分後に街iに所持銀貨j枚で行ける
dp[0][min(MAX, s)] = 0
updated = True
while updated:
  updated = False
  for i in range(n):
    for j in range(MAX + 1):
      dest = min(MAX, j + c[i])
      if dp[i][j] + d[i] < dp[i][dest]:
        updated = True
        dp[i][dest] = dp[i][j] + d[i]
  for i in range(m):
    for j in range(a[i], MAX+1):
      # u[i] -> v[i]
      if dp[u[i]][j] + b[i] < dp[v[i]][j - a[i]]:
        updated = True
        dp[v[i]][j - a[i]] = dp[u[i]][j] + b[i]
      # v[i] -> u[i]
      if dp[v[i]][j] + b[i] < dp[u[i]][j - a[i]]:
        updated = True
        dp[u[i]][j - a[i]] = dp[v[i]][j] + b[i]
for i in range(1, n):
  print(min(dp[i]))

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix

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

AMAX = 50
NODE_MAX = AMAX * (n - 1)
N = (NODE_MAX + 1) * n

U = []
V = []
C = []

for u, v, a, b in uvab:
    u -= 1
    v -= 1
    u *= NODE_MAX + 1
    v *= NODE_MAX + 1
    for i in range(NODE_MAX + 1 - a):
        U.append(u + i + a)
        V.append(v + i)
        C.append(b)
        U.append(v + i + a)
        V.append(u + i)
        C.append(b)


for i, (c, d) in enumerate(cd):
    base = i * (NODE_MAX + 1)
    for j in range(NODE_MAX):
        nxt = base + min(j + c, NODE_MAX)
        frm = base + j
        U.append(frm)
        V.append(nxt)
        C.append(d)

g = csr_matrix((C, (U, V)), shape=(N, N))
dist = dijkstra(g, indices=min(s, NODE_MAX)).astype(int)
dist[dist < 0] = dist.max()
for i in range(1, n):
    base = i * (NODE_MAX + 1)
    ans = dist[base:base+NODE_MAX+1].min()
    print(ans)

Submission status: Accepted

Solution code:
n,m,s=map(int,input().split())
s=min(s,2500)
edge=[[] for i in range(n*50*51)]
for i in range(m):
    u,v,a,b=map(int,input().split())
    for j in range(a,2501):
        edge[u-1+j*n].append((v-1+(j-a)*n,b))
        edge[v-1+j*n].append((u-1+(j-a)*n,b))
for i in range(n):
    c,d=map(int,input().split())
    for j in range(2501-c):
        edge[i+j*n].append((i+(j+c)*n,d))
    for j in range(2500):
        edge[i+(j+1)*n].append((i+j*n,0))

def dijkstra(s,n):
    from heapq import heappush,heappop
    d = [float('inf') for i in range(n+1)]
    pq = []
    d[s]=0
    heappush(pq,(0,s))
    while pq:
        dist,u = heappop(pq)
        for v,cost in edge[u]:
            if d[v]<=dist+cost:
                continue
            d[v]=dist+cost
            heappush(pq,(d[v],v))
    return d
d=dijkstra(s*n,n*50*51)
for i in range(1,n):
    print(d[i])

Submission status: Accepted

Solution code:
import heapq
N,M,S = [int(i) for i in input().split()]
S = min(S,2500)
Train = [[] for p in range(N)]
for j in range(M):
    U,V,A,B = [int(hoge) for hoge in input().split()]
    Train[U-1].append((V-1,(A,B)))#(次、(運賃,時間))
    Train[V-1].append((U-1,(A,B)))

CD = [[int(hoge) for hoge in input().split()] for k in range(N)]

num = N*2501          # グラフのノード数
dist = [float('inf') for i in range(num)] # 始点から各頂点までの最短距離を格納する
prev = [float('inf') for i in range(num)] # 最短経路における，その頂点の前の頂点のIDを格納する
    
start = 0 * 2501 + S
dist[start] = 0 #ID = Point * 2501 + Money(P=ID//2501 M = ID%2501)
q = []                  # プライオリティキュー．各要素は，(startからある頂点vまでの仮の距離, 頂点vのID)からなるタプル
heapq.heappush(q, (0, start)) # 始点をpush
while len(q) != 0:
    prov_cost, src = heapq.heappop(q) # pop(仮の距離,ID)
    
    # プライオリティキューに格納されている最短距離が，現在計算できている最短距離より大きければ，distの更新をする必要はない
    if dist[src] < prov_cost:
        continue

    # 他の頂点の探索
    src_Point = src//2501
    src_Money = src%2501
    src_RyogaeM = CD[src_Point][0]
    src_RyogaeTime = CD[src_Point][1]

    RyogaeAfter = min(2500,src_Money + src_RyogaeM)
    RyogaeID = src - src_Money + RyogaeAfter
    cost = src_RyogaeTime

    if dist[RyogaeID] > dist[src] + cost:
        dist[RyogaeID] = dist[src] + cost#distの更新
        heapq.heappush(q,(dist[RyogaeID],RyogaeID))

    for togo,trainfo in Train[src//2501]:#つながってる線路について
        cost = trainfo[1]#src→dest間の距離
        fee = trainfo[0]
        dest = togo * 2501 + src_Money - fee
        if src_Money >= fee and dist[dest] > dist[src] + cost:
            dist[dest] = dist[src] + cost # distの更新
            heapq.heappush(q, (dist[dest], dest)) # キューに新たな仮の距離の情報をpush
            prev[dest] = src                      # 前の頂点を記録

curpoint = 0
TheEnd = 2500
curmin = float("inf")
for point,d in enumerate(dist):
    if d < curmin:
        curmin = d
    if point == TheEnd:
        TheEnd += 2501
        if point > 2500:
            print(curmin)
        curmin = float("inf")

Submission status: Accepted

Solution code:
n,m,s=map(int,input().split())
s=min(s,2500)
edge=[[] for i in range(n*50*51)]
for i in range(m):
    u,v,a,b=map(int,input().split())
    for j in range(a,2501):
        edge[u-1+j*n].append((v-1+(j-a)*n,b))
        edge[v-1+j*n].append((u-1+(j-a)*n,b))
for i in range(n):
    c,d=map(int,input().split())
    for j in range(2501-c):
        edge[i+j*n].append((i+(j+c)*n,d))
    for j in range(2500):
        edge[i+(j+1)*n].append((i+j*n,0))
s=s*n
from heapq import heappush,heappop,heapify
d = [float('inf') for i in range(n*50*51)]
pq = []
d[s]=0
heappush(pq,(0,s))
while pq:
    dist,u = heappop(pq)
    for v,cost in edge[u]:
        if d[v]<=dist+cost:
            continue
        d[v]=dist+cost
        heappush(pq,(d[v],v))
for i in range(1,n):
    print(d[i])

Submission status: Accepted

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

AM = 50*50+1
INF = 10**15

N, M, S = map(int, input().split())
graph = [[] for _ in range(N)]
for _ in range(M):
    u, v, a, b = map(int, input().split())
    graph[u-1].append((a, b, v-1))
    graph[v-1].append((a, b, u-1))
C = []
D = []
for _ in range(N):
    c, d = map(int, input().split())
    C.append(c)
    D.append(d)

# dp[n][cost] := cost でいけるnの最短
dp = [[INF]*(AM+1) for _ in range(N)]
dp[0][min(AM, S)] = 0
q = [(0, min(AM, S), 0)]
while q:
    dis, cost, p = hp.heappop(q)
    if dp[p][cost] < dis:
        continue
    if 0 <= cost+C[p] <= AM and dp[p][cost+C[p]] > dp[p][cost]+D[p]:
        dp[p][cost+C[p]] = dp[p][cost] + D[p]
        hp.heappush(q, (dp[p][cost+C[p]], cost+C[p], p))
    for a, b, np in graph[p]:
        if 0 <= cost-a <= AM and dp[np][cost-a] > dp[p][cost] + b:
            dp[np][cost-a] = dp[p][cost]+b
            hp.heappush(q, (dp[np][cost-a], cost-a, np))

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

Submission status: Accepted

Solution code:
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)]

M = 50 * n + 1
s = min(s, M - 1)

dp = [[float('inf')] * M for _ in range(n)]

import math
dp[0][s] = 0
c, d = cd[0][0], cd[0][1]
for jj in range(M):
    dp[0][jj] = min(dp[0][jj], dp[0][s] + max(math.ceil((jj - s) / c), 0) * d)

while True:
    flag = False

    for i in range(m):
        u1, v1, a, b = uvab[i][0] - 1, uvab[i][1] - 1, uvab[i][2], uvab[i][3]
        for u, v in [(u1, v1), (v1, u1)]:
            for j in range(M - a):
                tmp = dp[u][j + a] + b
                if tmp < dp[v][j]:
                    dp[v][j] = tmp
                    flag = True

            if flag:
                c, d = cd[v][0], cd[v][1]
                for jj in range(c, M):
                    tmp = dp[v][jj - c] + d
                    if tmp < dp[v][jj]:
                        dp[v][jj] = tmp

    if flag == False:
        break

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

Submission status: Accepted

Solution code:
import heapq

INF = 2**60
# input
N, M, S = list(map(int, input().split()))

E = []
for i in range(N):
    E.append([])

for i in range(M):
    u, v, a, b = list(map(int, input().split()))
    E[u-1].append((v-1, a, b))
    E[v-1].append((u-1, a, b))

C, D = [], []
for i in range(N):
    c, d = list(map(int, input().split()))
    C.append(c)
    D.append(d)
# input

#dist[N][N]
dist = []
for i in range(51):
    dist.append([])
    for j in range(2501):
        dist[i].append(INF)

dist[0][min(S, 2500)] = 0


a = []
heapq.heappush(a, (INF, INF, INF))
heapq.heappush(a, (0, 0, min(S, 2500)))

while True:
    t = heapq.heappop(a)
    at = t[1]
    if t[0] == INF:
        break
    if dist[at][t[2]] < t[0]:
        continue
    if t[2] != 2500:
        if dist[t[1]][min(t[2] + C[at], 2500)] > t[0] + D[at]:
            dist[t[1]][min(t[2] + C[at], 2500)] = t[0] + D[at]
            heapq.heappush(a, (t[0] + D[at], t[1], min(t[2] + C[at], 2500)))

    for v in E[at]:
        nat = v[0]
        nd = t[0] + v[2]
        nrest = t[2] - v[1]
        if t[2] == 2500:
            nrest = 2500
        if nrest < 0:
            continue
        if dist[nat][nrest] > nd:
            dist[nat][nrest] = nd
            heapq.heappush(a, (nd, nat, nrest))


ans = [INF] * N
for i in range(N):
    for j in range(2501):
        ans[i] = min(ans[i], dist[i][j])


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

Submission status: Accepted

Solution code:
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)]
graph = [[] for i in range((n+1)*2500+1)]
for u2,v2,a,b in uvab:
  for u,v in (u2,v2),(v2,u2):
    for i in range(u*2500,u*2500+2500):
      if i%2500 >= a:
        graph[i].append((i+(v-u)*2500-a,b))
for i in range(n):
  c,d = cd[i]
  for j in range((i+1)*2500,(i+2)*2500-1):
    graph[j].append((min((i+2)*2500-1,j+c),d))
import heapq as hq
start = 2500+min(s,2499)
dist = [10**18]*((n+1)*2500+1)
dist[start] = 0
q = [(0,start)]
hq.heapify(q)
while q:
  _,x = hq.heappop(q)
  for y,d in graph[x]:
    if dist[y] > dist[x]+d:
      dist[y] = dist[x]+d
      hq.heappush(q,(dist[y],y))
for i in range(2,n+1):
  print(min(dist[i*2500:(i+1)*2500]))

Submission status: Accepted

Solution code:
import heapq
def Dijkstra(edge,start):
    d = [float('inf')]*(n*(A+1))
    d[start] = 0
    pq = [(0,start)]
    heapq.heapify(pq)
    while pq:
        dist,p = heapq.heappop(pq)
        for to,cost in edge[p].items():
            if d[to] <= dist + cost:continue
            d[to] = dist + cost
            heapq.heappush(pq, (d[to], to))
    return d

n,m,s = map(int,input().split())
edge = [{} for _ in range(n)]
A = 2500
for i in range(m):
    u,v,a,b = map(int,input().split())
    # A += a
    u -= 1
    v -= 1
    edge[u][v] = (a,b)
    edge[v][u] = (a,b)


A *= 2
C = [0]*n
D = [0]*n
for i in range(n):
    C[i],D[i] = map(int,input().split())

path = [{} for _ in range(n*(A+1))]
for i in range(n):
    for j in range(A+1):
        for to,(a,b) in edge[i].items():
            if j - a >= 0:
                path[i*(A+1)+j][to*(A+1)+j-a] = b
        path[i*(A+1)+j][i*(A+1)+min(j+C[i],A)] = D[i]

ans = Dijkstra(path,min(s,A))
for i in range(1,n):
    print(min(ans[i*(A+1):i*(A+1)+A+1]))

Submission status: Accepted

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

INF = float('inf')  ###
maxMoney = 2502  ### *2?
#maxMoney = 20

N, M, S = map(int, input().split())
adjL = [[] for _ in range(N)]
for _ in range(M):
    u, v, coin, tm = map(int, input().split())
    u, v = u-1, v-1
    adjL[u].append((v, coin, tm))
    adjL[v].append((u, coin, tm))
moneys, tms = [], []
for _ in range(N):
    money, tm = map(int, input().split())
    moneys.append(money)
    tms.append(tm)

# 単一始点最短経路を求める（Dijkstra法）
def Dijkstra(adjList):
    numV = N * (maxMoney+1)
    numUsed = 0
    costss = [[INF]*(maxMoney+1) for _ in range(N)]
    costss[0][S] = 0
    PQ = []
    heappush(PQ, (0, 0, S))
    while PQ:
        cNow, vNow, moneyNow = heappop(PQ)
        if cNow > costss[vNow][moneyNow]: continue
        numUsed += 1
        if numUsed == numV: break
        for v2, coin, tm in adjList[vNow]:
            if moneyNow < coin: continue
            c2 = cNow + tm
            m2 = moneyNow - coin
            if c2 < costss[v2][m2]:
                costss[v2][m2] = c2
                heappush(PQ, (c2, v2, m2))
        c2 = cNow + tms[vNow]
        m2 = moneyNow + moneys[vNow]
        if m2 > maxMoney:
            m2 = maxMoney
        if c2 < costss[vNow][m2]:
            costss[vNow][m2] = c2
            heappush(PQ, (c2, vNow, m2))
    return costss

S = min(S, maxMoney)
costss = Dijkstra(adjL)
#for i in range(N):
#    print(i, costss[i])

anss = [min(costss[t]) for t in range(1, N)]
print('\n'.join(map(str, anss)))

Submission status: Accepted

Solution code:
from heapq import heapify, heappush as hpush, heappop as hpop
N, M, S = map(int, input().split())
k = 2451
X = [[] for _ in range(N * k)]
for _ in range(M):
    u, v, a, b = map(int, input().split())
    u, v = u-1, v-1
    for i in range(a, k):
        X[u * k + i].append([v * k + i - a, b])
        X[v * k + i].append([u * k + i - a, b])

for i in range(N):
    c, d = map(int, input().split())
    for j in range(k - 1):
        X[i * k + j].append([i * k + min(j + c, k - 1), d])

def dijkstra(n, E, i0=0):
    h = [[0, i0]]
    D = [-1] * n
    done = [0] * n
    D[i0] = 0
    
    while h:
        d, i = hpop(h)
        done[i] = 1
        for j, w in E[i]:
            nd = d + w
            if D[j] < 0 or D[j] > nd:
                if done[j] == 0:
                    hpush(h, [nd, j])
                    D[j] = nd
    return D

D = dijkstra(N * k, X, min(S, k - 1))
print(*[min(D[i * k:(i+1) * k]) for i in range(N)][1:], sep = "\n")

Submission status: Accepted

Solution code:
from heapq import *
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():

    inf=10**16
    n,m,s=MI()
    to=[[] for _ in range(n)]
    for _ in range(m):
        u,v,a,b=MI()
        to[u-1].append((v-1,a,b))
        to[v-1].append((u-1,a,b))
    cd=LLI(n)

    dp=[[inf]*3005 for _ in range(n)]
    hp=[]
    heappush(hp,(0,min(s,3000),0))
    dp[0][min(s,3000)]=0

    while hp:
        t,g,u=heappop(hp)
        if dp[u][g]<t:continue
        c,d=cd[u]
        if g+c<3000:
            if dp[u][g + c] > t + d:
                dp[u][g + c] = t + d
                heappush(hp, (t + d, g + c, u))
        else:
            if dp[u][3000] > t + d:
                dp[u][3000] = t + d
                heappush(hp, (t + d, 3000, u))
        for v,a,b in to[u]:
            if g-a<0:continue
            if dp[v][g-a]<=t+b:continue
            dp[v][g - a] = t + b
            heappush(hp,(t+b,g-a,v))
    for u in range(1,n):
        print(min(dp[u]))

main()

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
inf = float('inf')
def dijkstra(graph:list, node:int, start:int) -> list:
    dist = [inf]*node

    dist[start] = 0
    heap = [(0,start)]
    while heap:
        cost,thisNode = heappop(heap)
        for NextCost,NextNode in graph[thisNode]:
            dist_cand = dist[thisNode]+NextCost
            if dist_cand < dist[NextNode]:
                dist[NextNode] = dist_cand
                heappush(heap,(dist[NextNode],NextNode))
    return dist

N,M,S = map(int,input().split())
graph = [[] for i in range(2501*N)]
for i in range(M):
    u,v,a,b = map(int,input().split())
    u -= 1
    v -= 1
    for s in range(a,2501):
        graph[2501*u+s].append([b,2501*v+s-a])
        graph[2501*v+s].append([b,2501*u+s-a])

for i in range(N):
    c,d = map(int,input().split())
    for s in range(2500):
        graph[2501*i+s].append([d,2501*i+min(2500,s+c)])

dist = dijkstra(graph,2501*N,min(2500,S))

ans = [inf]*N
for i in range(N):
    for s in range(2501):
        ans[i] = min(ans[i],dist[2501*i+s])

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")

#solve
def solve():
    n, m, s = LI()
    uvab = LIR(m)
    cd = LIR(n)
    dp = [[inf] * 2501 for i in range(n)]
    edg = [[] for i in range(n)]
    for u, v, a, b in uvab:
        edg[u - 1].append((v - 1, a, b))
        edg[v - 1].append((u - 1, a, b))
    for i, (c, d) in enumerate(cd):
        edg[i].append((i, -c, d))
    if s >= 2501:
        s = 2500
    q = [(0, 0, s)]
    dp[0][s] = 0
    time = 0
    while q:
        time, p, score = heappop(q)
        for e, a, b in edg[p]:
            timebuf = time
            if 0 <= score - a <= 2500:
                timebuf += b
                if dp[e][score - a] > timebuf:
                    dp[e][score - a] = timebuf
                    heappush(q, (timebuf, e, score - a))
                    for i in range(score - a, -1, -1):
                        if dp[e][i] > timebuf:
                            dp[e][i] = timebuf
                        else:
                            break
    
    for i in range(1, n):
        print(min(dp[i]))

    return


#main
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
from collections import deque

N,M,S = map(int,input().split())
city = [[]for i in range(N)]
for i in range(M):
    u,v,a,b = map(int,input().split())
    city[u-1].append([v-1,a,b])
    city[v-1].append([u-1,a,b])
ex = [[] for i in range(N)]
for i in range(N):
    c,d = map(int,input().split())
    ex[i] = [c,d]

MCOIN = 5000

cost = [[float('inf')]*(MCOIN+500) for i in range(N)]
cost[0][min(MCOIN,S)] = 0

queue = deque([[0,min(MCOIN,S)]])
while queue:
    p,m = queue.popleft()
    if m < MCOIN and cost[p][m+ex[p][0]] > cost[p][m] + ex[p][1]:
        queue.append([p,m+ex[p][0]])
        cost[p][m+ex[p][0]] = cost[p][m] + ex[p][1]
    for v,a,b in city[p]:
        if m >= a  and cost[v][m-a] > cost[p][m] + b:
            queue.append([v,m-a])
            cost[v][m-a] = cost[p][m] + b

for i in cost[1:]:
    print(min(i))

Submission status: Accepted

Solution code:
import heapq
import os
from collections import defaultdict

import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353


N, M, S = list(map(int, sys.stdin.buffer.readline().split()))
UVAB = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(M)]
CD = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(N)]
CD = [(0, 0)] + CD

graph = [[] for _ in range(N + 1)]
for u, v, a, b in UVAB:
    graph[u].append((a, b, v))
    graph[v].append((a, b, u))
for vs in graph:
    vs.sort()

mada = set(list(range(2, N + 1)))
heap = [(0, 1, S)]
ans = [INF] * (N + 1)
ans[1] = 0
# dp[v, s]: v にお金を s 持ってる状態で来たときの最小値
dp = defaultdict(lambda: INF)
dp[1, S] = 0
while heap and mada:
    d, v, s = heapq.heappop(heap)
    if d > dp[v, s]:
        continue
    if v in mada:
        mada.remove(v)

    ans[v] = min(ans[v], d)
    for a, b, u in graph[v]:
        if s - a < 0:
            break
        if d + b < dp[u, s - a]:
            dp[u, s - a] = d + b
            heapq.heappush(heap, (d + b, u, s - a))
    c, dd = CD[v]
    sc = min(s + c, 50 * N + 10)
    if d + dd < dp[v, sc]:
        dp[v, sc] = d + dd
        heapq.heappush(heap, (d + dd, v, sc))

print(*ans[2:], sep='\n')

Submission status: Accepted

Solution code:
import heapq


n, m, s = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]
change = [list(map(int, input().split())) for i in range(n)]
INF = 10 ** 18
MAX_ = 2600

graph = [[] for i in range(n)]
for u, v, cost, time in info:
    u -= 1
    v -= 1
    graph[u].append((v, cost, time))
    graph[v].append((u, cost, time))


dist = [INF] * ((MAX_ + 1) * n)
dist[min(s, MAX_)] = 0

q = [(0, min(s, MAX_), 0)] # q = [(時間, 銀貨, 現在地)]
while q:
    d, gin, v = heapq.heappop(q)

    if dist[v * (MAX_ + 1) + gin] < d:
        continue

    cc, dd = change[v]
    tmp = gin
    r = [gin]
    while True:
        if tmp + cc <= MAX_:
            if dist[v * (MAX_ + 1) + tmp + cc] > dist[v * (MAX_ + 1) + tmp] + dd:
                dist[v * (MAX_ + 1) + tmp + cc] = dist[v * (MAX_ + 1) + tmp] + dd
                r.append(tmp)
            else:
                break
            tmp += cc
        else:
            break

    for nxt_v, cost, time in graph[v]:
        for g in r:
            if g - cost < 0:
                continue
            if dist[v * (MAX_ + 1) + g] + time < dist[nxt_v * (MAX_ + 1) + g - cost]:
                dist[nxt_v * (MAX_ + 1) + g - cost] = dist[v * (MAX_ + 1) + g] + time
                heapq.heappush(q, (dist[nxt_v * (MAX_ + 1) + g - cost], g - cost, nxt_v))

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

Submission status: Accepted

Solution code:
class Dijkstra():
    """ ダイクストラ法
    重み付きグラフにおける単一始点最短路アルゴリズム

    * 使用条件
        - 負のコストがないこと
        - 有向グラフ、無向グラフともにOK

    * 計算量はO(E*log(V))

    * ベルマンフォード法より高速なので、負のコストがないならばこちらを使うとよい
    """
    class Edge():
        """ 重み付き有向辺 """
        def __init__(self, _to, _cost):
            self.to = _to
            self.cost = _cost

    def __init__(self, V):
        """ 重み付き有向辺
        無向辺を表現したいときは、_fromと_toを逆にした有向辺を加えればよい

        Args:
            V(int): 頂点の数
        """
        self.G = [[] for i in range(V)]  # 隣接リストG[u][i] := 頂点uのi個目の隣接辺
        self._E = 0  # 辺の数
        self._V = V  # 頂点の数

    @property
    def E(self):
        """ 辺数
        無向グラフのときは、辺数は有向グラフの倍になる
        """
        return self._E

    @property
    def V(self):
        """ 頂点数 """
        return self._V

    def add(self, _from, _to, _cost):
        """ 2頂点と、辺のコストを追加する """
        self.G[_from].append(self.Edge(_to, _cost))
        self._E += 1

    def shortest_path(self, s):
        """ 始点sから頂点iまでの最短路を格納したリストを返す
        Args:
            s(int): 始点s
        Returns:
            d(list): d[i] := 始点sから頂点iまでの最短コストを格納したリスト。
                     到達不可の場合、値はfloat("inf")
        """
        import heapq
        que = []  # プライオリティキュー（ヒープ木）
        d = [float("inf")] * self.V
        d[s] = 0
        heapq.heappush(que, (0, s))  # 始点の(最短距離, 頂点番号)をヒープに追加する

        while len(que) != 0:
            cost, v = heapq.heappop(que)
            # キューに格納されている最短経路の候補がdの距離よりも大きければ、他の経路で最短経路が存在するので、処理をスキップ
            if d[v] < cost: continue

            for i in range(len(self.G[v])):
                # 頂点vに隣接する各頂点に関して、頂点vを経由した場合の距離を計算し、今までの距離(d)よりも小さければ更新する
                e = self.G[v][i]  # vのi個目の隣接辺e
                if d[e.to] > d[v] + e.cost:
                    d[e.to] = d[v] + e.cost  # dの更新
                    heapq.heappush(que, (d[e.to], e.to))  # キューに新たな最短経路の候補(最短距離, 頂点番号)の情報をpush
        return d

N,M,S=map(int,input().split())
pro=Dijkstra(N*(50*(N-1)+1))
for i in range(0,M):
    u,v,a,b=map(int,input().split())
    for j in range(a,50*(N-1)+1):
        pro.add(N*j+u-1,N*(j-a)+v-1,b)
        pro.add(N*j+v-1,N*(j-a)+u-1,b)

for i in range(0,N):
    c,d=map(int,input().split())
    for j in range(0,50*(N-1)):
        to=min(50*(N-1),j+c)
        pro.add(N*j+i,N*to+i,d)

S=min(50*(N-1),S)
ans=pro.shortest_path(N*S)
for i in range(1,N):
    p=float("inf")
    for j in range(0,50*(N-1)+1):
        p=min(p,ans[N*j+i])
    print(p)