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: Time Limit Exceeded

Solution code:
import copy
import math

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

Us=[0]*M
Vs=[0]*M
As=[0]*M
Bs=[0]*M
for i in range(M):
    Us[i],Vs[i],As[i],Bs[i] = map(int,input().split())

# ---
V={}
Ns = max(As)*N
Nv=N*(Ns+1)
cnt=0
for i in range(1,N+1):
    for ns in range(Ns+1):
        V[(i,ns)]=cnt
        cnt+=1
#T= copy.copy(V)


if S > Ns:
    S = Ns

# --
w = [[math.inf]*Nv for _ in range(Nv) ]
# U <-> V
for _ in range(M):
    u = Us.pop()
    v = Vs.pop()
    a = As.pop()
    b = Bs.pop()
    #
    for i in range(Ns+1): # i = 0,..,Ns
        ns_s = Ns - i
        ns_g = ns_s - a
        if ns_g >= 0:
            # U -> V
            w[ V[(u,ns_s)] ][ V[(v,ns_g)] ] = b
            # V -> U
            w[ V[(v,ns_s)] ][ V[(u,ns_g)] ] = b
            #print(u,v,a,b,ns_s,ns_g,V[(u,ns_s)],V[(v,ns_g)])

# -----

for i in range(N):
    c,d = map(int,input().split())
    v = i+1
    for j in range(Ns): # j = 0,...,Ns-1
        ns_s = j
        ns_g = j + c
        if ns_g > Ns:
            ns_g = Ns
        w[ V[(v,ns_s)] ][ V[(v,ns_g)] ] = d

# -----
D=[-1]*Nv
# -----
T=list(range(Nv))

s=V[(1,S)]
T.remove(s) #del T[s]
D[s] = 0
for v in T:
    D[v] = w[ s ][ v ]
while len(T) > 0:
    u = min(T,key=lambda x:D[x])
    T.remove(u)
    for v in T:
        D[ v ] = min( D[ v ], D[ u ] + w[ u ][ v ] )

for i in range(2,N+1):
    ans = min([ D[ V[(i,ns)] ] for ns in range(Ns+1) ])
    print(ans)

Submission status: Time Limit Exceeded

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[node][min(silver+c[node],2500)]:
        heappush(hp,(time+d[node],min(silver+c[node],2500),node))
        
print(*mintimes[1:],sep="\n")

Submission status: Time Limit Exceeded

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
mintimes=[10**15]*n

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

Submission status: Time Limit Exceeded

Solution code:
import copy
import math

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

Us=[0]*M
Vs=[0]*M
As=[0]*M
Bs=[0]*M
for i in range(M):
    Us[i],Vs[i],As[i],Bs[i] = map(int,input().split())

# ---
V={}
Ns = max(As)*N
Nv=N*(Ns+1)
cnt=0
for i in range(1,N+1):
    for ns in range(Ns+1):
        V[(i,ns)]=cnt
        cnt+=1
T= copy.copy(V)

if S > Ns:
    S = Ns

# --
w = [[math.inf]*Nv for _ in range(Nv) ]
# U <-> V
for _ in range(M):
    u = Us.pop()
    v = Vs.pop()
    a = As.pop()
    b = Bs.pop()
    #
    for i in range(Ns+1): # i = 0,..,Ns
        ns_s = Ns - i
        ns_g = ns_s - a
        if ns_g >= 0:
            # U -> V
            w[ V[(u,ns_s)] ][ V[(v,ns_g)] ] = b
            # V -> U
            w[ V[(v,ns_s)] ][ V[(u,ns_g)] ] = b
            #print(u,v,a,b,ns_s,ns_g,V[(u,ns_s)],V[(v,ns_g)])

# -----

for i in range(N):
    c,d = map(int,input().split())
    v = i+1
    for j in range(Ns): # j = 0,...,Ns-1
        ns_s = j
        ns_g = j + c
        if ns_g > Ns:
            ns_g = Ns
        w[ V[(v,ns_s)] ][ V[(v,ns_g)] ] = d

# -----
D=[-1]*Nv
# -----
s=(1,S)
del T[s]
D[V[s]] = 0
for v in T:
    D[V[v]] = w[ V[s] ][ V[v] ]
while len(T) > 0:
    u,_ = min(T.items(),key=lambda x:D[x[1]])
    del T[u]
    for v in T:
        D[ V[v] ] = min( D[ V[v] ], D[ V[u] ] + w[ V[u] ][ V[v] ] )

for i in range(2,N+1):
    ans = min([ D[ V[(i,ns)] ] for ns in range(Ns+1) ])
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy
import math

def w(u,v):
    n1 = u[0]
    n2 = v[0]
    s1 = u[1]
    s2 = v[1]

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

Us=[0]*M
Vs=[0]*M
As=[0]*M
Bs=[0]*M


for i in range(M):
    Us[i],Vs[i],As[i],Bs[i] = map(int,input().split())

Cs=[0]*N
Ds=[0]*N
for i in range(N):
    Cs[i],Ds[i] = map(int,input().split())

# -----

V={}
Ns = max(As)*N
Nv=N*(Ns+1)
cnt=0
for i in range(1,N+1):
    for ns in range(Ns+1):
        V[(i,ns)]=cnt
        cnt+=1
T= copy.copy(V)

if S > Ns:
    S = Ns

# -----

w = [[math.inf]*Nv for _ in range(Nv) ]
# U <-> V
for _ in range(M):
    u = Us.pop()
    v = Vs.pop()
    a = As.pop()
    b = Bs.pop()
    #
    for i in range(Ns+1): # i = 0,..,Ns
        ns_s = Ns - i
        ns_g = ns_s - a
        if ns_g >= 0:
            # U -> V
            w[ V[(u,ns_s)] ][ V[(v,ns_g)] ] = b
            # V -> U
            w[ V[(v,ns_s)] ][ V[(u,ns_g)] ] = b
            #print(u,v,a,b,ns_s,ns_g,V[(u,ns_s)],V[(v,ns_g)])

# C,D
for i in range(N):
    c = Cs[i]
    d = Ds[i]
    v = i+1
    for j in range(Ns): # j = 0,...,Ns-1
        ns_s = j
        ns_g = j + c
        if ns_g > Ns:
            ns_g = Ns
        w[ V[(v,ns_s)] ][ V[(v,ns_g)] ] = d

# -----
D=[-1]*Nv
# -----
s=(1,S)
del T[s]
D[V[s]] = 0
for v in T:
    D[V[v]] = w[ V[s] ][ V[v] ]
while len(T) > 0:
    u,_ = min(T.items(),key=lambda x:D[x[1]])
    del T[u]
    for v in T:
        D[ V[v] ] = min( D[ V[v] ], D[ V[u] ] + w[ V[u] ][ V[v] ] )

for i in range(2,N+1):
    ans = min([ D[ V[(i,ns)] ] for ns in range(Ns+1) ])
    print(ans)

Submission status: Time Limit Exceeded

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
while flg:
    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: Time Limit Exceeded

Solution code:
import heapq
def main():
    N, M, S = map(int, input().split())
    maxS = 50 * (N-1)
    cost = [[] for _ in range(N)]
    for _ in range(M):
        U, V, A, B = map(int, input().split())
        U = U - 1
        V = V - 1
        cost[U].append((A,B,V))
        cost[V].append((A,B,U))
    for i in range(N):
        cost[i].sort()
    r = []
    for _ in range(N):
        C, D = map(int, input().split())
        r.append((C,D))
    time = [-1] * N
    money = [-1] * N
    used = set()
    cities = N
    q = [(0, S, 0)] # time, silver, city
    count = 0
    while cities:
        count += 1
        t, s, ci = heapq.heappop(q)
        if (s, ci) in used or money[ci] >= s:
            continue
        used.add((s, ci))
        if time[ci] == -1:
            time[ci] = t
            money[ci] = s
            cities -= 1
        for a, b, v in cost[ci]:
            if s < a:
                break
            if (s-a, v) not in used and money[v] < s-a:
                heapq.heappush(q, (t+b, s-a, v))
        if s != maxS:
            c, d = r[ci]
            if (s+c, ci) not in used:
                heapq.heappush(q, (t+d, s+c, ci))
    for i in time[1:]:
        print(i)
main()

Submission status: Time Limit Exceeded

Solution code:
import heapq
def main():
    N, M, S = map(int, input().split())
    maxS = 50 * (N-1)
    cost = [[] for _ in range(N)]
    for _ in range(M):
        U, V, A, B = map(int, input().split())
        U = U - 1
        V = V - 1
        cost[U].append((A,B,V))
        cost[V].append((A,B,U))
    for i in range(N):
        cost[i].sort()
    r = []
    for _ in range(N):
        C, D = map(int, input().split())
        r.append((C,D))
    time = [-1] * N
    used = set()
    cities = N
    q = [(0, S, 0)] # time, silver, city
    count = 0
    while cities:
        count += 1
        t, s, ci = heapq.heappop(q)
        if time[ci] == -1:
            time[ci] = t
            cities -= 1
        for a, b, v in cost[ci]:
            if s < a:
                break
            heapq.heappush(q, (t+b, s-a, v))
        if s != maxS:
            c, d = r[ci]
            heapq.heappush(q, (t+d, s+c, ci))
    for i in time[1:]:
        print(i)
main()

Submission status: Time Limit Exceeded

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
        ma = maxS
        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]
            heapq.heappush(cur, (t + d, u, min(s + c, maxS)))
    print('\n'.join(map(str, T[1:])))

main()

Submission status: Time Limit Exceeded

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][v - 1] = (a, b)
        AB[v - 1][u - 1] = (a, b)
        maxA = max(maxA, a)
    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
        c, d = CD[u]
        if s != maxS:
            heapq.heappush(cur, (t + d, u, min(s + c, maxS)))
        for v, (a, b) in AB[u].items():
            if s - a >= 0:
                heapq.heappush(cur, (t + b, v, s - a))
    print('\n'.join(map(str, T[1:])))

main()

Submission status: Time Limit Exceeded

Solution code:
N,M,S = map(int,input().split())
edges = [[] for _ in range(2500*50 + 100)]
def indexer(city,coin):
    return 50*coin + city

for _ in range(M):
    u,v,a,b = map(int,input().split())
    u -= 1
    v -= 1
    for scoin in range(a,2501):
        edges[indexer(u,scoin)].append([b,indexer(v,scoin-a)])
        edges[indexer(v,scoin)].append([b,indexer(u,scoin-a)])
## 両替
for i in range(N):
    c,d = map(int,input().split())
    for scoin in range(c,2501):
        edges[indexer(i,scoin-c)].append([d,indexer(i,scoin)])


def dijkstra(s,n,edges):
    import heapq
    dist = [float('inf')] * n
    fixed = [False]*n
    dist[s] = 0
    fixed[s] = True
    priority_que = []
    for e in edges[s]:
        heapq.heappush(priority_que,e)

    while len(priority_que):
        edge = heapq.heappop(priority_que)
        if fixed[edge[1]]:
            continue
        v = edge[1]
        dist[v] = edge[0]
        fixed[v] = True
        for ne in edges[v]:
            heapq.heappush(priority_que,[ne[0]+dist[v], ne[1]])
    return dist

d=dijkstra(indexer(0,min(2500,S)),2500*50 + 100,edges)
for i in range(1,N):
    ans = float('inf')
    for j in range(2501):
        ans = min(ans,d[indexer(i,j)])
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq

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

graph = [[] for _ in range(N)]
for _ in range(M):
	u, v, A, B = map(int, input().strip().split())
	u -= 1
	v -= 1
	graph[u].append((v, A, B))
	graph[v].append((u, A, B))

exchanges = []
for _ in range(N):
	C, D = map(int, input().strip().split())
	exchanges.append((C, D))

queue = [(0, 0, S)]

state_table = [[None] * (2500 + 1) for i in range(N)]

reached = [False] * N
reached_count = 0

while queue:
#	print(len(queue))
	time, cur, money = heapq.heappop(queue)
	if not reached[cur]:
		reached[cur] = True
		reached_count += 1
		if reached_count >= N:
			break
	count, d_time = exchanges[cur]
	for n, A, B in graph[cur]:
		n_money = money - A
		n_time = time + B
		states = state_table[n]
		max_fare = 2500
		while True:
			if n_money >= 0:
				if n_money > max_fare:
					n_money = max_fare
				if states[n_money] == None or states[n_money] > n_time:
					states[n_money] = n_time
					heapq.heappush(queue, (n_time, n, n_money))
				if n_money >= max_fare:
					break
			n_money += count
			n_time += d_time

#for i in range(N):
#	print(i, state_table[i])

for i in range(1, N):
	states = state_table[i]
	minimum = None
	for t in states:
		if t != None and (minimum == None or minimum > t):
			minimum = t
	print(minimum)

Submission status: Time Limit Exceeded

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

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

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

def addcand(st, nd, ns, d, conf, cands, prev, p):
    if checkcand(st, nd, ns, d, conf):
        if (st, ns) in d:
            pd = d[(st, ns)]
            if nd < pd:
                d[(st, 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) ]
prev = {}

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 = {}

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

    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, prev, (cst, curs))

#    print(cands)
#    print(d)    
                

#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: Time Limit Exceeded

Solution code:
from collections import deque
N, M, S = map(int, input().split())
Route = [[]for i in range(N)]
for i in range(M):
    U, V, A, B = map(int, input().split())
    Route[U-1].append((V-1, -1 * A, B))
    Route[V-1].append((U-1, -1 * A, B))
for i in range(N):
    C, D = map(int, input().split())
    Route[i].append((i, C, D))

city_silver_time = [[-1 for j in range(3000)]for i in range(N)]
Q = deque()
if S >= 3000:
    S = 2999
city_silver_time[0][S] = 0
Q.append((0, S, 0))

while len(Q) > 0:
    now, have, time = Q.popleft()
    for i in range(len(Route[now])):
        next, cost, take = Route[now][i]
        if (have + cost < 0) or (have + cost >= 3000):
            continue
        elif city_silver_time[next][have + cost] == -1:
            city_silver_time[next][have + cost] = time + take
            Q.append((next, have + cost, time + take))
        elif city_silver_time[next][have + cost] > time + take:
            city_silver_time[next][have + cost] = time + take
            Q.append((next, have + cost, time + take))

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

Submission status: Time Limit Exceeded

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, prev, p):
    if checkcand(st, nd, ns, d, conf):
        if (st, ns) in d:
            pd = d[(st, ns)]
            if nd < pd:
                d[(st, 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) ]
prev = {}

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, prev, (cst, curs))

    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, prev, (cst, curs))

#    print(cands)
#    print(d)    
                

#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: Time Limit Exceeded

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

(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:
            ns = curs - a
            if not (v, ns) in conf:
                if (v, curs - a) in d:
                    pd = d[(v, ns)]
                    if cd + b < pd:
                        d[(v, ns)] = cd + b
                        idx = bisect.bisect_left(cands, (pd, v, ns))
                        cands.pop(idx)
                        idx = bisect.bisect_left(cands, (cd + b, v, ns))
                        cands.insert(idx, (cd + b, v, ns))
                else:
                    d[(v, ns)] = cd + b
                    idx = bisect.bisect_left(cands, (cd + b, v, ns))
                    cands.insert(idx, (cd + b, v, ns))

    (exc, exd) = ex[cst]
    nd = cd
    ns = curs
    while True:
        ns += exc
        nd += exd
        if ns > maxs:
            ns = maxs
        if not (cst, ns) in conf:
            if (cst, ns) in d:
                pd = d[(cst, ns)]
                if nd < pd:
                    d[(cst, ns)] = nd
                    idx = bisect.bisect_left(cands, (pd, cst, ns))
                    cands.pop(idx)
                    idx = bisect.bisect_left(cands, (nd, cst, ns))
                    cands.insert(idx, (nd, cst, ns))
            else:
                d[(cst, ns)] = nd
                idx = bisect.bisect_left(cands, (nd, cst, ns))
                cands.insert(idx, (nd, cst, ns))
                
        if ns == maxs:
            break


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: Time Limit Exceeded

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))
                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]))

Submission status: Time Limit Exceeded

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

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

edges = []
for _ in range(M):
    u, v, a, b = map(int, readline().split())
    for coin in range(a, 2500):
        edges.append(((u, coin), (v, coin - a), b))
        edges.append(((v, coin), (u, coin - a), b))

for u in range(1, N + 1):
    c, d = map(int, readline().split())
    for coin in range(2500):
        edges.append(((u, coin), (u, min(coin + c, 2499)), d))

if S >= 2500:
    S = 2499


G = nx.DiGraph()
G.add_weighted_edges_from(edges)
path_lengths = nx.single_source_dijkstra_path_length(G, (1, S))

INF = 10 ** 18
answer = [INF] * (N + 1)
for key, L in path_lengths.items():
    u, c = key
    if answer[u] > L:
        answer[u] = L

print(*answer[2:], sep='\n')

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
sysread = sys.stdin.readline
from heapq import heappop, heappush

def run():
    N, M, S = list(map(int, sysread().split()))
    to = [[] for _ in range(N+1)]
    max_m = 2500
    for _ in range(M):
        u,m,a,b = list(map(int, sysread().split()))
        to[u].append((m,b,a))
        to[m].append((u,b,a))


    C, D = [0], [0]
    for _ in range(N):
        c,d = list(map(int, sysread().split()))
        C.append(c)
        D.append(d)

    queue = []
    # (time, node, rest-coin)
    if S > max_m: S = max_m
    heappush(queue, (0, 1, S))

    #state = [[1<<61] * (max_m+1) for _ in range(N+1)]
    state = [float('inf') for _ in range(N+1)]
    update = [False for _ in range(N+1)]
    nodes = [0] * N
    #while queue:
    while nodes:
        time, node, coin = heappop(queue)

        if not update[node]:
            state[node] = min(state[node], time)
            update[node] = True
            nodes.pop()

        #if state[node][coin] < time: continue
        #if coin + C[node] <= max_m and time + D[node] < state[node][coin+C[node]]:
        if coin + C[node] <= max_m:
            #state[node][coin+C[node]] = time + D[node]
            heappush(queue, (time+D[node], node, coin+C[node]))
        for n_node, n_time, n_coin in to[node]:
            #if coin >= n_coin and state[n_node][coin-n_coin] > n_time + time:
            if coin >= n_coin:
                #state[n_node][coin - n_coin] = n_time + time
                heappush(queue, (time + n_time, n_node, coin - n_coin))

    for s in state[2:]:
        #print(min(s))
        print(s)
if __name__ == "__main__":
    run()