Language: C

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

# 2501×nの[]行列
# 0~2500枚 × 頂点数
edge=[[[] for i in range(50*50+1)] for i in range(n)]

# (頂点, コスト)→(頂点, コスト)へ辺を渡っての遷移（頂点が変わる）
# u,v,a,bが与えられるたびに、edgeを更新
for i in range(m):
    u,v,a,b=map(int,input().split())
    
    # jは、保有銀貨枚数
    # j:a→2500なのは、jがa未満であれば、隣の頂点に行けないから
    for j in range(a,2501):
        edge[u-1][j].append((v-1,j-a,b))
        edge[v-1][j].append((u-1,j-a,b))

# (頂点, コスト)→(頂点, コスト)へ、その頂点に留まって両替の遷移（頂点変わらない）
# c,dが与えられるたびに、edgeを更新
for i in range(n):
    c,d=map(int,input().split())
      
    # 銀貨を捨てるのはノーコスト
    # 2500枚以上持ってたら、2500枚持ってることと同値と考える
    for j in range(2500):
        if j+c>=2500:
            edge[i][j].append((i,2500,d))
        elif j+c<2500:
            edge[i][j].append((i,j+c,d))
        
from heapq import heappush,heappop,heapify

# dはn×2501のすべての状態の最小コストの表
d=[[float('inf')  for i in range(50*50+1)] for i in range(n)]

# 初期値。頂点0, 銀貨Sには、コスト0で到達
d[0][s]=0

pq = []
heappush(pq,(0,0,s))

while len(pq):
    # [コスト, 頂点, 銀貨数]で、コストをkeyとして、heapソートして、一番コストが低いリストを先頭に持ってくる
    _,u,g = heappop(pq)
    
    # 頂点までのコストが更新できれば更新してヒープに登録
    # edge[u][g]は、頂点u, 銀貨g枚の状態から、行ける状態のtuple(頂点, 銀貨数, コスト)を呼び出す
    # pqには、[コスト, 頂点, 銀貨数]の順で入れている
    for tuple in edge[u][g]:
        if d[tuple[0]][tuple[1]]>d[u][g]+tuple[2]:
            d[tuple[0]][tuple[1]]=d[u][g]+tuple[2]
            heappush(pq,[d[u][g]+tuple[2],tuple[0],tuple[1]])
            
# d[i]で、頂点iにおける保有銀貨数に応じたコストが入ったリストを呼び出せる
# リストの中で、一番小さいコストのやつを呼び出せば、その頂点に行ける最小コストと同値である
for i in range(1,n):
    print(min(d[i]))


Compiler output:
main.c:1:1: warning: data definition has no type or storage class
    1 | n,m,s=map(int,input().split())
      | ^
main.c:1:1: error: type defaults to 'int' in declaration of 'n' [-Wimplicit-int]
main.c:1:3: error: type defaults to 'int' in declaration of 'm' [-Wimplicit-int]
    1 | n,m,s=map(int,input().split())
      |   ^
main.c:1:5: error: type defaults to 'int' in declaration of 's' [-Wimplicit-int]
    1 | n,m,s=map(int,input().split())
      |     ^
main.c:1:7: error: implicit declaration of function 'map' [-Wimplicit-function-declaration]
    1 | n,m,s=map(int,input().split())
      |       ^~~
main.c:1:11: error: expected expression before 'int'
    1 | n,m,s=map(int,input().split())
      |           ^~~
main.c:2:1: error: expected ',' or ';' before 's'
    2 | s=min(s,2500)
      | ^
main.c:4:7: error: "×" is not a valid filename
    4 | # 2501×nの[]行列
      |       ^
main.c:5:4: error: "~" is not a valid filename
    5 | # 0~2500枚 × 頂点数
      |    ^
main.c:8:3: error: invalid preprocessing directive #(
    8 | # (頂点, コスト)→(頂点, コスト)へ辺を渡っての遷移（頂点が変わる）
      |   ^
main.c:9:3: error: invalid preprocessing directive #u
    9 | # u,v,a,bが与えられるたびに、edgeを更新
      |   ^
main.c:13:7: error: invalid preprocessing directive #j\U0000306f
   13 |     # jは、保有銀貨枚数
      |       ^~~
main.c:14:7: error: invalid preprocessing directive #j
   14 |     # j:a→2500なのは、jがa未満であれば、隣の頂点に行けないから
      |       ^
main.c:19:3: error: invalid preprocessing directive #(
   19 | # (頂点, コスト)→(頂点, コスト)へ、その頂点に留まって両替の遷移（頂点変わらない）
      |   ^
main.c:20:3: error: invalid preprocessing directive #c
   20 | # c,dが与えられるたびに、edgeを更新
      |   ^
main.c:24:7: error: invalid preprocessing directive #\U00009280\U00008ca8\U00003092\U00006368\U00003066\U0000308b\U0000306e\U0000306f\U000030ce\U000030fc\U000030b3\U000030b9\U000030c8
   24 |     # 銀貨を捨てるのはノーコスト
      |       ^~~~~~~~~~~~~~~~~~~~~~~~~~
main.c:25:7: error: "2500枚以上持ってたら" after # is not a positive integer
   25 |     # 2500枚以上持ってたら、2500枚持ってることと同値と考える
      |       ^~~~~~~~~~~~~~~~~~~~
main.c:34:3: error: invalid preprocessing directive #d\U0000306fn
   34 | # dはn×2501のすべての状態の最小コストの表
      |   ^~~~
main.c:35:11: warning: multi-character character constant [-Wmultichar]
   35 | d=[[float('inf')  for i in range(50*50+1)] for i in range(n)]
      |           ^~~~~
main.c:37:3: error: invalid preprocessing directive #\U0000521d\U0000671f\U00005024
   37 | # 初期値。頂点0, 銀貨Sには、コスト0で到達
      |   ^~~~~~
main.c:44:7: error: invalid preprocessing directive #[
   44 |     # [コスト, 頂点, 銀貨数]で、コストをkeyとして、heapソートして、一番コストが低いリストを先頭に持ってくる
      |       ^
main.c:47:7: error: invalid preprocessing directive #\U00009802\U000070b9\U0000307e\U00003067\U0000306e\U000030b3\U000030b9\U000030c8\U0000304c\U000066f4\U000065b0\U00003067\U0000304d\U0000308c\U00003070\U000066f4\U000065b0\U00003057\U00003066\U000030d2\U000030fc\U000030d7\U0000306b\U0000767b\U00009332
   47 |     # 頂点までのコストが更新できれば更新してヒープに登録
      |       ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
main.c:48:7: error: invalid preprocessing directive #edge
   48 |     # edge[u][g]は、頂点u, 銀貨g枚の状態から、行ける状態のtuple(頂点, 銀貨数, コスト)を呼び出す
      |       ^~~~
main.c:49:7: error: invalid preprocessing directive #pq\U0000306b\U0000306f
   49 |     # pqには、[コスト, 頂点, 銀貨数]の順で入れている
      |       ^~~~~~
main.c:55:3: error: invalid preprocessing directive #d
   55 | # d[i]で、頂点iにおける保有銀貨数に応じたコストが入ったリストを呼び出せる
      |   ^
main.c:56:3: error: invalid preprocessing directive #\U000030ea\U000030b9\U000030c8\U0000306e\U00004e2d\U00003067
   56 | # リストの中で、一番小さいコストのやつを呼び出せば、その頂点に行ける最小コストと同値である
      |   ^~~~~~~~~~~~