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 heapq import heapify, heappop, heappush
import sys
input = sys.stdin.readline

DEBUG = False
INF = float('inf')
MAX_N = 50
MAX_A = 50

N, M, S = map(int, input().split())
U = []
V = []
A = []
B = []
C = []
D = []

connect = [[] for _ in range(N)]
for _ in range(M):
    u, v, a, b = map(int, input().split())
    U.append(u)
    V.append(v)
    A.append(a)
    B.append(b)
    connect[u-1].append([v-1, a, b])
    connect[v-1].append([u-1, a, b])
for _ in range(N):
    c, d = map(int, input().split())
    C.append(c)
    D.append(d)

if DEBUG:
    print("U: {}".format(U))
    print("V: {}".format(V))
    print("A: {}".format(A))
    print("B: {}".format(B))
    print("C: {}".format(C))
    print("D: {}".format(D))
    print("connect: {}".format(connect))

MAX_N = N
MAX_A = max(A)
MAX_MONEY = MAX_N * MAX_A
S = min(S, MAX_MONEY-1)

node = [INF for _ in range(MAX_MONEY * N)]
node[0] = 0

hq = []
heappush(hq, (0, S))
while hq:
    time, current_node = heappop(hq)
    if DEBUG:
        print("time: {}, current_node: {}, len(hq): {}".format(time, current_node, len(hq)))
    if time < node[current_node]:
        node[current_node] = time
    else:
        continue
    index_city = current_node // MAX_MONEY
    money = current_node % MAX_MONEY

    for index_next_city, a, b in connect[index_city]:
        if money >= a and time+b < node[index_next_city*MAX_MONEY + money-a]:
            heappush(hq, (time+b, index_next_city*MAX_MONEY + money-a))
    if money < MAX_MONEY-1:
        heappush(hq, (time+D[index_city], min(money+C[index_city], MAX_MONEY-1)+MAX_MONEY*index_city))

for i in range(1,N):
    print(min(node[MAX_MONEY*i:MAX_MONEY*(i+1)]))

Submission status: Wrong Answer

Solution code:
import heapq


dp = {}
hq = []

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

MAX_S = (N-1)*50
S = min(S, MAX_S)

for i in range(1,N+1):
    dp[i] = {}
    for j in range(MAX_S+1):
        dp[i][j] = 10**10

uv = {}
for i in range(N):
    uv[i+1] = []
for i in range(M):
    U, V, A, B = map(int, input().split())
    uv[U].append((V,A,B))
    uv[V].append((U,A,B))

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

def q_push(v, money, time):
    if money < 0:
        return 
    if dp[v][money] <= time:
        return
    dp[v][money] = time
    heapq.heappush(hq, (time, v, money))


q_push(1,S,0)
while hq:
    now_t, now_v, now_m = heapq.heappop(hq)

    if dp[now_v][now_m] != now_t:
        continue

    new_money = min(now_m+c[now_v],MAX_S)
    q_push(now_v,new_money,now_t+d[now_v])
    for next_v, next_a, next_b in uv[now_v]:
        q_push(next_v,now_m-next_a,now_t+next_b)

for i in range(2, N+1):
    ans = 10**10
    for j in range(0, MAX_S+1):
        ans = min(ans, dp[i][j])
    
    print(ans)

Submission status: Wrong Answer

Solution code:
import heapq


dp = {}
hq = []

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

MAX_S = (N-1)*50
S = min(S, MAX_S)

for i in range(1,N+1):
    dp[i] = {}
    for j in range(MAX_S+1):
        dp[i][j] = 10**9*N

uv = {}
for i in range(N):
    uv[i+1] = []
for i in range(M):
    U, V, A, B = map(int, input().split())
    uv[U].append((V,A,B))
    uv[V].append((U,A,B))

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

def q_push(v, money, time):
    if money < 0:
        return 
    if dp[v][money] <= time:
        return
    dp[v][money] = time
    heapq.heappush(hq, (time, v, money))


q_push(1,S,0)
while hq:
    now_t, now_v, now_m = heapq.heappop(hq)

    if dp[now_v][now_m] != now_t:
        continue

    new_money = min(now_m+c[now_v],MAX_S)
    q_push(now_v,new_money,now_t+d[now_v])
    for next_v, next_a, next_b in uv[now_v]:
        q_push(next_v,now_m-next_a,now_t+next_b)

for i in range(2, N+1):
    ans = 10**9*N
    for j in range(0, MAX_S+1):
        ans = min(ans, dp[i][j])
    
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys,math,copy,queue,itertools,bisect,collections
from heapq import *
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
INF = 10**12

N,M,S = LI()
if S > N * 50:
    S = N * 50
root = [[] for _ in range(N)]
for _ in range(M):
    u,v,a,b = LI()
    root[u-1].append((v-1,a,b))
    root[v-1].append((u-1,a,b))
city = [LI() for _ in range(N)]

dp = [[INF] * (N*50+1) for _ in range(N)]
dp[0][S] = 0

hq = [[0,0,S]]
heapify(hq)

while hq:
    tm,pos,coin = heappop(hq)

    c = coin
    t = tm
    if c < N * 50:
        c += city[pos][0]
        c = min(c, N * 50)
        t += city[pos][1]
        if dp[pos][c] > t:
            dp[pos][c] = t
            heappush(hq,[t,pos,c])

    for p,a,b in root[pos]:
        c = coin - a
        if c >= 0:
            if dp[p][c] > tm + b:
                dp[p][c] = tm + b
                heappush(hq,[tm+b,p,c])

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

Submission status: Wrong Answer

Solution code:
import sys,math,copy,queue,itertools,bisect,collections
from heapq import *
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
INF = 10**12

N,M,S = LI()
if S > (N-1) * 50:
    S = (N-1) * 50
root = [[] for _ in range(N)]
for _ in range(M):
    u,v,a,b = LI()
    root[u-1].append((v-1,a,b))
    root[v-1].append((u-1,a,b))
city = [LI() for _ in range(N)]

dp = [[INF] * (N*50) for _ in range(N)]
dp[0][S] = 0

hq = [[0,0,S]]
heapify(hq)

while hq:
    tm,pos,coin = heappop(hq)

    c = coin
    t = tm
    while c < (N-1) * 50:
        c += city[pos][0]
        c = min(c, (N-1) * 50) 
        t += city[pos][1]
        if dp[pos][c] > t:
            dp[pos][c] = t
            heappush(hq,[t,pos,c])

    for p,a,b in root[pos]:
        c = coin - a
        if c >= 0:
            if dp[p][c] > tm + b:
                dp[p][c] = tm + b
                heappush(hq,[tm+b,p,c])

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

Submission status: Wrong Answer

Solution code:
import sys,math,copy,queue,itertools,bisect,collections
from heapq import *
sys.setrecursionlimit(10**7)
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
_LI = lambda : [int(x)-1 for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())
INF = 10**12

N,M,S = LI()
if S > (N-1) * 50:
    S = (N-1) * 50
root = [[] for _ in range(N)]
for _ in range(M):
    u,v,a,b = LI()
    root[u-1].append((v-1,a,b))
    root[v-1].append((u-1,a,b))
city = [LI() for _ in range(N)]

dp = [[INF] * (N*50) for _ in range(N)]

hq = [[0,0,S]]
heapify(hq)

while hq:
    tm,pos,coin = heappop(hq)

    c = coin
    t = tm
    while c + city[pos][0] <= (N-1) * 50:
        c += city[pos][0]
        t += city[pos][1]
        if dp[pos][c] > t:
            dp[pos][c] = t
            heappush(hq,[t,pos,c])

    for p,a,b in root[pos]:
        c = coin - a
        if c >= 0:
            if dp[p][c] > tm + b:
                dp[p][c] = tm + b
                heappush(hq,[tm+b,p,c])

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

Submission status: Wrong Answer

Solution code:
from heapq import *
n,m,s=map(int,input().split())
c=[0]*n
d=[0]*n
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))
for i in range(n):
    c[i],d[i]=map(int,input().split())

flag=0 #if this == (1<<n)-1 then finish roop
endflag=[[False]*2501 for i in range(n)]
mintimes=[10**15]*n

hp=[(0,min(2500,s),0)]#(time,silver,node)
while flag!=((1<<n)-1):
    time,silver,node = heappop(hp)
    flag=flag|(1<<node)
    endflag[node][silver]=True
    mintimes[node]=min(mintimes[node],time)
    for atnode,costmoney,costtime in g[node]:
        if costmoney<=silver and not endflag[atnode][silver-costmoney]:
            heappush(hp,(time+costtime,silver-costmoney,atnode))
    if silver!=2500 and not endflag[atnode][min(silver+c[node],2500)]:
        heappush(hp,(time+d[node],min(silver+c[node],2500),node))
        
print(*mintimes[1:],sep="\n")

Submission status: Wrong Answer

Solution code:
n, m, s = map(int, input().split())

lines = [0]*m # city1, city2, silv, time
chg = [0]*n # silv, time
for i in range(m):
    lines[i] = tuple(map(int, input().split()))
for i in range(n):
    chg[i] = tuple(map(int, input().split()))
    
smax = sum([l[2] for l in lines])
def dik(key, val):
    org = dic_state.get(key, 10**18)
    dic_state[key] = min( org , val )
    return val < org
dic_state = {(1,s):0}
flg = True
for k in range(2*n):
    flg = False
    for state in list(dic_state.keys()):
        ds = chg[state[0]-1][0]
        dt = chg[state[0]-1][1]
        for i in range(1,smax+1-state[1]):
            if dt*i > smax:
                break
            flg = flg or dik((state[0], state[1] + ds * i), dic_state[state] + dt * i)
        for l in lines:
            if state[0] == l[0] and (state[1] >= l[2]):
                flg = flg or dik((l[1], state[1] - l[2]), dic_state[state] + l[3])
            if (state[0] == l[1]) and (state[1] >= l[2]):
                flg = flg or dik((l[0], state[1] - l[2]), dic_state[state] + l[3])

for i in range(2,n+1):
    print(min([dic_state.get((i,j), 10**18) for j in range(smax)]))

Submission status: Wrong Answer

Solution code:
n, m, s = map(int, input().split())
 
lines = [0]*m # city1, city2, silv, time
chg = [0]*n # silv, time
for i in range(m):
    lines[i] = tuple(map(int, input().split()))
for i in range(n):
    chg[i] = tuple(map(int, input().split()))
    
smax = sum([l[2] for l in lines])
def dik(key, val):
    org = dic_state.get(key, 10**18)
    dic_state[key] = min( org , val )
    return val < org
dic_state = {(1,s):0}
flg = True
for k in range(2*n):
    flg = False
    for state in list(dic_state.keys()):
        for i in range(1,smax+1-state[1]):
            dt = chg[state[0]-1][1] * ((i + chg[state[0]-1][0]-1) // chg[state[0]-1][0])
            flg = flg or dik((state[0], state[1] + i), dic_state[state] + dt)
        for l in lines:
            if state[0] == l[0] and (state[1] >= l[2]):
                flg = flg or dik((l[1], state[1] - l[2]), dic_state[state] + l[3])
            if (state[0] == l[1]) and (state[1] >= l[2]):
                flg = flg or dik((l[0], state[1] - l[2]), dic_state[state] + l[3])

for i in range(2,n+1):
    print(min([dic_state.get((i,j), 10**18) for j in range(smax)]))

Submission status: Wrong Answer

Solution code:
from scipy.sparse import*
(n,m,s,*D),*t=[map(int,t.split())for t in open(0)]
R,C=[],[]
for u,v,a,b in t[:m]:
    for i in range(2501-a):
        R+=(i+a)*51+u,(i+a)*51+v
        C+=i*51+v,i*51+u
        D+=b,b
for i,(c,d)in enumerate(t[m:],1):
    for j in range(2501-c):
        R+=j*51+i,
        C+=(j+c)*51+i,
        D+=d,
d=csgraph.dijkstra(csr_matrix((D,(R,C)),[8**6]*2),1,min(2500,s)*51+1)
for i in range(2,n+1):print(min(d[i::51]))

Submission status: Wrong Answer

Solution code:
import sys,bisect,string,math,time,functools,random
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
def Golf():*a,=map(int,open(0))
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            a,b,c=(inp+[1])[:3]
            org_inp.append(inp)
        else:
            #index=0
            a,b,c=(list(ls[i])+[1])[:3]
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0}):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0}) # sample usage
    mp=[1]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[1]+[mp_def[j] for j in s]+[1]
    mp+=[1]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)];rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
input=lambda: sys.stdin.readline().rstrip()

class Comb:
    def __init__(self,n,mo=10**9+7):
        self.fac=[0]*(n+1)
        self.inv=[1]*(n+1)
        self.fac[0]=1
        self.fact(n)
        for i in range(1,n+1):
            self.fac[i]=i*self.fac[i-1]%mo
            self.inv[n]*=i
            self.inv[n]%=mo
        self.inv[n]=pow(self.inv[n],mo-2,mo)
        for i in range(1,n):
            self.inv[n-i]=self.inv[n-i+1]*(n-i+1)%mo
        return
    
    def fact(self,n):
        return self.fac[n]
        
    def invf(self,n):
        return self.inv[n]

    def comb(self,x,y):
        if y<0 or y>x:
            return 0
        return self.fac[x]*self.inv[x-y]*self.inv[y]%mo

show_flg=False
show_flg=True

class Tree:
    def __init__(self,inp_size=None,init=True):
        if init:
            self.stdin(inp_size)
        return

    def stdin(self,inp_size=None):
        if inp_size==None:
            self.size=int(input())
        else:
            self.size=inp_size
        self.edges,_=GI(self.size,self.size-1)
        return
    
    def listin(self,ls):
        self.size=len(ls)+1
        self.edges,_=GI(self.size,self.size-1,ls)
        return

    def __str__(self):
        return  str(self.edges)

    def dfs(self,x,func=lambda prv,nx,dist:prv+dist,root_v=0):
        q=deque()
        q.append(x)
        v=[-1]*self.size
        v[x]=root_v
        while q:
            c=q.pop()
            for nb,d in self.edges[c]:
                if v[nb]==-1:
                    q.append(nb)
                    v[nb]=func(v[c],nb,d)
        return v

    def EulerTour(self,x,func=lambda prv,nx,dist:prv+dist,root_v=0):
        q=deque()
        q.append((-1,x))
        v=[None]*self.size
        v[x]=root_v
        et=[]
        while q:
            cb,ce=q.pop()
            et.append(ce)
            for nb,d in self.edges[ce]:
                if v[nb]==None:
                    q.append((nb,ce))
                    q.append((ce,nb))
                    v[nb]=func(v[ce],nb,d)
        vid=[[-1,-1]for i in range(self.size)]
        for i,j in enumerate(et):
            if vid[j][0]==-1:
                vid[j][0]=i
            else:
                vid[j][1]=i
        return v,et,vid
    
    def LCA_init(self,depth,et):
        self.st=SegTree(self.size*2-1,func=min,ide=inf)
        for i,j in enumerate(et):
            self.st.update(i,j)
        self.LCA_init_stat==True
        return
    
    def LCA(self,root,x,y):
        if self.LCA_init_stat==False:
            depth,et,vid=self.EulerTour(root)
            self.LCA_init(depth,et)
        return self.st.query(x,y+1)


def dijkstra(edge,st):
    # edge=[[(v_to,dist_to_v),...],[],...]
    # initialize: def: d=dist(st,i), prev=[previous vertex in minimum path], q[]
    n=len(edge)
    d=[(0 if st==i else 1<<33) for i in range(n)]
    prev=[0]*n
    q=[(j,i) for i,j in enumerate(d)]
    heapify(q)
    remain=set(range(n))
    # calc
    while q:
        dist,cur=heappop(q)
        if cur not in remain:
            continue
        remain.remove(cur)
        for dst,dist in edge[cur]:
            alt=d[cur]+dist
            if alt<d[dst]:
                d[dst]=alt
                prev[dst]=cur
                heappush(q,(alt,dst))
    return d,prev


n,m,s=LI()
t_ls=[]
k=1+n*50
s=min(k-1,s)
for i in range(m):
    u,v,a,b=LI()
    u-=1
    v-=1
    for j in range(a,k):
        t_ls+=[(u*k+j,v*k+j-a,b)]
        t_ls+=[(v*k+j,u*k+j-a,b)]

for i in range(n):
    c,d=LI()
    for j in range(k):
        t_ls+=[(i*k+j,i*k+min(j+c,k-1),d)]

gt,_=GI(n*k,len(t_ls),ls=t_ls,Directed=True,index=0)
dist_t,_=dijkstra(gt,0*k+s)

for i in range(1,n):
    print(min(dist_t[i*k:-~i*k]))

Submission status: Wrong Answer

Solution code:
import heapq

def main():
    N, M, S = map(int, input().split())
    AB = [[] for _ in range(N)]
    maxA = 0
    for _ in range(M):
        u, v, a, b = map(int, input().split())
        AB[u - 1].append((a, b, v - 1))
        AB[v - 1].append((a, b, u - 1))
        maxA = max(maxA, a)
    for i in range(N):
        AB[i].sort()

    CD = [tuple(map(int, input().split())) for _ in range(N)]
    maxS = N * maxA
    cur = [(0, 0, S)]  # (time, station, silver)
    T = [-1] * N
    tc = N
    visited = set()
    while tc:
        t, u, s = heapq.heappop(cur)
        if (u, s) in visited:
            continue
        visited.add((u, s))
        if T[u] == -1:
            T[u] = t
            tc -= 1
        for a, b, v in AB[u]:
            if s < a:
                break
            heapq.heappush(cur, (t + b, v, s - a))
        if s != maxS:
            c, d = CD[u]
            min_a = AB[u][0][0]
            k = max(1, (s - min_a + c  - 1) // c)
            heapq.heappush(cur, (t + k * d, u, min(s + k * c, maxS)))
    print('\n'.join(map(str, T[1:])))

main()

Submission status: Wrong Answer

Solution code:
import heapq
INF = 10**10

N, M, S = map(int, input().split())
adj = [[] for _ in range(N)]
for m in range(M):
    u,v,a,b = map(int, input().split())
    u -= 1
    v -= 1
    adj[u].append((v,a,b))
    adj[v].append((u,a,b))

C = []
D = []
for n in range(N):
    c, d = map(int, input().split())
    C.append(c)
    D.append(d)

M = 2500
S = min(S, M-1) # 2500枚あれば十分
dist = [[INF]*M for _ in range(N)] # dist[都市][銀貨の枚数]
dist[0][S] = 0
q = [(0,S,0)] # (距離、銀貨の枚数、都市)

while q:
    d, sil, node = heapq.heappop(q)
    if dist[node][sil] < d: # 探索の対象にする必要があるか確認
        continue 
    if sil+C[node] < M and d+D[node] < dist[node][sil+C[node]]:
        dist[node][sil+C[node]] = d + D[node]
        heapq.heappush(q, (d + D[node], sil+C[node] ,node))
    for to,a,b in adj[node]:
        if sil >= a and d + b < dist[to][sil-a]:
            dist[to][sil-a] = d + b
            heapq.heappush(q, (d + b, sil-a ,to))

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

Submission status: Wrong Answer

Solution code:
import heapq

def main():
    N, M, S = map(int, input().split())
    AB = [[] for _ in range(N)]
    maxA = 0
    for _ in range(M):
        u, v, a, b = map(int, input().split())
        AB[u - 1].append((a, b, v - 1))
        AB[v - 1].append((a, b, u - 1))
        maxA = max(maxA, a)
    for i in range(N):
        AB[i].sort()

    CD = [tuple(map(int, input().split())) for _ in range(N)]
    maxS = N * maxA
    cur = [(0, 0, S)]  # (time, station, silver)
    T = [-1] * N
    tc = N
    while tc:
        t, u, s = heapq.heappop(cur)
        if T[u] == -1:
            T[u] = t
            tc -= 1
        for a, b, v in AB[u]:
            if s < a:
                break
            heapq.heappush(cur, (t + b, v, s - a))
        if s != maxS:
            c, d = CD[u]
            min_a = AB[u][0][0]
            k = max(1, (s - min_a + c  - 1) // d)
            heapq.heappush(cur, (t + k * d, u, min(s + k * c, maxS)))
    print('\n'.join(map(str, T[1:])))

main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3
import bisect

def checkcand(st, nd, ns, d, conf):
    if (st, ns) in conf:
        return False

    for (cst, cns) in conf:
        if st == cst:
            cnd = d[(cst, cns)]
            if cns >= ns and cnd <= nd:
                return False
    
    return True

def addcand(st, nd, ns, d, conf, cands):
    if checkcand(st, nd, ns, d, conf):
        if (st, ns) in d:
            pd = d[(st, ns)]
            if nd < pd:
                d[(v, ns)] = nd
                idx = bisect.bisect_left(cands, (pd, st, ns))
                cands.pop(idx)
                idx = bisect.bisect_left(cands, (nd, st, ns))
                cands.insert(idx, (nd, st, ns))
        else:
            d[(st, ns)] = nd
            idx = bisect.bisect_left(cands, (nd, st, ns))
            cands.insert(idx, (nd, st, ns))


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

rs = [ [] for i in range(n + 1) ]

ma = 0
for i in range(m):
    (u, v, a, b) = map(int, input().split())
    rs[u].append((v, a, b))
    rs[v].append((u, a, b))
    ma = max(ma, a)

maxs = ma * (n - 1)

ex = [ () ]
for i in range(n):
    ex.append(tuple(map(int, input().split())))

d = {}
d[(1, s)] = 0
cands = [(0, 1, s)]
conf = set()

while cands:
    (cd, cst, curs) = cands.pop(0)
    conf.add((cst, curs))
    
    for (v, a, b) in rs[cst]:
        if a <= curs:
            addcand(v, cd + b, curs - a, d, conf, cands)

    if curs < maxs:
        (exc, exd) = ex[cst]
        nd = cd + exd                    
        ns = curs + exc
        if ns > maxs:
            ns = maxs
        addcand(cst, nd, ns, d, conf, cands)

#    print(cands)
#    print(d)    
                
    
cst = 1
md = -1
for (st, cs) in sorted(d.keys()):
    if cst != st:
        if cst > 1:
            print(md)
        md = -1
        cst = st
    
    if md == -1:
        md = d[(st, cs)]
    else:
        md = min(md, d[(st, cs)])


print(md)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from operator import mul


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n, m, s = LI()
G = [[] for _ in range(n)]
for _ in range(m):
    u, v, a, b = LI()
    G[u - 1] += [(v - 1, a, b)]
    G[v - 1] += [(u - 1, a, b)]

change = LIR(n)

def dijkstra(s):
    hq = [(0, 0, s)]
    dist = [[INF] * 2451 for _ in range(n)]
    dist[0][s] = 0
    checked = [[0] * 2451 for _ in range(n)]
    while hq:
        start_time, u, start_money = heappop(hq)
        if checked[u][start_money]:
            continue
        checked[u][start_money] = 1
        for v, c, d in G[u]:
            time = start_time
            money = start_money
            while True:
                if money >= c and time + d < dist[v][money - c]:
                    dist[v][money - c] = time + d
                    heappush(hq, (time + d, v, money - c))
                else:
                    break
                money += change[u][0]
                time += change[u][1]
                if money > 2450:
                    break
                if dist[u][money] > time:
                    dist[u][money] = time
                    heappush(hq, (time, u, money))
                else:
                    break
    return dist

D = dijkstra(min(2450, s))
for t in range(1, n):
    print(min(D[t]))