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 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)
for to_city in range(2500, len(results), 2500):
    print(int(results[to_city]))

Submission status: Wrong Answer

Solution code:
import heapq
inf = 10**20
h = 2500
n, m, s = map(int, input().split())
# A[i][j]=iからjへのコスト
A = [[inf for j in range(n)] for i in range(n)]
# B[i][j]=iからjへの時間
B = [[inf for j in range(n)] for i in range(n)]
for _ in range(m):
    u, v, a, b = map(int, input().split())
    A[u-1][v-1] = a
    A[v-1][u-1] = a
    B[u-1][v-1] = b
    B[v-1][u-1] = b
CD = [tuple(map(int, input().split())) for i in range(n)]
C = [c for c, d in CD]
D = [d for c, d in CD]
# G[i,x][j,y]=状態(i,x)から(j,y)に変わるのにかかる時間
G = {(i, x): {} for i in range(n) for x in range(h)}
for i in range(n):
    for j in range(n):
        for x in range(h):
            if i == j:
                G[i, x][i, x] = 0
                if x-1 >= 0:
                    G[i, x][i, x-1] = 0
                if x+C[i] < h:
                    G[i, x][i, x+C[i]] = D[i]
            elif x >= A[i][j]:
                G[i, x][j, x-A[i][j]] = B[i][j]
# T[i,x]=状態(0,s)から(i,x)にかかる時間
T = {(i, x): inf for i in range(n) for x in range(h)}
T[0, s] = 0
Q = [(T[i, x], (i, x)) for i in range(n) for x in range(h)]
heapq.heapify(Q)
while Q:
    _, (i, x) = heapq.heappop(Q)
    for j, y in G[i, x].keys():
        if T[i, x]+G[i, x][j, y] < T[j, y]:
            T[j, y] = T[i, x] + G[i, x][j, y]
            heapq.heappush(Q, (T[j, y], (j, y)))
for i in range(1, n):
    print(T[i, 0])

Submission status: Wrong Answer

Solution code:
import heapq

WALLET_MAX = 2501
TIME_MAX = 10 ** 15

N, M, S = map(int, input().split())
fare_adj = [[WALLET_MAX] * N for _ in range(N)]
time_adj = [[TIME_MAX] * N for _ in range(N)]
fare_max = 0
for i in range(M):
    u, v, a, b = map(int, input().split())
    u -= 1
    v -= 1
    fare_adj[u][v] = fare_adj[v][u] = a
    time_adj[u][v] = time_adj[v][u] = b
    fare_max = max(fare_max, a)

exchanges = []
for i in range(N):
    # g-s rate, waiting duration
    c, d = map(int, input().split())
    exchanges.append((c, d))


WALLET_MAX = fare_max * (N - 1)
mintime = [[TIME_MAX] * (WALLET_MAX + 1) for _ in range(N)]


def search():
    q = [(0, 0, min(S, WALLET_MAX), N - 1)]
    while q:
        t, loc, silvers, maxsteps = heapq.heappop(q)
        if t >= mintime[loc][silvers]:
            continue
        mintime[loc][silvers] = t
        max_silvers = fare_max * maxsteps
        while silvers <= max_silvers:
            for nloc in range(N):
                if nloc == loc:
                    continue
                ntime = t + time_adj[loc][nloc]
                nsilvers = min(silvers - fare_adj[loc][nloc], max_silvers)
                if nsilvers >= 0 and ntime < mintime[nloc][nsilvers]:
                    heapq.heappush(q, (ntime, nloc, nsilvers, maxsteps - 1))
            rate, wait = exchanges[loc]
            assert rate > 0 and wait > 0
            t += wait
            silvers += rate


search()
for t in range(1, N):
    print(min(mintime[t]))

Submission status: Wrong Answer

Solution code:
import heapq

COST_MAX = 2501
TIME_MAX = 10 ** 15

N, M, S = map(int, input().split())
fare_adj = [[COST_MAX] * N for _ in range(N)]
time_adj = [[TIME_MAX] * N for _ in range(N)]
fare_max = 0
fare_sum = 0
for i in range(M):
    u, v, a, b = map(int, input().split())
    u -= 1
    v -= 1
    fare_adj[u][v] = fare_adj[v][u] = a
    time_adj[u][v] = time_adj[v][u] = b
    fare_sum += a
    fare_max = max(fare_max, a)

exchanges = []
for i in range(N):
    # g-s rate, waiting duration
    c, d = map(int, input().split())
    exchanges.append((c, d))


mintime = [[TIME_MAX] * (fare_sum + 1) for _ in range(N)]


def search():
    q = [(0, 0, min(S, fare_sum), N - 1)]
    while q:
        t, loc, silvers, rest = heapq.heappop(q)
        if t >= mintime[loc][silvers]:
            continue
        mintime[loc][silvers] = t
        while silvers <= fare_sum:
            for nloc in range(N):
                if nloc == loc:
                    continue
                ntime = t + time_adj[loc][nloc]
                nsilvers = silvers - fare_adj[loc][nloc]
                nsilvers = min(nsilvers, fare_max * rest)
                if nsilvers >= 0 and ntime < mintime[nloc][nsilvers]:
                    heapq.heappush(q, (ntime, nloc, nsilvers, rest - 1))
            rate, wait = exchanges[loc]
            t += wait
            silvers += rate


search()
for t in range(1, N):
    print(min(mintime[t]))

Submission status: Wrong Answer

Solution code:
def dijkstra(v, G):
    import heapq

    ret = [10 ** 12] * len(G)
    ret[v] = 0
    q = [(ret[i], i) for i in range(len(G))]
    heapq.heapify(q)

    while len(q):
        tmpr, u = heapq.heappop(q)
        if tmpr == ret[u]:
            for w, l in G[u]:
                if ret[w] > ret[u] + l:
                    ret[w] = ret[u] + l
                    heapq.heappush(q, (ret[w], w))
    return ret


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

maxA = max([a for u, v, a, b in UVAB])
Q = maxA * (N - 1) + 1
G = [[] for _ in range(Q * N)]

for u, v, a, b in UVAB:
    for q in range(Q):
        if q >= a:
            G[Q * (u - 1) + q].append((Q * (v - 1) + q - a, b))
            G[Q * (v - 1) + q].append((Q * (u - 1) + q - a, b))

for n, (c, d) in enumerate(CD):
    for q in range(Q):
        G[Q * n + q].append((Q * n + min(Q - 1, c + q), d))

ans = dijkstra(min(S, Q - 1), G)
for n in range(1, N):
    print(min(ans[Q * n:Q * (n + 1)]))

Submission status: Wrong Answer

Solution code:
def dijkstra(v, G):
    import heapq

    ret = [10 ** 10] * len(G)
    ret[v] = 0
    q = [(ret[i], i) for i in range(len(G))]
    heapq.heapify(q)

    while len(q):
        tmpr, u = heapq.heappop(q)
        if tmpr == ret[u]:
            for w, l in G[u]:
                if ret[w] > ret[u] + l:
                    ret[w] = ret[u] + l
                    heapq.heappush(q, (ret[w], w))
    return ret


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

maxA = max([a for u, v, a, b in UVAB])
Q = maxA * (N - 1) + 1
G = [[] for _ in range(Q * N)]

for u, v, a, b in UVAB:
    for q in range(Q):
        if q >= a:
            G[Q * (u - 1) + q].append((Q * (v - 1) + q - a, b))
            G[Q * (v - 1) + q].append((Q * (u - 1) + q - a, b))

for n, (c, d) in enumerate(CD):
    for q in range(Q):
        G[Q * n + q].append((Q * n + min(Q - 1, c + q), d))

ans = dijkstra(min(S, Q - 1), G)
for n in range(1, N):
    print(min(ans[Q * n:Q * (n + 1)]))

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop

infi = 10 ** 20
n, m, s = map(int, input().split())

s = min(s, 2500)

edges = [[] for _ in range(51 * 2501 + 1)]
# edge:1-50, max silver=0-2500

for _ in range(m):
    u, v, a, b = map(int, input().split())
    for i in range(a, 51):
        edges[v + 50 * i].append((b, u + 50 * (i - a)))
        edges[u + 50 * i].append((b, v + 50 * (i - a)))


for edge_num in range(1, n + 1):
    c, d = map(int, input().split())
    for i in range(51):
        if edge_num + (i + c) * 50 <= 51 * 2501:
            edges[edge_num + i * 50].append((d, edge_num + (i + c) * 50))
start = 1 + 50 * s


def dijkstra(edges, start):
    time = [infi] * (51 * 2501 + 1)
    used = [False] * (51 * 2501 + 1)
    # time[i][j] 頂点i, 銀貨jのときの時間
    time[start] = 0
    edgelist = []
    heappush(edgelist, (0, start))
    while edgelist:
        nowtime, nowedge = heappop(edgelist)
        if used[nowedge] is True:
            continue
        used[nowedge] = True
        time[nowedge] = nowtime
        for vt, v in edges[nowedge]:
            if used[v] is True:
                continue
            newtime = nowtime + vt
            heappush(edgelist, (newtime, v))
    return time


time = dijkstra(edges, start)

ans = [infi] * (51)
for i in range(1, 51 * 2501 + 1):
    temp = time[i]
    a = i % 50
    if a == 0:
        a += 50
    ans[a] = min(temp, ans[a])

print(*ans[2 : (n + 1)], sep="\n")

Submission status: Wrong Answer

Solution code:
import collections
import heapq


class Dijkstra:
    def __init__(self):
        self.e = collections.defaultdict(list)

    def add(self, u, v, d):
        self.e[u].append([v, d])
        self.e[v].append([u, d])

    def delete(self, u, v):
        self.e[u] = [_ for _ in self.e[u] if _[0] != v]
        self.e[v] = [_ for _ in self.e[v] if _[0] != u]

    def search(self, s):
        """
        :param s: 始点
        :return: 始点から各点までの最短経路
        """
        d = collections.defaultdict(lambda: float('inf'))
        d[s] = 0
        q = []
        heapq.heappush(q, (0, s))
        v = collections.defaultdict(bool)
        while len(q):
            k, u = heapq.heappop(q)
            if v[u]:
                continue
            v[u] = True

            for uv, ud in self.e[u]:
                if v[uv]:
                    continue
                vd = k + ud
                if d[uv] > vd:
                    d[uv] = vd
                    heapq.heappush(q, (vd, uv))

        return d

N,M,S = map(int,input().split())
train = [list(map(int,input().split())) for i in range(M)]
change = [list(map(int,input().split())) for i in range(N)]

G = Dijkstra()

for u,v,a,b in train:
    for i in range(a,2501):
        G.e[(u,i)].append([(v,i-a),b])
        G.e[(v,i)].append([(u,i-a),b])
for i in range(1,N+1):
    for j in range(2501-change[i-1][0]):
        G.e[(i,j)].append([(i,j+change[i-1][0]),change[i-1][1]])

A = G.search((1,S))

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

Submission status: Wrong Answer

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 i in range(M)]
cd = [list(map(int, input().split())) for i in range(N)]

max_a = max([x[2] for x in uvab])
num_coins = max_a * M # <= 50 * 100 = 5,000
num_states = N * (num_coins + 1) # <= 50 * 5,001 = 250,050

d = []
row = []
col = []

for u, v, a, b in uvab:
  u -= 1; v -= 1
  i = (num_coins + 1) * u
  j = (num_coins + 1) * v
  for n in range(a, num_coins+1):
    d.extend([b, b])
    row.extend([i+n, j+n])
    col.extend([j+n-a, i+n-a])

for i, _cd in enumerate(cd):
  get, time = _cd
  start = i * (num_coins + 1)
  end = (i + 1) * (num_coins + 1)
  for j in range(start, end):
    if j + get < end:
      d.append(time)
      row.append(j)
      col.append(j + get)
    else:
      break

g = csr_matrix((d, (row, col)), shape=(num_states, num_states))

start_idx = min(S, num_coins)
dist = dijkstra(g, indices=start_idx).astype(int)
ans = []
for i in range(1, N):
  start = i * (num_coins + 1)
  end = (i + 1) * (num_coins + 1)
  _ans = 10 ** 12
  for j in range(start, end):
    _ans = min(_ans, dist[j])
  ans.append(_ans)

print(*ans, sep='\n')

Submission status: Wrong Answer

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 i in range(M)]
cd = [list(map(int, input().split())) for i in range(N)]

max_a = max([x[2] for x in uvab])
num_coins = max_a * M # <= 50 * 100 = 5,000
num_states = N * (num_coins + 1) # <= 50 * 5,001 = 250,050

d = []
row = []
col = []

for u, v, a, b in uvab:
  u -= 1; v -= 1
  i = (num_coins + 1) * u
  j = (num_coins + 1) * v
  for n in range(a, num_coins+1):
    d.extend([b, b])
    row.extend([i+n, j+n])
    col.extend([j+n-a, i+n-a])

for i, _cd in enumerate(cd):
  get, time = _cd
  start = i * (num_coins + 1)
  end = (i + 1) * (num_coins + 1)
  for j in range(start, end):
    if j + get < end:
      d.append(time)
      row.append(j)
      col.append(j + get)
    else:
      break

g = csr_matrix((d, (row, col)), shape=(num_states, num_states))

start_idx = min(S, num_coins)
dist = dijkstra(g, indices=start_idx)
ans = []
for i in range(1, N):
  start = i * (num_coins + 1)
  end = (i + 1) * (num_coins + 1)
  _ans = 10 ** 10
  for j in range(start, end):
    _ans = min(_ans, dist[j])
  ans.append(int(_ans))

print(*ans, sep='\n')

Submission status: Wrong Answer

Solution code:
import heapq
def dijkstra_heap():
    used = [-1] * (2501*n)
    edgelist=[]
    d=[0]*n
    d[0]=1
    f=1
    for i in range(0,2501):
        if 0<=ss+i*cd[0][0]<=2500:
            heapq.heappush(edgelist,[cd[0][1]*i,cd[0][0]*i+ss])
        else:
            break
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        if used[minedge[1]]!=-1:
            continue
        v = minedge[1]
        kai=minedge[0]
        mai=v%2501
        used[v] = kai
        if d[v//2501]==0:
            d[v//2501]=1
            f+=1
            if f==n:
                return used
        for e in edge[v//2501]:
            if mai-e[1]>=0:
                for i in range(2501):
                    sss=mai-e[1]+cd[e[2]][0]*i
                    if 0<=sss<=2500:
                        if used[e[2]*2501+sss]==-1:
                            heapq.heappush(edgelist,[e[0]+kai+cd[e[2]][1]*i,e[2]*2501+sss])  
                    else:
                        break
    return used

################################
n,m,ss = map(int,input().split())

edge = [[] for i in range(n)]

for i in range(m):
    x,y,a,b = map(int,input().split())
    edge[x-1].append([b,a,y-1])
    edge[y-1].append([b,a,x-1])
cd=[]
for i in range(n):
    cd.append(list(map(int,input().split())))
pp=dijkstra_heap()
for i in range(1,n):
    ans=10**20
    for j in range(2501):
        if pp[i*2501+j]!=-1:
            ans=min(ans,pp[i*2501+j])
    print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect, heapq
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n,m,s0 = map(int,input().split())
s0 = min(50,s0)
G = [[] for i in range(n)]
for i 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))
kankin = [tuple(map(int,input().split())) for i in range(n)]

def ceil(x,y):
  return (x-1)//y+1


def dijktra(g,s):
    n=len(g)
    dist = [[inf]*51 for i in range(n)]
    dist[s][s0]
    hq=[]
    heapq.heappush(hq,(0,s0,s))
    while hq:
      time,money,u = heapq.heappop(hq)
      if dist[u][money] < time: continue
      c,d = kankin[u]
      while money <= 50:
        for v,money1,time1 in g[u]:
          if not money >= money1: continue
          if dist[v][money-money1] > time + time1:
            dist[v][money-money1] = (time + time1)
            heapq.heappush(hq,(time + time1, money-money1,v))
        money += c; time += d

    return dist

dist = dijktra(G,0)
for i in range(1,n):
  print(min(dist[i]))

Submission status: Wrong Answer

Solution code:
import heapq
def dijkstra_heap():
    used = [-1] * (2501*n)
    edgelist=[]
    d=[0]*n
    d[0]=1
    for i in range(0,2501):
        if 0<=ss+i*cd[0][0]<=2500:
            heapq.heappush(edgelist,[cd[0][1]*i,cd[0][0]*i+ss])
        else:
            break
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        if used[minedge[1]]!=-1:
            continue
        v = minedge[1]
        kai=minedge[0]
        mai=v%2501
        used[v] = kai
        d[v//2501]=1
        if sum(d)==n:
            return used
        for e in edge[v//2501]:
            if mai-e[1]>=0:
                for i in range(2501):
                    sss=mai-e[1]+cd[e[2]][0]*i
                    if 0<=sss<=2500:
                        if used[e[2]*2501+sss]==-1:
                            heapq.heappush(edgelist,[e[0]+kai+cd[e[2]][1]*i,e[2]*2501+sss])  
                    else:
                        break
    return used

################################
n,m,ss = map(int,input().split())

edge = [[] for i in range(n)]

for i in range(m):
    x,y,a,b = map(int,input().split())
    edge[x-1].append([b,a,y-1])
    edge[y-1].append([b,a,x-1])
cd=[]
for i in range(n):
    cd.append(list(map(int,input().split())))
pp=dijkstra_heap()
for i in range(1,n):
    ans=10**20
    for j in range(2501):
        if pp[i*2501+j]!=-1:
            ans=min(ans,pp[i*2501+j])
    print(ans)

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]:
        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 ** 18 #最短時間
    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 ** 18
  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]:
        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 ** 18
  for s in range(N):
    if DB[s][g][0] == 0: continue
    mi = min(mi, DB[s][g][0])
  if mi == 10 ** 18:
    x = 1 / 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 ** 18 #最短時間
    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 ** 18
  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]:
        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 ** 18
  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):
  mid = 10 ** 18 #最短時間
  mim = 0 #最短時間のとこの残金
  for j in range(N):
    if D[j] == 0: continue
    if mid > DB[j][s][0]:
      mid, mim = DB[j][s]
  DB[s][s] = [mid, mim]
  for _ in range(N):
    mid = 10 ** 18 #最短時間
    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 ** 9
  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]:
        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 ** 18
  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):
  mid = 10 ** 18 #最短時間
  mim = 0 #最短時間のとこの残金
  for j in range(N):
    if D[j] == 0: continue
    if mid > DB[j][s][0]:
      mid, mim = DB[j][s]
  DB[s][s] = [mid, mim]
  for _ in range(N):
    mid = 10 ** 18 #最短時間
    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 ** 9
  mix = 0
  for j in range(N):
    if D[j] == 0: continue
    for k in range(N):
      if D[k] == 1: continue
      if 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 ** 18
  for s in range(N):
    if DB[s][g][0] == 0: continue
    mi = min(mi, DB[s][g][0])
  print(mi)