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:
# -*- coding: utf-8 -*-
import heapq
import sys
from collections import defaultdict

input = sys.stdin.buffer.readline
INF = 2**62-1


def read_int_n():
    return list(map(int, input().split()))


def read_str_n():
    return list(map(str, input().split()))


def Dijkstra(g, s):
    d = defaultdict(lambda: INF)
    d[s] = 0
    q = []
    heapq.heappush(q, (d[s], s))

    prev = {}
    done = set()
    while q:
        c, u = heapq.heappop(q)
        if u in done:
            continue
        done.add(u)
        for v in g[u]:
            alt = g[u][v] + d[u]
            if d[v] > alt:
                d[v] = alt
                prev[v] = u
                heapq.heappush(q, (d[v], v))
    return d

def slv(N, M, S, UVAB, CD):
    g = defaultdict(dict)
    V = {}
    MA = 0
    for u, v, a, b in UVAB:
        g[u][v] = (a, b)
        g[v][u] = (a, b)
        MA = max(MA, a)
    MA *= (N-1)

    for i, (c, d) in enumerate(CD, 1):
        V[i] = (c, d)

    s = (1, min(S, MA))
    d = defaultdict(lambda: INF)
    d[s] = 0
    q = []
    heapq.heappush(q, (d[s], s))

    while q:
        c, u = heapq.heappop(q)
        if d[u] < c:
            continue
        uu, cc = u
        c, dd = V[uu]
        for vv in g[uu]:
            a, b = g[uu][vv]
            m = cc - a
            for i in range(1000000):
                m += i*c
                if m < 0:
                    continue
                m = min(m, MA)
                v = (vv, m)
                alt = i*dd + b + d[u]

                if d[v] > alt:
                    d[v] = alt
                    heapq.heappush(q, (d[v], v))
                if m == MA:
                    break

    ans = [INF] * (N+1)
    for k, v in d.items():
        u = k[0]
        ans[u] = min(ans[u], v)

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



def main():
    N, M, S = read_int_n()
    UVAB = [read_int_n() for _ in range(M)]
    CD = [read_int_n() for _ in range(N)]
    (slv(N, M, S, UVAB, CD))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import heapq
import sys
from collections import defaultdict

input = sys.stdin.buffer.readline
INF = 2**62-1


def read_int_n():
    return list(map(int, input().split()))


def read_str_n():
    return list(map(str, input().split()))


def slv(N, M, S, UVAB, CD):
    g = defaultdict(dict)
    V = {}
    MA = 0
    for u, v, a, b in UVAB:
        g[u][v] = (a, b)
        g[v][u] = (a, b)
        MA += a

    for i, (c, d) in enumerate(CD, 1):
        V[i] = (c, d)

    stack = [0]
    d = defaultdict(lambda: INF)


    def f(u, m, s):
        q = []
        c, d = V[u]
        for i in range(1, 100000):
            nc = s+i*c
            if nc > MA:
                q.append((m+i*d, (u, MA)))
                break
            else:
                q.append((m+i*d, (u, nc)))
        return q

    S = min(S, MA)
    q = [(0, (1, S))]
    heapq.heapify(q)
    d = defaultdict(lambda : INF)
    d[(1, S)] = 0
    while q:
        m, u = heapq.heappop(q)
        for v in g[u[0]]:
            na, nb = g[u[0]][v]
            if na <= u[1]:
                alt = nb + d[u]
                vv = (v, u[1]-na)
                if d[vv] > alt:
                    d[vv] = alt
                    heapq.heappush(q, (alt, vv))
        if m not in d:
            for qq in f(u[0], m, u[1]):
                if qq[1] not in d:
                    d[qq[1]] = qq[0]
                    heapq.heappush(q, qq)

    ans = [INF] * (N+1)
    for k, v in d.items():
        u = k[0]
        ans[u] = min(ans[u], v)

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



def main():
    N, M, S = read_int_n()
    UVAB = [read_int_n() for _ in range(M)]
    CD = [read_int_n() for _ in range(N)]
    (slv(N, M, S, UVAB, CD))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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


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

d = defaultdict(list)
e = defaultdict(int)

for _ in range(M):
    U, V, A, B = map(int, input().split())
    d[U].append((A, B, V))
    d[V].append((A, B, U))

for i in range(1, N+1):
    C, D = map(int, input().split())
    e[i] = (C, D)

dist = defaultdict(lambda :10**30)
ans = defaultdict(lambda :10**30)

source = (1, S)
dist[source] = 0
q = [(0, source)]
visited = [False]*(N+1)

while q:
    cost, (s, nokori) = heappop(q)
    u, v = e[s]
    if dist[(s, nokori)] < cost:
        break

    for a, b, t in d[s]:
        if visited[t]:continue
        i = 0
        while 1:
            n_nokori = nokori+u*i-a
            n_cost = b +v*i
            nt = (t, n_nokori)
            
            if n_nokori < 0:
                i += 1
                continue
            
            if dist[nt] > dist[(s, nokori)]+n_cost:
                dist[nt] = dist[(s, nokori)]+n_cost
                heappush(q, (dist[nt], nt))
            
            i += 1
            if n_nokori > 6001:
                break

for (s, _), v in dist.items():
    ans[s] = min(ans[s], v)

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

Submission status: Wrong Answer

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


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

d = defaultdict(list)
e = defaultdict(int)

for _ in range(M):
    U, V, A, B = map(int, input().split())
    d[U].append((A, B, V))
    d[V].append((A, B, U))

for i in range(1, N+1):
    C, D = map(int, input().split())
    e[i] = (C, D)

dist = defaultdict(lambda :10**30)
ans = defaultdict(lambda :10**30)

source = (1, S)
dist[source] = 0
q = [(0, source)]
visited = [False]*(N+1)

while q:
    cost, (s, nokori) = heappop(q)
    u, v = e[s]
    if dist[(s, nokori)] < cost:
        break

    for a, b, t in d[s]:
        if visited[t]:continue
        i = 0
        while 1:
            n_nokori = nokori+u*i-a
            n_cost = b +v*i
            nt = (t, n_nokori)

            i += 1
            if n_nokori < 0:
                continue
            
            if dist[nt] > dist[(s, nokori)]+n_cost:
                dist[nt] = dist[(s, nokori)]+n_cost
                heappush(q, (dist[nt], nt))
            
            i += 1
            if n_nokori > 5001:
                break

for (s, _), v in dist.items():
    ans[s] = min(ans[s], v)

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

Submission status: Wrong Answer

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()

n, m, s = map(int, input().split())
s = min(s, 2500)
from collections import defaultdict
# O(ElogV)
import heapq
def dijkstra(s, x):
    # 始点sから各頂点への最短距離
    d = defaultdict(lambda: float("inf"))
    d[(s, x)] = 0
    # 各頂点が訪問済みかどうか
    used = defaultdict(lambda: False)
    used[(s, x)] = True
    # 仮の距離を記録するヒープ
    que = []
    for e in edge[(s, x)]:
        heapq.heappush(que, e)
    while que:
        minedge = heapq.heappop(que)
        if used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = True
        for e in edge[v]:
            if not used[e[1]]:
                heapq.heappush(que, (e[0] + d[v], e[1]))
    return d

max_money = 2500
edge = defaultdict(list)
for _ in range(m):
    u, v, a, b = map(int, input().split())
    u -= 1
    v -= 1
    for i in range(a, max_money + 1):
        if i - a >= 0:
            edge[(u, i)].append((b, (v, i - a)))
            edge[(v, i)].append((b, (u, i - a)))
for j in range(n):
    c, d = map(int, input().split())
    for i in range(max_money + 1):
        if i + c <= max_money:
            edge[(j, i)].append((d, (j, i + c)))

ans = [10**10]*n

d = dijkstra(0, s)
for i in d:
    x, y = i
    cost = d[i]
    ans[x] = min(ans[x], cost)
for i in ans[1:]:
    print(i)

Submission status: Wrong Answer

Solution code:
# ダイクストラ
def main():
    import sys
    sys.setrecursionlimit(10**9)
    input = sys.stdin.readline
    from heapq import heappush, heappop

    N, M, S = map(int, input().split())
    S = min(S, 2500)
    graph = [[] for _ in range(N)]

    for u, v, a, b in (map(int, input().split()) for _ in range(M)):
        graph[u-1].append((v-1, a, b))
        graph[v-1].append((u-1, a, b))

    for i, (c, d) in enumerate(map(int, input().split()) for _ in range(N)):
        graph[i].append((i, -c, d))

    hq = [(0, 0, S)]
    INF = 10**10
    # dp[v][silver]
    # 都市vにsilverを使って到達したときの時間の最小値
    dp = [[INF]*2551 for _ in range(N)]
    dp[0][S] = 0

    while hq:
        time, v, silver = heappop(hq)
        if dp[v][silver] < time:
            continue

        for dest, a, b in graph[v]:
            next_s = silver-a if silver-a < 2500 else 2500
            if next_s < 0 or dp[dest][next_s] <= time+b:
                continue
            for i in range(next_s, -1, -1):
                if dp[dest][i] > time+b:
                    dp[dest][i] = time+b
                else:
                    break
            heappush(hq, (time+b, dest, next_s))

    print(*(min(dp[i]) for i in range(1, N)), sep='\n')

main()

Submission status: Wrong Answer

Solution code:
# ダイクストラ
def main():
    import sys
    sys.setrecursionlimit(10**9)
    input = sys.stdin.readline
    from heapq import heappush, heappop

    N, M, S = map(int, input().split())
    S = min(S, 2500)
    graph = [[] for _ in range(N)]

    for u, v, a, b in (map(int, input().split()) for _ in range(M)):
        graph[u-1].append((v-1, a, b))
        graph[v-1].append((u-1, a, b))

    for i, (c, d) in enumerate(map(int, input().split()) for _ in range(N)):
        graph[i].append((i, -c, d))

    hq = [(0, 0, S)]
    INF = 10**10
    # dp[v][silver]
    # 都市vにsilverを使って到達したときの時間の最小値
    dp = [[INF]*2501 for _ in range(N)]
    dp[0][S] = 0

    while hq:
        time, v, silver = heappop(hq)
        if dp[v][silver] < time:
            continue

        for dest, a, b in graph[v]:
            next_s = silver-a if silver-a < 2500 else 2500
            if next_s < 0 or dp[dest][next_s] <= time+b:
                continue
            for i in range(next_s, -1, -1):
                if dp[dest][i] > time+b:
                    dp[dest][i] = time+b
                else:
                    break
            heappush(hq, (time+b, dest, next_s))

    print(*(min(dp[i]) for i in range(1, N)), sep='\n')

main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
import heapq
INF = 10**9

MAX_SILVER = 3000 

class Dijkstra:
    def __init__(self, adj):
        self.adj = adj
        self.dist = [INF] * len(adj)
        self.q = []

    def calc(self, start):
        self.dist[start] = 0
        heapq.heappush(self.q, (0, start))
        while len(self.q) != 0:
            prov_cost, src = heapq.heappop(self.q)
            if self.dist[src] < prov_cost:
                continue
            for dest, cost in self.adj[src]:
                if self.dist[dest] > self.dist[src] + cost:
                    self.dist[dest] = self.dist[src] + cost
                    heapq.heappush(self.q, (self.dist[dest], dest))
        return self.dist

n, m, s = map(int, input().split())
edge = [[] for _ in range(n * MAX_SILVER)]
for _ in range(m):
    u, v, a, b = map(int, input().split())
    u -= 1; v -= 1
    for i in range(a, MAX_SILVER):
        edge[u*MAX_SILVER + i].append((v*MAX_SILVER + i-a, b))
        edge[v*MAX_SILVER + i].append((u*MAX_SILVER + i-a, b))

for v in range(n):
    c, d = map(int, input().split())
    for i in range(MAX_SILVER - 100):
        edge[v*MAX_SILVER + i].append((v*MAX_SILVER + i + c, d))

DIJK = Dijkstra(edge)
if s > 2500:
    s = 2500
dist = DIJK.calc(s)

for v in range(1, n): 
    ret = INF
    for val in range(MAX_SILVER):
        if dist[v*MAX_SILVER + val] < ret:
            ret = dist[v*MAX_SILVER + val]
    print(ret)

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop
N, M, S = map(int, input().split())
edge = [[] for _ in range(N)]
for i in range(M):
    u,v,a,b = map(int, input().split())
    edge[u-1].append((v-1, a, b))
    edge[v-1].append((u-1, a, b))

INF = 10 ** 18

CD = [tuple(map(int, input().split())) for _ in range(N)]
S = min(2500, S)
# キューの中身(時間,銀貨の数,現在地)
q = [(0, S, 0)]
d = [[INF] * 2510 for _ in range(N)]
#d[0][S] = 0
while len(q) > 0:
    t, s, v = heappop(q)
    d[v][s] = t
    for nv, ns, nt in edge[v]:
        if s < ns: continue
        if d[nv][s-ns] > t+nt:
            d[nv][s-ns] = t+nt
            heappush(q, (t+nt, s-ns, nv))
    c, dtime = CD[v]
    if s+c <= 2500:
        if d[v][s+c] > t+dtime:
            d[v][s+c] = t+dtime
            heappush(q, (t+dtime, s+c, v))

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

Submission status: Wrong Answer

Solution code:
import heapq as hq
N,M,S = list(map(int, input().split()))
#Edge
E = [[] for _ in range(N)]
  
for _ in range(M):
  # U <-> V, A coins, B mins
  u,v,a,b = list(map(int, input().split()))
  # 0-indexed
  E[u-1].append([v-1, a, b])
  E[v-1].append([u-1, a, b])

# City
C = []
for _ in range(N):
  # C coins, D mins
  C.append(list(map(int, input().split())))
  
# dp[p][i] 点Pにたどり着いた時、i円持っている時の最小時間
MAXYEN = 50 * N
dp = [[ 1e12 for i in range(MAXYEN + 5) ] for _ in range(N)]
S = min(MAXYEN, S)
dp[0][S] = 0

# 状態は点とお金と時間. time, pointindex, money
Q = []
hq.heapify(Q)
hq.heappush(Q, [0,0,S])

while len(Q) > 0:
  nowt, nowi, nowm = hq.heappop(Q)
  #print("Pop :", nowt, nowi, nowm)
  # Edgeをわたる。a yen払ってB時間かけて、Vに移動する。
  for e in E[nowi]:
    to_i, costm, costt = e
    #print("Edge:", to_i, costm, costt)
    if nowm - costm < 0:
      # unreachable 
      continue
    if dp[to_i][nowm-costm] > dp[nowi][nowm] + costt:
      dp[to_i][nowm-costm] = dp[nowi][nowm] + costt
      hq.heappush(Q, [dp[nowi][nowm] + costt, to_i, nowm-costm])
      
  # その場でお金を1回買う。移動せず、CYenGetして、D時間かける
  getm, costt = C[nowi]
  targetm = min(MAXYEN, nowm + getm)
  #print("Buy :", getm, targetm, costt)
  if dp[nowi][targetm] > dp[nowi][nowm] + costt:
    dp[nowi][targetm] = dp[nowi][nowm] + costt
    hq.heappush(Q, [dp[nowi][targetm], nowi, targetm])
  
for i in range(1,N):
  print(min(dp[i]))

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop
import sys
n, m, s = map(int, input().split())
edges = list()
for _ in range(m):
  new_u, new_v, new_a, new_b = map(int, input().split())
  edges.append((new_u-1, new_v-1, new_a, new_b))
coins_range = (n-1)*max(edges,key=lambda item:item[2])[2]+1
print(coins_range)
c, d = list(), list()
for _ in range(n):
  new_c, new_d = map(int, input().split())
  c.append(new_c)
  d.append(new_d)
adjacency = {(i, j): [] for i in range(n) for j in range(coins_range)}
for (node, coins) in adjacency.keys():
  new_coins = coins+c[node]
  if new_coins<=coins_range-1:
    adjacency[(node, coins)].append(((node, coins+c[node]), (d[node])))
for edge in edges:
  node1, node2, cost, weight = edge
  for coins in range(cost, coins_range):
    adjacency[(node1, coins)].append(((node2, coins-cost), weight))
    adjacency[(node2, coins)].append(((node1, coins-cost), weight))
def dijkstra():
  while state_heap:
    distance, state = heappop(state_heap)
    visited[state] = True
    for (new_state, weight) in adjacency[state]:
      if not visited[new_state]:
        distances[new_state] = min(distances[new_state], distance+weight)
        heappush(state_heap, (distances[new_state], new_state))
distances = {(i, j): float("inf") for i in range(n) for j in range(coins_range)}
initial_state = (0, min(s, coins_range-1))
distances[initial_state] = 0
state_heap = []
heappush(state_heap, (distances[initial_state], initial_state))
visited = {(i, j): False for i in range(n) for j in range(coins_range)}
visited[initial_state] = True
dijkstra()
final_distances = [float("inf")]*n
for ((node, _), distance) in distances.items():
  final_distances[node] = min(final_distances[node], distance)
[print(distance) for distance in final_distances[1:]]

Submission status: Wrong Answer

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

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

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

D=defaultdict(lambda :[])

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

for c,d in C:
    for n in range(N):
        for a in range(A_max+1):
            if a+c>A_max:
                continue
            to_state=(n,a+c)
            from_state=(n,a)
            D[from_state].append((d,to_state))


start=(0,max(A_max,S))
Q=[(0,start)]

Dist=defaultdict(lambda :float('inf'))

Dist[start]=0

while Q:
    q = heapq.heappop(Q)
    cur_time,cur_state=q

    if Dist[cur_state]<cur_time:
        continue
    for cost,next_state in D[cur_state]:
        next_time = cost+cur_time

        if Dist[next_state]>next_time:
            Dist[next_state]=next_time
            heapq.heappush(Q,(next_time,next_state))

for dest in range(1,N):
    ans=float("inf")
    for a in range(A_max+1):
        state=(dest,a)
        ans=min(ans,Dist[state])
    print(ans)

Submission status: Wrong Answer

Solution code:
import heapq


class Dijkstra(object):

    """ 使用例
    dik = Dijkstra()
    edge = defaultdict(list)
    edge[(1, 1)].append([1, (1, 2)])
    edge[(1, 2)].append([1, (1, 1)])
    edge[(1, 2)].append([2, (2, 1)])
    edge[(2, 1)].append([2, (1, 2)])
    edge[(2, 1)].append([5, (2, 2)])
    edge[(2, 2)].append([5, (2, 1)])
    edge[(2, 2)].append([3, (1, 2)])
    edge[(1, 2)].append([3, (2, 2)])

    s0 = (1, 1)
    ans = dik(s0, edge)

    """

    INF = 10**11

    def __init(self):
        pass

    def __call__(self, s0, edge):

        # s0:始点 (,,,)
        # edge[(,,,)] = [コスト、(,,,)], [コスト、(,,,)]

        d = dict()
        used = dict()

        edgelist = edge[s0]
        heapq.heapify(edgelist)

        d[s0] = 0
        used[s0] = False

        while len(edgelist):
            minedge = heapq.heappop(edgelist)
            if not used.get(minedge[1], True):
                continue
            v = minedge[1]
            d[v] = minedge[0]
            used[v] = False

            for e in edge[v]:
                if used.get(e[1], True):
                    if d.get(e[1], self.INF) <= d[v] + e[0]:
                        continue
                    heapq.heappush(edgelist, [d[v] + e[0], e[1]])

        return d


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

    s_max = 2500
    S = min(S, s_max)

    dik = Dijkstra()
    edge = dict()
    s0 = (1, S)

    for m in range(1, M + 1):
        U, V, A, B = map(int, input().split())
        for s in range(A, s_max + 1):
            if not (U, s) in edge:
                edge[(U, s)] = []
            if not (V, s) in edge:
                edge[(V, s)] = []
            edge[(U, s)].append([B, (V, s - A)])
            edge[(V, s)].append([B, (U, s - A)])

    for n in range(1, N + 1):
        C, D = map(int, input().split())
        for s in range(s_max + 1):
            s1 = min(s + C, s_max)
            if not (n, s) in edge:
                edge[(n, s)] = []
            edge[(n, s)].append([D, (n, s1)])

    d = dik(s0, edge)

    for n in range(2, N + 1):
        ans = Dijkstra.INF
        for s in range(s_max + 1):
            ans = min(ans, d.get((n, s), Dijkstra.INF))
        print(ans)


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
import heapq


class Dijkstra(object):

    """ 使用例
    dik = Dijkstra()
    edge = defaultdict(list)
    edge[(1, 1)].append([1, (1, 2)])
    edge[(1, 2)].append([1, (1, 1)])
    edge[(1, 2)].append([2, (2, 1)])
    edge[(2, 1)].append([2, (1, 2)])
    edge[(2, 1)].append([5, (2, 2)])
    edge[(2, 2)].append([5, (2, 1)])
    edge[(2, 2)].append([3, (1, 2)])
    edge[(1, 2)].append([3, (2, 2)])

    s0 = (1, 1)
    ans = dik(s0, edge)

    """

    INF = 10**9

    def __init(self):
        pass

    def __call__(self, s0, edge):

        # s0:始点 (,,,)
        # edge[(,,,)] = [コスト、(,,,)], [コスト、(,,,)]

        d = dict()
        used = dict()

        edgelist = edge[s0]
        heapq.heapify(edgelist)

        d[s0] = 0
        used[s0] = False

        while len(edgelist):
            minedge = heapq.heappop(edgelist)
            if not used.get(minedge[1], True):
                continue
            v = minedge[1]
            d[v] = minedge[0]
            used[v] = False

            for e in edge[v]:
                if used.get(e[1], True):
                    if d.get(e[1], self.INF) <= d[v] + e[0]:
                        continue
                    heapq.heappush(edgelist, [d[v] + e[0], e[1]])

        return d


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

    s_max = 2500
    S = min(S, s_max)

    dik = Dijkstra()
    edge = dict()
    s0 = (1, S)

    for m in range(1, M + 1):
        U, V, A, B = map(int, input().split())
        for s in range(A, s_max + 1):
            if not (U, s) in edge:
                edge[(U, s)] = []
            if not (V, s) in edge:
                edge[(V, s)] = []
            edge[(U, s)].append([B, (V, s - A)])
            edge[(V, s)].append([B, (U, s - A)])

    for n in range(1, N + 1):
        C, D = map(int, input().split())
        for s in range(s_max + 1):
            s1 = min(s + C, s_max)
            if not (n, s) in edge:
                edge[(n, s)] = []
            edge[(n, s)].append([D, (n, s1)])

    d = dik(s0, edge)

    for n in range(2, N + 1):
        ans = Dijkstra.INF
        for s in range(s_max + 1):
            ans = min(ans, d.get((n, s), Dijkstra.INF))
        print(ans)


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
import heapq


class Dijkstra(object):

    """ 使用例
    dik = Dijkstra()
    edge = defaultdict(list)
    edge[(1, 1)].append([1, (1, 2)])
    edge[(1, 2)].append([1, (1, 1)])
    edge[(1, 2)].append([2, (2, 1)])
    edge[(2, 1)].append([2, (1, 2)])
    edge[(2, 1)].append([5, (2, 2)])
    edge[(2, 2)].append([5, (2, 1)])
    edge[(2, 2)].append([3, (1, 2)])
    edge[(1, 2)].append([3, (2, 2)])

    s0 = (1, 1)
    ans = dik(s0, edge)

    """

    def __init(self):
        pass

    def __call__(self, s0, edge):

        # s0:始点 (,,,)
        # edge[(,,,)] = [コスト、(,,,)], [コスト、(,,,)]

        d = dict()
        used = dict()

        edgelist = edge[s0]
        heapq.heapify(edgelist)

        d[s0] = 0
        used[s0] = False

        while len(edgelist):
            minedge = heapq.heappop(edgelist)
            if not used.get(minedge[1], True):
                continue
            v = minedge[1]
            d[v] = minedge[0]
            used[v] = False

            for e in edge[v]:
                if used.get(e[1], True):
                    if d.get(e[1], float('inf')) <= d[v] + e[0]:
                        continue
                    heapq.heappush(edgelist, [d[v] + e[0], e[1]])

        return d


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

s_max = 2500
S = min(S, s_max)

dik = Dijkstra()
edge = dict()
s0 = (1, S)

for m in range(1, M + 1):
    U, V, A, B = map(int, input().split())
    for s in range(A, s_max + 1):
        if not (U, s) in edge:
            edge[(U, s)] = []
        if not (V, s) in edge:
            edge[(V, s)] = []
        edge[(U, s)].append([B, (V, s - A)])
        edge[(V, s)].append([B, (U, s - A)])

for n in range(1, N + 1):
    C, D = map(int, input().split())
    for s in range(s_max + 1):
        s1 = min(s + C, s_max)
        if not (n, s) in edge:
            edge[(n, s)] = []
        edge[(n, s)].append([D, (n, s1)])

d = dik(s0, edge)
exit()

for n in range(2, N + 1):
    ans = float('inf')
    for s in range(s_max + 1):
        ans = min(ans, d.get((n, s)), float('inf'))
    print(ans)

Submission status: Wrong Answer

Solution code:
import heapq
from collections import defaultdict


class Dijkstra(object):

    """ 使用例
    dik = Dijkstra()
    edge = defaultdict(list)
    edge[(1, 1)].append([1, (1, 2)])
    edge[(1, 2)].append([1, (1, 1)])
    edge[(1, 2)].append([2, (2, 1)])
    edge[(2, 1)].append([2, (1, 2)])
    edge[(2, 1)].append([5, (2, 2)])
    edge[(2, 2)].append([5, (2, 1)])
    edge[(2, 2)].append([3, (1, 2)])
    edge[(1, 2)].append([3, (2, 2)])

    s0 = (1, 1)
    ans = dik(s0, edge)

    """

    def __init(self):
        pass

    def __call__(self, s0, edge):

        # s0:始点 (,,,)
        # edge[(,,,)] = [コスト、(,,,)], [コスト、(,,,)]

        d = defaultdict(lambda: float('inf'))
        used = defaultdict(lambda: True)

        edgelist = edge[s0]
        heapq.heapify(edgelist)

        d[s0] = 0
        used[s0] = False

        while len(edgelist):
            minedge = heapq.heappop(edgelist)
            if not used[minedge[1]]:
                continue
            v = minedge[1]
            d[v] = minedge[0]
            used[v] = False

            for e in edge[v]:
                if used[e[1]]:
                    if d[e[1]] <= d[v] + e[0]:
                        continue
                    heapq.heappush(edgelist, [d[v] + e[0], e[1]])

        return d


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

s_max = 2500
S = min(S, s_max)

dik = Dijkstra()
edge = defaultdict(list)
s0 = (1, S)

for m in range(1, M + 1):
    U, V, A, B = map(int, input().split())
    for s in range(A, s_max + 1):
        edge[(U, s)].append([B, (V, s - A)])
        edge[(V, s)].append([B, (U, s - A)])

for n in range(1, N + 1):
    C, D = map(int, input().split())
    for s in range(s_max + 1):
        s1 = min(s + C, s_max)
        edge[(n, s)].append([D, (n, s1)])

d = dik(s0, edge)
exit()

for n in range(2, N + 1):
    ans = []
    for s in range(s_max + 1):
        ans.append(d[(n, s)])
    print(min(ans))