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:
def examA():
    S, W = LI()
    if S<=W:
        print("unsafe")
    else:
        print("safe")
    return

def examB():
    A, B, C, D = LI()
    while(True):
        C -= B
        if C<=0:
            print("Yes")
            break
        A -= D
        if A<=0:
            print("No")
            break
    return

def examC():
    N = I()
    S = [SI()for _ in range(N)]
    Set = set(S)
    ans = len(Set)
    print(ans)
    return

def examD():
    S = SI()
    N = len(S)
    D = [0]*(N+1)
    for i in range(N):
        D[i+1] = (D[i]+int(S[N-1-i])*pow(10,i,2019))%2019
    #print(D)
    ans = 0
    C = Counter(D)
    #print(C)
    for c in C.values():
        ans += (c-1)*c//2
    print(ans)
    return

def examE():
    def dijkstra(n, edges, start, C, silver):
        maxC = (2*n-1)*50
        dist = [[inf]*(maxC+1) for _ in range(n)]
        dist[start][silver] = 0
        Q = [(0, (start, silver))]  # (dist,vertex)
        while (Q):
            d, (v, c) = heapq.heappop(Q)
            if dist[v][c]<d:continue
            loop = (maxC-c)//C[v][0] + 1
            for i in range(loop):
                nextc = c+i*C[v][0]
                nextd = d+i*C[v][1]
                if nextc>maxC:
                    nextc=maxC
                if dist[v][nextc] < nextd: continue  # 候補として挙がったd,vだが、他に短いのがある
                for u, cost, coin in edges[v]:
                    k = nextc-coin
                    if k<0:
                        continue
                    if dist[u][k] > nextd + cost:
                        dist[u][k] = nextd + cost
                        heapq.heappush(Q, (dist[u][nextc-coin], (u, k)))
        return dist
    N, M, S = LI()
    V = [[]for _ in range(N)]
    for _ in range(M):
        s, t, a, b = LI()
        s -= 1; t -= 1
        V[s].append((t,b,a))
        V[t].append((s,b,a))
    C = [LI()for _ in range(N)]
    D = dijkstra(N,V,0,C,min(S,(2*N-1)*50))
    for i in range(1,N):
        print(min(D[i]))
    return

def examE2():
    def dijkstra(edges, start=0):
        dist = [inf] * len(edges)
        dist[start] = 0
        Q = [(0, start)]  # (dist,vertex)
        while (Q):
            d, v = heapq.heappop(Q)
            if dist[v] < d: continue  # 候補として挙がったd,vだが、他に短いのがある
            for u, cost in edges[v]:
                if dist[u] > dist[v] + cost:
                    dist[u] = dist[v] + cost
                    heapq.heappush(Q, (dist[u], u))
        return dist
    maxS = 2500
    N, M, S = LI()
    V = [[]for _ in range(N*(maxS+1))]

    for _ in range(M):
        u, v, a, b = LI()
        u -= 1; v -= 1
        for i in range(a, maxS):
            V[u * maxS + i].append([v * maxS + i - a, b])
            V[v * maxS + i].append([u * maxS + i - a, b])

    for i in range(N):
        c, d = LI()
        for j in range(maxS - 1):
            V[i * maxS + j].append([i * maxS + min(j + c, maxS - 1), d])
    D = dijkstra(V,min(maxS,S))
    for i in range(1,N):
        print(min(D[i*maxS:(i+1)*maxS]))
    return

def examF():
    N = I()
    S = LI()
    T = LI()
    U = LI()
    V = LI()

    ans = 0
    print(ans)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(readline())
def LI(): return list(map(int,readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examE2()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Submission status: Wrong Answer

Solution code:

N, M, S = map(int,input().split())
ubab = [list(map(int, input().split())) for _ in range(M)]
cd = [list(map(int, input().split())) for _ in range(N)]

from heapq import heappush, heappop

routes = [[] for _ in range(N)]
max_money = 0
for u, v, a, b in ubab:
    routes[u-1].append([b, -a, v-1]) #★注意★[コスト、お金、要素]
    routes[v-1].append([b, -a, u-1])
    if a > max_money:
        max_money = a

for i, (c, d) in enumerate(cd):
    routes[i].append([d,+c,i])

max_pocessing = max_money * (N-1)

minimum = [[10e+1000 for _ in range(max_pocessing+1)] for _ in range(N)] 
if S>max_pocessing:
    S = max_pocessing-1
minimum[0][S] = 0
last_num = 0
last_money = S # [地点番号、所持金]
hp = []


while True:
    for cost, money, num in routes[last_num]:
        if last_money+money >= max_pocessing:
            money = max_pocessing - last_money
        if minimum[num][last_money+money] == 10e+1000:
            heappush(hp, (minimum[last_num][last_money]+cost, last_money+money, num))    
    while len(hp)>0:
        candidate_cost, candidate_money, candidate_num = heappop(hp)
        if minimum[candidate_num][candidate_money] == 10e+1000 and candidate_money >= 0:
            break
    else:
        break
    last_num = candidate_num
    last_money = candidate_money
    minimum[candidate_num][candidate_money] = candidate_cost

for each_minimum in minimum[1:]:
    print(min(each_minimum))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub
import copy

# sys.setrecursionlimit(100000)
input = sys.stdin.buffer.readline
INF = 2**62-1

def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


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


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
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)
    done = set()
    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))
        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:

def sub(s, c, d):
    """s枚の銀貨を得たいときに、レートc, 時間dでかかる最小時間
    """
    dp = [[None] * (s+1) for _ in range(len(c))]
    for i in range(s+1):
        dp[0][i] = ((i // c[0] + int(i%c[0])) * d[0])
    for i in  range(len(c)):
        dp[i][0] = 0
    for i in range(1,len(c)):
        cc, dd = c[i], d[i]
        for j in range(1,s+1):
            dp[i][j] = dp[i-1][j]
            if j>=cc:
                dp[i][j] = min(dp[i][j], dp[i][j-cc]+dd)
            else:
                dp[i][j] = min(dp[i][j], dp[i][0]+dd)
#     print(s, c, d, dp[-1][-1])
    return dp[len(c)-1][s]

import heapq
from collections import defaultdict
h = []
heapq.heapify(h)

n, m, s = list(map(int, input().split()))
a, b = [[None] * m for _ in range(2)]
c, d = [[None] * n for _ in range(2)]
ns = defaultdict(list)
uv2e = {}
for i in range(m):
    u,v,a[i],b[i] = list(map(int, input().split()))
    ns[u-1].append(v-1)
    ns[v-1].append(u-1)
    uv2e[u-1,v-1] = i
    uv2e[v-1,u-1] = i
for i in range(n):
    c[i], d[i] = list(map(int, input().split()))

# (t, u, ss, dd)
prevs = defaultdict(list)
heapq.heappush(h, (0, 0, s, set([0])))
prevs[0].append(set([0]))
done = set()
best_time = [10**100] * n
best_prev = [-1] * n
while h:
    t, u, ss, prev = heapq.heappop(h)
#     print("best: ", t, u, ss, prev)
    done.add(u)
    best_time[u] = min(t, best_time[u])
    best_prev[u] = prev
    if len(done)==n:
        break
    for v in ns[u]:
        e = uv2e[u,v]
        tmp_t = t + b[e]
        if ss>=a[e]:
            tmp_ss = s - a[e]
        else:
            tmp_ss = 0            
            tmp_t += sub(a[e] - ss, [c[item] for item in prev], [d[item] for item in prev])
#             tmp_t += min(((a[e] - ss) // c[item] + 1 - int((a[e] - ss) % c[item] == 0)) * d[item] for item in prev)

        tmp_prev = prev|set([v])
        if tmp_prev not in prevs[v]:
            heapq.heappush(h, (tmp_t, v, tmp_ss, tmp_prev))
            prevs[v].append(tmp_prev)
#             print((tmp_t, v, tmp_ss, tmp_cds, prev|set([v])))
print(*best_time[1:], sep="\n")

Submission status: Wrong Answer

Solution code:

def sub(s, c, d):
    """s枚の銀貨を得たいときに、レートc, 時間dでかかる最小時間
    """
    dp = [[None] * (s+1) for _ in range(len(c))]
    for i in range(s+1):
        dp[0][i] = ((i // c[0] + int(i%c[0])) * d[0])
    for i in range(1,len(c)):
        cc, dd = c[i], d[i]
        for j in range(s+1):
            dp[i][j] = dp[i-1][j]
            if j>=cc:
                dp[i][j] = min(dp[i][j], dp[i][j-cc]+dd)
#     print(s, c, d, dp[-1][-1])
    return dp[len(c)-1][s]

import heapq
from collections import defaultdict
h = []
heapq.heapify(h)

n, m, s = list(map(int, input().split()))
a, b = [[None] * m for _ in range(2)]
c, d = [[None] * n for _ in range(2)]
ns = defaultdict(list)
uv2e = {}
for i in range(m):
    u,v,a[i],b[i] = list(map(int, input().split()))
    ns[u-1].append(v-1)
    ns[v-1].append(u-1)
    uv2e[u-1,v-1] = i
    uv2e[v-1,u-1] = i
for i in range(n):
    c[i], d[i] = list(map(int, input().split()))

# (t, u, ss, dd)
prevs = defaultdict(list)
heapq.heappush(h, (0, 0, s, set([0])))
prevs[0].append(set([0]))
done = set()
best_time = [10**100] * n
best_prev = [-1] * n
while h:
    t, u, ss, prev = heapq.heappop(h)
#     print("best: ", t, u, ss, prev)
    done.add(u)
    best_time[u] = min(t, best_time[u])
    best_prev[u] = prev
    if len(done)==n:
        break
    for v in ns[u]:
        e = uv2e[u,v]
        tmp_t = t + b[e]
        if ss>=a[e]:
            tmp_ss = s - a[e]
        else:
            tmp_ss = 0            
            tmp_t += sub(a[e] - ss, [c[item] for item in prev], [d[item] for item in prev])
#             tmp_t += min(((a[e] - ss) // c[item] + 1 - int((a[e] - ss) % c[item] == 0)) * d[item] for item in prev)

        tmp_prev = prev|set([v])
        if tmp_prev not in prevs[v]:
            heapq.heappush(h, (tmp_t, v, tmp_ss, tmp_prev))
            prevs[v].append(tmp_prev)
#             print((tmp_t, v, tmp_ss, tmp_cds, prev|set([v])))
print(*best_time[1:], sep="\n")

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    import queue
    mod=10**9+7
    N,M,S=MI()
    #各頂点，所持金が０〜N*50までなので，状態すうはN*(N*50+1)
    #頂点iでj枚ならi*(N*50+1)+j
    NN=N*50+1
    ##########################################
    import heapq
    class Dijkstra():
        """
        ・有向 / 無向は問わない(無向の場合は，逆向きの辺もたす)
        ・負のコストがない場合のみ
        ・計算量はO(E log|V|)　
        ・heapを使うことで頂点を走査する必要がなくなる（代わりに，距離更新したものは確定でなくともqueに入れておく）
        """
        
        #最短のpathをたす
        
        
        class Edge():
            #重み付き有向辺
            
            def __init__(self, _to, _cost):
                self.to =_to
                self.cost = _cost
        
        def __init__(self, V):
            #引数Vは頂点数
            self.G = [[] for _ in range(V)] #隣接リストG[u][i]が頂点uのi番目の辺
            self. _E = 0 #辺の数
            self._V = V #頂点数
        
        #proparty - 辺の数
        def E(self):
            return self._E
        
        #proparty - 頂点数
        def V(self):
            return self._V
        
        def add(self, _from, _to, _cost):
            #2頂点と辺のコストを追加
            self.G[_from].append(self.Edge(_to,_cost))
            self._E +=1
            
        def add2(self, _from, _to, _cost):
            #2頂点と辺のコスト（無向）を追加
            self.G[_from].append(self.Edge(_to, _cost))
            self.G[_to].append(self.Edge(_from, _cost))
            self._E +=2
            
        def shortest_path(self,s):#,g):
            #始点sから頂点iまでの最短経路長のリストを返す
            
            que = [] #priority queue
            d = [float("inf")] * self.V()
            prev = [None]*self.V() #prev[j]は，sからjへ最短経路で行くときのjの一つ前の場所
            d[s] = 0
            heapq.heappush(que,(0,s)) #始点の距離と頂点番号をヒープに追加
            
            while len(que)!=0:
                #キューに格納されてある中で一番コストが小さい頂点を取り出す
                cost,v = heapq.heappop(que)
                
                #キューに格納された最短経路長候補がdの距離よりも大きい場合に処理をスキップ
                if d[v] < cost:
                    continue
                    
                #頂点vに隣接する各頂点iに対して，vを経由した場合の距離を計算して，これがd[i]よりも小さい場合に更新
                for i in range(len(self.G[v])):
                    e = self.G[v][i] #vのi個目の隣接辺
                    if d[e.to] > d[v] + e.cost:
                        d[e.to] = d[v] + e.cost #更新
                        prev[e.to] = v
                        heapq.heappush(que,(d[e.to],e.to)) #queに新たな最短経路長候補を追加
            
            """#sからgまでの最短経路
            path = []
            pos = g #今いる場所，ゴールで初期化
            for _ in range(self.V()+1):
                path.append(pos)
                if pos == s:
                    break
                #print("pos:",format(pos))
                pos = prev[pos]
            path.reverse()
            #print(path)"""
                        
            return d#,path
    ########################
    djk=Dijkstra(N*NN)
    
    for i in range(M):
        u,v,a,b=MI()
        u-=1
        v-=1
        for j in range(a,NN):
            djk.add(u*NN+j,v*NN+j-a,b)
            djk.add(v*NN+j,u*NN+j-a,b)
    for i in range(N):
        c,d=MI()
        for j in range(0,NN-c,1):
            djk.add(i*NN+j,i*NN+j+c,d)
            
    dL=djk.shortest_path(min(S,NN-1))
    for i in range(1,N):
        ans=10**10
        for j in range(0,NN):
            ans=min(ans,dL[i*NN+j])
        print(ans)
        
        
    

main()

Submission status: Wrong Answer

Solution code:
import heapq
import sys

def main():

    n,m,s = map(int,input().split())
    uvab = [list(map(int,input().split())) for _ in range(m)]
    cd = [list(map(int,input().split())) for _ in range(n)]

    edges = [[[] for _ in range(n)] for _ in range(2501)]

    for u,v,a,b in uvab:
        for i in range(a,2501):
            edges[i][u-1].append(((v-1, i-a), b))
            edges[i][v-1].append(((u-1, i-a), b))

    for i in range(n):
        c,d = cd[i]
        for j in range(2501):
            edges[j][i].append(((i, min(j+c, 2500)), d))

    def dijkstra(edges, c):
        hq = []
        d = [[10**20] * n for _ in range(c)]
        d[min(2500, s)][0] = 0
        heapq.heappush(hq, (0, (0, min(2500, s))))
        while hq:
            d1, p = heapq.heappop(hq)
            for p2, d2 in edges[p[1]][p[0]]:
                if d[p2[1]][p2[0]] == -1 or d[p2[1]][p2[0]] > d1 + d2:
                    d[p2[1]][p2[0]] = d1 + d2
                    heapq.heappush(hq, (d1+d2, p2))
        return d

    dis = dijkstra(edges, 2501)
    ans = [10**10]*n
    for i in range(2501):
        for j in range(n):
            ans[j] = min(ans[j], dis[i][j])

    for i in ans[1:]:
        print(i)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import heapq
import sys

def main():

    n,m,s = map(int,input().split())
    uvab = [list(map(int,input().split())) for _ in range(m)]
    cd = [list(map(int,input().split())) for _ in range(n)]

    edges = [[[] for _ in range(n)] for _ in range(2501)]

    for u,v,a,b in uvab:
        for i in range(a,2501):
            edges[i][u-1].append(((v-1, i-a), b))
            edges[i][v-1].append(((u-1, i-a), b))

    for i in range(n):
        c,d = cd[i]
        for j in range(2501):
            edges[j][i].append(((i, min(j+c, 2500)), d))

    def dijkstra(edges, m, c):
        hq = []
        d = [[10**10] * n for _ in range(c)]
        d[min(2500, s)][0] = 0
        heapq.heappush(hq, (0, (0, min(2500, s))))
        while hq:
            d1, p = heapq.heappop(hq)
            for p2, d2 in edges[p[1]][p[0]]:
                if d[p2[1]][p2[0]] == -1 or d[p2[1]][p2[0]] > d1 + d2:
                    d[p2[1]][p2[0]] = d1 + d2
                    heapq.heappush(hq, (d1+d2, p2))
        return d

    dis = dijkstra(edges, 0, 2501)
    ans = [10**10]*n
    for i in range(2501):
        for j in range(n):
            ans[j] = min(ans[j], dis[i][j])

    for i in ans[1:]:
        print(i)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import heapq
import sys

def main():

    n,m,s = map(int,input().split())
    uvab = [list(map(int,input().split())) for _ in range(m)]
    cd = [list(map(int,input().split())) for _ in range(n)]

    edges = [[[] for _ in range(n)] for _ in range(2501)]

    for u,v,a,b in uvab:
        for i in range(a,2501):
            edges[i][u-1].append(((v-1, i-a), b))
            edges[i][v-1].append(((u-1, i-a), b))

    for i in range(n):
        c,d = cd[i]
        for j in range(2500):
            edges[j][i].append(((i, min(j+c, 2500)), d))

    def dijkstra(edges, m, c):
        hq = []
        d = [[10**10] * n for _ in range(c)]
        d[min(2500, s)][0] = 0
        heapq.heappush(hq, (0, (0, min(2500, s))))
        while hq:
            d1, p = heapq.heappop(hq)
            for p2, d2 in edges[p[1]][p[0]]:
                if d[p2[1]][p2[0]] == -1 or d[p2[1]][p2[0]] > d1 + d2:
                    d[p2[1]][p2[0]] = d1 + d2
                    heapq.heappush(hq, (d1+d2, p2))
        return d

    dis = dijkstra(edges, 0, 2501)
    ans = [10**10]*n
    for i in range(2501):
        for j in range(n):
            ans[j] = min(ans[j], dis[i][j])

    for i in ans[1:]:
        print(i)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys;input=sys.stdin.readline
from heapq import *
def dijkstra(s,cost):
    d = [float("inf")] * NN
    used = [False] * NN
    d[s] = 0
    while True:
        v = -1
        for i in range(NN):
            if (not used[i]) and (v == -1):
                v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
            return d
        used[v] = True
        for j, c in cost[v]:
            d[j] = min(d[j],d[v]+c)

def dijkstra_heapq(s, cost):
    d = [float("inf")] * NN
    h = [(0, s)]
    d[s] = 0
    while h:
        vc, v = heappop(h)
#        print(h)
        if vc > d[v]:
            continue
        for j, c in cost[v]:
            if vc+c<d[j]:
                d[j] = vc+c
                heappush(h, (vc+c, j))
    return d

N,W,S = map(int,input().split())
V = 250
NN = N*(V+1)

def enc(u, v):
    return u*NN + v

#print(NN)
cost = [[] for _ in range(NN)]
for i in range(W):
    x,y,z,u = map(int,input().split())
    x -= 1
    y -= 1
    for v in range(V+1):
        if v-z>=0:
            cost[x*(V+1)+v].append((y*(V+1)+v-z, u))
            cost[y*(V+1)+v].append((x*(V+1)+v-z, u))

for i in range(N):
    x, y = map(int, input().split())
    for v in range(V+1):
        cost[i*(V+1)+v].append((i*(V+1)+min(v+x, V), y))

S = min(V, S)
d = dijkstra_heapq(S,cost)
for i in range(1, N):
    print(min(d[i*(V+1):(i+1)*(V+1)]))

Submission status: Wrong Answer

Solution code:
from networkx import*
R=range
(n,m,s),*t=[map(int,t.split())for t in open(0)]
x=51
r=R(0,x**3,x)
G=DiGraph()
G.add_nodes_from(range(x**3))
f=G.add_weighted_edges_from
for u,v,a,b in t[:m]:
 for i in r:f([(i+a*x+u,i+v,b),(i+a*x+v,i+u,b)])
i=0
for c,d in t[m:]:i+=1;f((j+i,j+c*x+i,d)for j in r)
d=single_source_dijkstra_path_length(G,min(x,s)*x+1)
for i in R(2,n+1):print(min(d[j]for j in R(i,x**3,x)))

Submission status: Wrong Answer

Solution code:
from networkx import*
R=range
(n,m,s),*t=[map(int,t.split())for t in open(0)]
x=51
r=R(0,x**3,x)
G=DiGraph()
f=G.add_weighted_edges_from
for u,v,a,b in t[:m]:
 for i in r:f([(i+a*x+u,i+v,b),(i+a*x+v,i+u,b)])
i=0
for c,d in t[m:]:i+=1;f((j+i,j+c*x+i,d)for j in r)
d=single_source_dijkstra_path_length(G,min(x,s)*x+1)
for i in R(2,n+1):print(min(d[j]for j in R(i,x**3,x)))

Submission status: Wrong Answer

Solution code:

import heapq
from collections import defaultdict
h = []
heapq.heapify(h)

n, m, s = list(map(int, input().split()))
a, b = [[None] * m for _ in range(2)]
c, d = [[None] * n for _ in range(2)]
ns = defaultdict(list)
uv2e = {}
for i in range(m):
    u,v,a[i],b[i] = list(map(int, input().split()))
    ns[u-1].append(v-1)
    ns[v-1].append(u-1)
    uv2e[u-1,v-1] = i
    uv2e[v-1,u-1] = i
for i in range(n):
    c[i], d[i] = list(map(int, input().split()))

# (t, u, ss, dd)
prevs = defaultdict(list)
heapq.heappush(h, (0, 0, s, set([0])))
prevs[0].append(set([0]))
done = set()
best_time = [10**100] * n
best_prev = [-1] * n
while h:
    t, u, ss, prev = heapq.heappop(h)
#     print("best: ", t, u, ss, prev)
    done.add(u)
    best_time[u] = min(t, best_time[u])
    best_prev[u] = prev
    if len(done)==n:
        break
    for v in ns[u]:
        e = uv2e[u,v]
        tmp_t = t + b[e]
        if ss>=a[e]:
            tmp_ss = s - a[e]
        else:
            tmp_ss = 0            
            tmp_t += min(((a[e] - ss) // c[item] + 1 - int((a[e] - ss) % c[item] == 0)) * d[item] for item in prev)
        tmp_prev = prev|set([v])
        if tmp_prev not in prevs[v]:
            heapq.heappush(h, (tmp_t, v, tmp_ss, tmp_prev))
            prevs[v].append(tmp_prev)
#             print((tmp_t, v, tmp_ss, tmp_cds, prev|set([v])))
print(*best_time[1:], sep="\n")

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from heapq import heappush, heappop

N,M,S = map(int,readline().split())
ABC = [list(map(int,readline().split())) for _ in range(M)]
m = map(int,read().split())
CD = list(zip(m,m))

graph = [[] for _ in range(N)]
for u,v,a,b in ABC:
    graph[u-1].append((v-1,a,b))
    graph[v-1].append((u-1,a,b))

def f():
  INF = 10 ** 18
  p = 1
  ans = []
  qq = 2500
  dist = [[INF] * qq for _ in range(N)]
  dist[0][min(qq-1,S)] = 0
  q = [(0,min(qq-1,S),0)]
  while q:
      st,ss,v = heappop(q) # 総時間、銀貨、今いる頂点
      if dist[v][ss] < st:
        continue
      if v == p:
        ans.append(st)
        if p == N-1:
          break
        p += 1
      c,d = CD[v]
      # 銀貨の購入
      if ss < qq-1:
          ns = min(ss + c, qq-1)
          nt = st + d
          if dist[v][ns] > nt:
              dist[v][ns] = nt
              heappush(q,(nt,ns,v))
      # 移動
      for nex,g,tt in graph[v]:
          if ss-g < 0:
              continue
          dt = st + tt
          if dist[nex][ss-g] <= dt:
              continue
          dist[nex][ss-g] = dt
          heappush(q,(dt,ss-g,nex))
  return ans
      
print(*f(),sep='\n')

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from heapq import heappush, heappop

N,M,S = map(int,readline().split())
ABC = [list(map(int,readline().split())) for _ in range(M)]
m = map(int,read().split())
CD = list(zip(m,m))

graph = [[] for _ in range(N)]
for u,v,a,b in ABC:
    graph[u-1].append((v-1,a,b))
    graph[v-1].append((u-1,a,b))

def f():
  INF = 10 ** 18
  p = 1
  ans = []
  qq = 2500
  dist = [[INF] * qq for _ in range(N)]
  dist[0][min(qq-1,S)] = 0
  q = [(0,min(qq-1,S),0)]
  while q:
      st,ss,v = heappop(q) # 総時間、銀貨、今いる頂点
      if dist[v][ss] < st:
        continue
      if v == p:
        ans.append(st)
        p += 1
        if p == N-1:
          break
      c,d = CD[v]
      # 銀貨の購入
      if ss < qq-1:
          ns = min(ss + c, qq-1)
          nt = st + d
          if dist[v][ns] > nt:
              dist[v][ns] = nt
              heappush(q,(nt,ns,v))
      # 移動
      for nex,g,tt in graph[v]:
          if ss-g < 0:
              continue
          dt = st + tt
          if dist[nex][ss-g] <= dt:
              continue
          dist[nex][ss-g] = dt
          heappush(q,(dt,ss-g,nex))
  return ans
      
print(*f(),sep='\n')