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: Wrong Answer

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

n, m, s = map(int, input().split())
if s >= 2500:
    s = 2499
edges = []
for _ in range(m):
    from_, to, cost, time = map(int, input().split())
    edges.append([from_-1, to-1, cost, time])

banks = []
for city in range(n):
    coin, time = map(int, input().split())
    banks.append([coin, time])

modified_edges_from = [0]
modified_edges_to = [s]
modified_edge_time = [0]


def add_modified_edge(from_, to, time):
    modified_edges_from.append(from_)
    modified_edges_to.append(to)
    modified_edge_time.append(time)


for city, bank in enumerate(banks):
    city_0_coin = city * 2500
    city_maxim_coin = city_0_coin + 2499

    coin, time = bank
    from_ = city_0_coin
    if city == 0:
        from_ = s
    while from_ < city_maxim_coin:
        to = min(from_ + coin, city_maxim_coin)
        add_modified_edge(from_, to, time)
        from_ = to


def expand_edge(from_, to, cost, time):
    with_0_coin_from = from_ * 2500
    with_maxim_coin_from = with_0_coin_from + 2499
    with_0_coin_to = to * 2500
    with_maxim_coin_to = with_0_coin_to + 2499
    for with_coin_from in range(with_maxim_coin_from, with_0_coin_from+cost-1, -1):
        coin = with_coin_from % 2500 - cost
        with_coin_to = with_0_coin_to + coin
        add_modified_edge(with_coin_from, with_coin_to, time)

    for with_coin_to in range(with_maxim_coin_to, with_0_coin_to+cost-1, -1):
        coin = with_coin_to % 2500 - cost
        with_coin_from = with_0_coin_from + coin
        add_modified_edge(with_coin_to, with_coin_from, time)


for natural_from, natural_to, cost, time in edges:
    expand_edge(natural_from, natural_to, cost, time)

csr = csr_matrix((modified_edge_time, (modified_edges_from, modified_edges_to)), (n*2500, n*2500))
results = dijkstra(csr, indices=0)
second_city = 2500
last_city = 2500 * (n-1)
for to_city in range(second_city, last_city+1, 2500):
    print(int(min(results[to_city:to_city+2499])))

Submission status: Wrong Answer

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

n, m, s = map(int, input().split())
if s >= 2500:
    s = 2499
edges = []
for _ in range(m):
    from_, to, cost, time = map(int, input().split())
    edges.append([from_-1, to-1, cost, time])

banks = []
for city in range(n):
    coin, time = map(int, input().split())
    banks.append([coin, time])

modified_edges_from = [0]
modified_edges_to = [s]
modified_edge_time = [0]


def add_modified_edge(from_, to, time):
    modified_edges_from.append(from_)
    modified_edges_to.append(to)
    modified_edge_time.append(time)


for city, bank in enumerate(banks):
    city_0_coin = city * 2500
    city_maxim_coin = city_0_coin + 2499

    coin, time = bank
    from_ = city_0_coin
    if city == 0:
        from_ = s
    while from_ < city_maxim_coin:
        to = min(from_ + coin, city_maxim_coin)
        add_modified_edge(from_, to, time)
        from_ = to


def expand_edge(from_, to, cost, time):
    with_0_coin_from = from_ * 2500
    with_maxim_coin_from = with_0_coin_from + 2499
    with_0_coin_to = to * 2500
    with_maxim_coin_to = with_0_coin_to + 2499
    for with_coin_from in range(with_maxim_coin_from, with_0_coin_from+cost-1, -1):
        coin = with_coin_from % 2500 - cost
        with_coin_to = with_0_coin_to + coin
        add_modified_edge(with_coin_from, with_coin_to, time)

    for with_coin_to in range(with_maxim_coin_to, with_0_coin_to+cost-1, -1):
        coin = with_coin_to % 2500 - cost
        with_coin_from = with_0_coin_from + coin
        add_modified_edge(with_coin_to, with_coin_from, time)


for natural_from, natural_to, cost, time in edges:
    expand_edge(natural_from, natural_to, cost, time)

csr = coo_matrix((modified_edge_time, (modified_edges_from, modified_edges_to)), (n*2500, n*2500)).tocsr()
results = dijkstra(csr, indices=0)
second_city = 2500
last_city = 2500 * (n-1)
for to_city in range(second_city, last_city+1, 2500):
    print(int(min(results[to_city:to_city+2499])))

Submission status: Wrong Answer

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

n,m,s = map(int,input().split())
if s >= 2500:
    s = 2499

dg = 2500
INF = 10**12

dist = [INF]*(n*dg)

edge = [[] for i in range(n)]
a = [0]*m
b = [0]*m

for i in range(m):
    u,v,aa,bb = map(int,input().split())
    a[i] = aa
    b[i] = bb
    edge[u-1].append( (i,v-1))
    edge[v-1].append( (i,u-1) )


c = [0]*n
d = [0]*n

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

tank = [(0,s)]
nonused = [True]*(n*dg)


while tank:
    tim,fr = heapq.heappop(tank)
    if dist[fr] != INF:
        continue
    dist[fr] = tim
    pos,mon = divmod(fr,dg)

    for idx,go in edge[pos]:
        if mon >= a[idx] and dist[go*dg + mon-a[idx]] == INF:
            heapq.heappush(tank,(tim + b[idx] ,go*dg + mon-a[idx] ))
    if mon + c[pos] < dg and dist[fr + c[pos]] == INF:
        heapq.heappush(tank,(tim + d[pos] ,fr + c[pos] ))

for i in range(1,n):
    res = INF
    for j in range(dg):
        if dist[i*dg+j] < res:
            res = dist[i*dg+j]
    print(res)

Submission status: Wrong Answer

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

n, m, s = map(int, input().split())
if s > 2500:
    s = 2499
edges = []
for _ in range(m):
    from_, to, cost, time = map(int, input().split())
    edges.append([from_-1, to-1, cost, time])

banks = []
for city in range(n):
    coin, time = map(int, input().split())
    banks.append([coin, time])

modified_edges_from = [0]
modified_edges_to = [s]
modified_edge_time = [0]


def add_modified_edge(from_, to, time):
    modified_edges_from.append(from_)
    modified_edges_to.append(to)
    modified_edge_time.append(time)


for city, bank in enumerate(banks):
    city_0_coin = city * 2500
    city_maxim_coin = city_0_coin + 2499

    for from_ in range(city_maxim_coin, city_0_coin, -1):
        add_modified_edge(from_, from_-1, 0)

    coin, time = bank
    from_ = city_0_coin
    if city == 0:
        from_ = s
    while from_ < city_maxim_coin:
        to = min(from_ + coin, city_maxim_coin)
        add_modified_edge(from_, to, time)
        from_ = to


def expand_edge(from_, to, cost, time):
    with_0_coin_from = from_ * 2500
    with_maxim_coin_from = with_0_coin_from + 2499
    with_0_coin_to = to * 2500
    with_maxim_coin_to = with_0_coin_to + 2499
    for with_coin_from in range(with_maxim_coin_from, with_0_coin_from+cost-1, -1):
        coin = with_coin_from % 2500 - cost
        with_coin_to = with_0_coin_to + coin
        add_modified_edge(with_coin_from, with_coin_to, time)

    for with_coin_to in range(with_maxim_coin_to, with_0_coin_to+cost-1, -1):
        coin = with_coin_to % 2500 - cost
        with_coin_from = with_0_coin_from + coin
        add_modified_edge(with_coin_to, with_coin_from, time)


for natural_from, natural_to, cost, time in edges:
    expand_edge(natural_from, natural_to, cost, time)

csr = coo_matrix((modified_edge_time, (modified_edges_from, modified_edges_to)), (n*2500, n*2500)).tocsr()
results = dijkstra(csr, indices=0).astype(int)
first_city = 2500
last_city = 2500 * (n-1)
for to_city in range(first_city, last_city+1, 2500):
    print(results[to_city])

Submission status: Wrong Answer

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

n, m, s = map(int, input().split())
if s > 2500:
    s = 2499
edges = []
for _ in range(m):
    from_, to, cost, time = map(int, input().split())
    edges.append([from_-1, to-1, cost, time])

banks = []
for city in range(n):
    coin, time = map(int, input().split())
    banks.append([coin, time])

modified_edges_from = [0]
modified_edges_to = [s]
modified_edge_time = [0]


def add_modified_edge(from_, to, time):
    modified_edges_from.append(from_)
    modified_edges_to.append(to)
    modified_edge_time.append(time)


for city, bank in enumerate(banks):
    city_0_coin = city * 2500
    city_maxim_coin = city_0_coin + 2499

    for from_ in range(city_maxim_coin, city_0_coin, -1):
        add_modified_edge(from_, from_-1, 0)

    coin, time = bank
    from_ = city_0_coin
    if city == 0:
        from_ = s
    while from_ < city_maxim_coin:
        to = min(from_ + coin, city_maxim_coin)
        add_modified_edge(from_, to, time)
        from_ = to


def expand_edge(from_, to, cost, time):
    with_0_coin_from = from_ * 2500
    with_maxim_coin_from = with_0_coin_from + 2499
    with_0_coin_to = to * 2500
    with_maxim_coin_to = with_0_coin_to + 2499
    for with_coin_from in range(with_maxim_coin_from, with_0_coin_from+cost-1, -1):
        coin = with_coin_from % 2500 - cost
        with_coin_to = with_0_coin_to + coin
        add_modified_edge(with_coin_from, with_coin_to, time)

    for with_coin_to in range(with_maxim_coin_to, with_0_coin_to+cost-1, -1):
        coin = with_coin_to % 2500 - cost
        with_coin_from = with_0_coin_from + coin
        add_modified_edge(with_coin_to, with_coin_from, time)


for natural_from, natural_to, cost, time in edges:
    expand_edge(natural_from, natural_to, cost, time)

csr = coo_matrix((modified_edge_time, (modified_edges_from, modified_edges_to)), (n*2500, n*2500)).tocsr()
results = dijkstra(csr, indices=0)
first_city = 2500
last_city = 2500 * (n-1)
for to_city in range(first_city, last_city+1, 2500):
    print(int(results[to_city]))

Submission status: Wrong Answer

Solution code:
N, M, S = list(map(int, input().split()))
UVAB = [list(map(int, input().split())) for _ in range(M)]
CD = [list(map(int, input().split())) for _ in range(N)]

DL = [[[0] * 2 for _ in range(N)] for _ in range(N)]
for u, v, a, b in UVAB:
  u -= 1
  v -= 1
  DL[u][v] = a, b
  DL[v][u] = a, b

DB = [[[0] * 2 for _ in range(N)] for _ in range(N)] #[時間、金]
DB[0][0][1] = S 

D = [0] * N
D[0] = 1

s = 0
for i in range(N):
  for _ in range(N):
    mid = 10 ** 30 #最短時間
    mim = 0 #最短時間のとこの残金
    mig = s #最短時間のとこのゴール
    for g in range(N): #ゴール
      if DB[s][g][0] != 0 or s == g: continue #すでに調べていたら終わり
      for p in range(N): #中間ポイント
        if DB[s][p][0] == 0 and p != s: continue #中間ポイントに行けなければ終わり
        a, b = DL[p][g]
        if a == 0: continue #ゴールに行けなければ終わり
        sgd = DB[s][p][0] + b #ゴールまでの時間
        m = DB[s][p][1] - a #残金 
        if m < 0: #金が足りない分稼ぐ
          mt = abs(m) // CD[s][0]
          m += mt * CD[s][0]
          sgd += mt * CD[s][1]
          if m < 0:
            m += CD[s][0]
            sgd += CD[s][1]
        if mid == sgd:
          if mim < m:
            mid = sgd
            mig = g
            mim = m
        elif mid > sgd:
          mid = sgd
          mig = g
          mim = m
    if mig != s:
      DB[s][mig] = [mid, mim]

  mid = 10 ** 30
  mix = 0
  for j in range(N):
    if D[j] == 0: continue
    for k in range(N):
      if D[k] == 1 or k == s: continue
      if mid == DB[j][k][0]:
        if mim < DB[j][k][1]:
          mid, mim, mix = DB[j][k][0], DB[j][k][1], k
      elif mid > DB[j][k][0]:
        mid, mim, mix = DB[j][k][0], DB[j][k][1], k
  s = mix
  D[s] = 1
  if s != 0:
    DB[s][s] = [mid, mim]

for g in range(1, N):
  mi = 10 ** 30
  for s in range(N):
    if DB[s][g][0] == 0: continue
    mi = min(mi, DB[s][g][0])
  print(mi)
for i in range(1, N):
  if DB[i][i][0] == 0:
    x = 1 / 0

Submission status: Wrong Answer

Solution code:
N, M, S = list(map(int, input().split()))
UVAB = [list(map(int, input().split())) for _ in range(M)]
CD = [list(map(int, input().split())) for _ in range(N)]

DL = [[[0] * 2 for _ in range(N)] for _ in range(N)]
for u, v, a, b in UVAB:
  u -= 1
  v -= 1
  DL[u][v] = a, b
  DL[v][u] = a, b

DB = [[[0] * 2 for _ in range(N)] for _ in range(N)] #[時間、金]
DB[0][0][1] = S 

D = [0] * N
D[0] = 1

s = 0
for i in range(N):
  for _ in range(N):
    mid = 10 ** 30 #最短時間
    mim = 0 #最短時間のとこの残金
    mig = s #最短時間のとこのゴール
    for g in range(N): #ゴール
      if DB[s][g][0] != 0 or s == g: continue #すでに調べていたら終わり
      for p in range(N): #中間ポイント
        if DB[s][p][0] == 0 and p != s: continue #中間ポイントに行けなければ終わり
        a, b = DL[p][g]
        if a == 0: continue #ゴールに行けなければ終わり
        sgd = DB[s][p][0] + b #ゴールまでの時間
        m = DB[s][p][1] - a #残金 
        if m < 0: #金が足りない分稼ぐ
          mt = abs(m) // CD[s][0]
          m += mt * CD[s][0]
          sgd += mt * CD[s][1]
          if m < 0:
            m += CD[s][0]
            sgd += CD[s][1]
        if mid == sgd:
          if mim < m:
            mid = sgd
            mig = g
            mim = m
        elif mid > sgd:
          mid = sgd
          mig = g
          mim = m
    if mig != s:
      DB[s][mig] = [mid, mim]

  mid = 10 ** 30
  mix = 0
  for j in range(N):
    if D[j] == 0: continue
    for k in range(N):
      if D[k] == 1 or k == s: continue
      if mid == DB[j][k][0]:
        if mim < DB[j][k][1]:
          mid, mim, mix = DB[j][k][0], DB[j][k][1], k
      elif mid > DB[j][k][0]:
        mid, mim, mix = DB[j][k][0], DB[j][k][1], k
  s = mix
  D[s] = 1
  if s != 0:
    DB[s][s] = [mid, mim]

for g in range(1, N):
  mi = 10 ** 30
  for s in range(N):
    if DB[s][g][0] == 0: continue
    mi = min(mi, DB[s][g][0])
  print(mi)

Submission status: Wrong Answer

Solution code:
N, M, S = list(map(int, input().split()))
UVAB = [list(map(int, input().split())) for _ in range(M)]
CD = [list(map(int, input().split())) for _ in range(N)]

DL = [[[0] * 2 for _ in range(N)] for _ in range(N)]
for u, v, a, b in UVAB:
  u -= 1
  v -= 1
  DL[u][v] = a, b
  DL[v][u] = a, b

DB = [[[0] * 2 for _ in range(N)] for _ in range(N)] #[時間、金]
DB[0][0][1] = S 

D = [0] * N
D[0] = 1

s = 0
for i in range(N):
  for _ in range(N):
    mid = 10 ** 30 #最短時間
    mim = 0 #最短時間のとこの残金
    mig = s #最短時間のとこのゴール
    for g in range(N): #ゴール
      if DB[s][g][0] != 0 or s == g: continue #すでに調べていたら終わり
      for p in range(N): #中間ポイント
        if DB[s][p][0] == 0 and p != s: continue #中間ポイントに行けなければ終わり
        a, b = DL[p][g]
        if a == 0: continue #ゴールに行けなければ終わり
        sgd = DB[s][p][0] + b #ゴールまでの時間
        m = DB[s][p][1] - a #残金 
        if m < 0: #金が足りない分稼ぐ
          mt = abs(m) // CD[s][0]
          m += mt * CD[s][0]
          sgd += mt * CD[s][1]
          if m < 0:
            m += CD[s][0]
            sgd += CD[s][1]
        if mid > sgd:
          mid = sgd
          mig = g
          mim = m
    if mig != s:
      DB[s][mig] = [mid, mim]

  mid = 10 ** 30
  mix = 0
  for j in range(N):
    if D[j] == 0: continue
    for k in range(N):
      if D[k] == 1 or k == s: continue
      if mid == DB[j][k][0]:
        if mim < DB[j][k][1]:
          mid, mim, mix = DB[j][k][0], DB[j][k][1], k
      elif mid > DB[j][k][0]:
        mid, mim, mix = DB[j][k][0], DB[j][k][1], k
  s = mix
  D[s] = 1
  if s != 0:
    DB[s][s] = [mid, mim]

for g in range(1, N):
  mi = 10 ** 30
  for s in range(N):
    if DB[s][g][0] == 0: continue
    mi = min(mi, DB[s][g][0])
  print(mi)

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict
from heapq import heappush, heappop, heapify
input = sys.stdin.readline

INF = 10**12
n, m, s = map(int, input().split())
edges = defaultdict(lambda: defaultdict(lambda: [INF, INF]))
cd = []
max_a = 0

for i in range(m):
    u, v, a, b = map(int, input().split())
    max_a = max(max_a, a)
    edges[u-1][v-1] = [a, b]
    edges[v-1][u-1] = [a, b]

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

# 解答ACする
# Dijakstraの状態を(頂点、所持している銀貨の枚数, cost)で持つ
# SIZE = max_a * n + 1
SIZE = 2550
if s > SIZE:
    s = SIZE - 1
nodes = [[INF for _ in range(SIZE)] for _ in range(n)]
nodes[0][s] = 0

def dijakstra():
    goals = set({0})
    que = [(0, 0, s)]
    heapify(que)
    while len(que) > 0:
        # print(que[:3])
        cost, num, silver = heappop(que)
        # print(silver)
        if nodes[num][silver] < cost:
            continue
        # print(cost, num, silver)
        if num not in goals:
            goals.add(num)
        if len(goals) == n:
            break
        c, d = cd[num]
        for v in edges[num].keys():
            a, b = edges[num][v]
            times = -1
            to = silver - a
            while to < SIZE:
                times += 1
                plus = times * c
                to = silver + plus - a
                if to < 0:
                    continue
                if to >= SIZE:
                    break
                if nodes[v][to] > cost + b + d * times:
                    nodes[v][to] = cost + b + d * times
                    heappush(que, (cost + b + d * times, v, to))
dijakstra()
for i in range(1, n):
    print(min(nodes[i]))

Submission status: Wrong Answer

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

INF = 10**12
n, m, s = map(int, input().split())
edges = defaultdict(lambda: defaultdict(lambda: [INF, INF]))
cd = []
max_a = 0

for i in range(m):
    u, v, a, b = map(int, input().split())
    max_a = max(max_a, a)
    edges[u-1][v-1] = [a, b]
    edges[v-1][u-1] = [a, b]

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

# 解答ACする
# Dijakstraの状態を(頂点、所持している銀貨の枚数, cost)で持つ
# SIZE = max_a * n + 1
SIZE = 2550
if s > SIZE:
    s = SIZE - 1
nodes = [[INF for _ in range(SIZE)] for _ in range(n)]
nodes[0][s-1] = 0

def dijakstra():
    goals = set({0})
    que = [(0, 0, s)]
    heapify(que)
    while len(que) > 0:
        # print(que[:3])
        cost, num, silver = heappop(que)
        # print(silver)
        if nodes[num][silver] < cost:
            continue
        # print(cost, num, silver)
        if num not in goals:
            goals.add(num)
        if len(goals) == n:
            break
        c, d = cd[num]
        for v in edges[num].keys():
            a, b = edges[num][v]
            times = -1
            to = silver - a
            while to < SIZE:
                times += 1
                plus = times * c
                to = silver + plus - a
                if to < 0:
                    continue
                if to >= SIZE:
                    break
                if nodes[v][to] > cost + b + d * times:
                    nodes[v][to] = cost + b + d * times
                    heappush(que, (cost + b + d * times, v, to))
dijakstra()
for i in range(1, n):
    print(min(nodes[i]))

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict
from heapq import heappush, heappop, heapify
input = sys.stdin.readline

INF = 10**12
n, m, s = map(int, input().split())
edges = defaultdict(lambda: defaultdict(lambda: [INF, INF]))
cd = []
max_a = 0

for i in range(m):
    u, v, a, b = map(int, input().split())
    max_a = max(max_a, a)
    edges[u-1][v-1] = [a, b]
    edges[v-1][u-1] = [a, b]

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

# 解答ACする
# Dijakstraの状態を(頂点、所持している銀貨の枚数, cost)で持つ
# SIZE = max_a * n + 1
SIZE = 2550
if s > SIZE:
    s = SIZE - 1
nodes = [[INF for _ in range(SIZE)] for _ in range(n)]
nodes[0][s-1] = 0

def dijakstra():
    goals = set({0})
    que = [(0, 0, s)]
    heapify(que)
    while len(que) > 0:
        # print(que[:3])
        cost, num, silver = heappop(que)
        # print(silver)
        if nodes[num][silver] < cost:
            continue
        # print(cost, num, silver)
        if num not in goals:
            goals.add(num)
        if len(goals) == n:
            break
        c, d = cd[num]
        for v in edges[num].keys():
            a, b = edges[num][v]
            times = -1
            to = silver - a
            while to < SIZE:
                times += 1
                plus = times * c
                to = silver + plus - a
                if to < 0:
                    continue
                if to >= SIZE:
                    break
                if nodes[v][to] > cost + b + d * times:
                    nodes[v][to] = cost + b + d * times
                    heappush(que, (cost + b + d * times, v, to))
dijakstra()
for i in range(1, n):
    print(min(nodes[i]))

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict
from heapq import heappush, heappop, heapify
input = sys.stdin.readline

INF = 10**12
n, m, s = map(int, input().split())
edges = defaultdict(lambda: defaultdict(lambda: [INF, INF]))
cd = []
max_a = 0

for i in range(m):
    u, v, a, b = map(int, input().split())
    max_a = max(max_a, a)
    edges[u-1][v-1] = [a, b]
    edges[v-1][u-1] = [a, b]

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

# 解答ACする
# Dijakstraの状態を(頂点、所持している銀貨の枚数, cost)で持つ
# SIZE = max_a * n + 1
SIZE = 2550
if s > SIZE:
    s = SIZE
nodes = [[INF for _ in range(SIZE)] for _ in range(n)]
nodes[0][s-1] = 0

def dijakstra():
    goals = set({0})
    que = [(0, 0, s)]
    heapify(que)
    while len(que) > 0:
        # print(que[:3])
        cost, num, silver = heappop(que)
        # print(cost, num, silver)
        if num not in goals:
            goals.add(num)
        if len(goals) == n:
            break
        c, d = cd[num]
        for v in edges[num].keys():
            a, b = edges[num][v]
            times = -1
            to = silver - a
            while to < SIZE:
                times += 1
                plus = times * c
                to = silver + plus - a
                if to < 0:
                    continue
                if to >= SIZE:
                    break
                if nodes[v][to] > cost + b + d * times:
                    nodes[v][to] = cost + b + d * times
                    heappush(que, (cost + b + d * times, v, to))
dijakstra()
for i in range(1, n):
    print(min(nodes[i]))

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict
from heapq import heappush, heappop, heapify
input = sys.stdin.readline

INF = 10**12
n, m, s = map(int, input().split())
edges = defaultdict(lambda: defaultdict(lambda: [INF, INF]))
cd = []
max_a = 0

for i in range(m):
    u, v, a, b = map(int, input().split())
    max_a = max(max_a, a)
    edges[u-1][v-1] = [a, b]
    edges[v-1][u-1] = [a, b]

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

# 解答ACする
# Dijakstraの状態を(頂点、所持している銀貨の枚数, cost)で持つ
# SIZE = max_a * n + 1
SIZE = 2550
if s > SIZE:
    s = SIZE
nodes = [[INF for _ in range(SIZE)] for _ in range(n)]
nodes[0][s-1] = 0

def dijakstra():
    goal = 0
    que = [(0, 0, s)]
    heapify(que)
    while len(que) > 0:
        # print(que[:3])
        cost, num, silver = heappop(que)
        # print(cost, num, silver)
        if num == goal:
            if goal == n-1:
                break
            else:
                goal += 1
        c, d = cd[num]
        for v in edges[num].keys():
            a, b = edges[num][v]
            times = -1
            to = silver - a
            while to < SIZE:
                times += 1
                plus = times * c
                to = silver + plus - a
                if to < 0:
                    continue
                if to >= SIZE:
                    break
                if nodes[v][to] > cost + b + d * times:
                    nodes[v][to] = cost + b + d * times
                    heappush(que, (cost + b + d * times, v, to))
dijakstra()
for i in range(1, n):
    print(min(nodes[i]))

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict
from heapq import heappush, heappop, heapify
input = sys.stdin.readline

INF = 10**12
n, m, s = map(int, input().split())
edges = defaultdict(lambda: defaultdict(lambda: [INF, INF]))
cd = []
max_a = 0

for i in range(m):
    u, v, a, b = map(int, input().split())
    max_a = max(max_a, a)
    edges[u-1][v-1] = [a, b]
    edges[v-1][u-1] = [a, b]

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

# 解答ACする
# Dijakstraの状態を(頂点、所持している銀貨の枚数, cost)で持つ
# SIZE = max_a * n + 1
SIZE = 2501
if s > SIZE:
    s = SIZE
nodes = [[INF for _ in range(SIZE)] for _ in range(n)]
nodes[0][s-1] = 0

def dijakstra():
    goal = 0
    que = [(0, 0, s)]
    heapify(que)
    while len(que) > 0:
        # print(que[:3])
        cost, num, silver = heappop(que)
        # print(cost, num, silver)
        if num == goal:
            if goal == n-1:
                return
            else:
                goal += 1
        c, d = cd[num]
        for v in edges[num].keys():
            a, b = edges[num][v]
            times = -1
            to = silver - a
            while to < SIZE:
                times += 1
                plus = times * c
                to = silver + plus - a
                if to < 0:
                    continue
                if to >= SIZE:
                    break
                if nodes[v][to] > cost + b + d * times:
                    nodes[v][to] = cost + b + d * times
                    heappush(que, (cost + b + d * times, v, to))
dijakstra()
for i in range(1, n):
    print(min(nodes[i]))

Submission status: Wrong Answer

Solution code:
MOD = 10 ** 9 + 7
INF = 10 ** 13
import sys
sys.setrecursionlimit(100000000)
dy = (-1,0,1,0)
dx = (0,1,0,-1)
from collections import deque

def main():
    n,m,s = map(int,input().split())
    G = [[] for _ in range(n)]
    MAXS = 0
    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))
        MAXS = max(MAXS,a)
    
    Silver = [tuple(map(int,input().split())) for _ in range(n)]
    MAXS *= n - 1
    dp = [[INF]* (MAXS+1) for _ in range(n)]
    for i in range(min(s + 1,MAXS)):
        dp[0][i] = 0
    c,d = Silver[0]
    for i in range(min(s + 1,MAXS),MAXS):
        dp[0][i] = d*((i - s + c - 1)//c)
    
    q = deque([0])
    while q:
        i = q.popleft()
        c,d = Silver[i]
        for e,a,b in G[i]:
            flag = False
            for s in range(MAXS - 1,-1,-1):
                if s - a >= 0:
                    if dp[e][s - a] > dp[i][s] + b:
                        dp[e][s - a] = dp[i][s] + b
                        flag = True
                else:
                    k = (a - s + c - 1)//c
                    while s - a + k*c <= MAXS:
                        if dp[e][s - a + k*c] > dp[i][s] + b + k*d:
                            dp[e][s - a + k*c] = dp[i][s] + b + k*d
                            flag = True
                        k += 1
            if flag:
                q.append(e)
    #print(dp)
    for i in range(1,n):
        ans = min(dp[i])
        print(ans)
if __name__ == '__main__':
    main()