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 heapq
import os
from collections import defaultdict

import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353


N, M, S = list(map(int, sys.stdin.buffer.readline().split()))
UVAB = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(M)]
CD = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(N)]
CD = [(0, 0)] + CD

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

mada = set(list(range(2, N + 1)))
heap = [(0, 1, S)]
# dp[v, s]: v にお金を s 持ってる状態で来たときの最小値
dp = defaultdict(lambda: INF)
dp[1, S] = 0
while heap and mada:
    d, v, s = heapq.heappop(heap)
    if d > dp[v, s]:
        continue
    if v in mada:
        mada.remove(v)
    for u, a, b in graph[v]:
        if s - a < 0:
            continue
        if d + b < dp[u, s - a]:
            dp[u, s - a] = d + b
            heapq.heappush(heap, (d + b, u, s - a))
    c, dd = CD[v]
    if d + dd < dp[v, s + c]:
        dp[v, s + c] = d + dd
        heapq.heappush(heap, (d + dd, v, s + c))

ans = [INF] * (N + 1)
ans[1] = 0
for (v, s), d in dp.items():
    ans[v] = min(ans[v], d)
print(*ans[2:], sep='\n')

Submission status: Time Limit Exceeded

Solution code:
import heapq


n, m, s = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]
change = [list(map(int, input().split())) for i in range(n)]
INF = 10 ** 18

graph = [[] for i in range(n)]
for u, v, cost, time in info:
    u -= 1
    v -= 1
    graph[u].append((v, cost, time))
    graph[v].append((u, cost, time))

    
dist = [INF] * (3001 * n)
dist[min(s, 3000)] = 0

q = [(0, min(s, 3000), 0)] # q = [(時間, 銀貨, 現在地)]
while q:
    d, gin, v = heapq.heappop(q)

    if dist[v * 3001 + gin] < d:
        continue

    cc, dd = change[v]
    tmp = gin
    r = [gin]
    while True:
        if tmp + cc <= 3000:
            if dist[v * 3001 + tmp + cc] > dist[v * 3001 + tmp] + dd:
                dist[v * 3001 + tmp + cc] = dist[v * 3001 + tmp] + dd
                r.append(tmp)
            else:
                break
            tmp += cc
        else:
            break

    for nxt_v, cost, time in graph[v]:
        for g in r:
            if g - cost < 0:
                continue
            if dist[v * 3001 + g] + time < dist[nxt_v * 3001 + g - cost]:
                dist[nxt_v * 3001 + g - cost] = dist[v * 3001 + g] + time
                heapq.heappush(q, (dist[nxt_v * 3001 + g - cost], g - cost, nxt_v))

for i in range(1, n):
     print(min(dist[i * 3001:(i + 1) * 3001]))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from queue import PriorityQueue as PQ

N, M, S = map(int, input().split())
edge = defaultdict(lambda: defaultdict(dict))
max_price = 0
for _ in range(M):
    u, v, a, b = map(int, input().split())
    edge[u][v] = (a, b)
    edge[v][u] = (a, b)
    max_price += a
exchange = {}
for i in range(1, N + 1):
    c, d = map(int, input().split())
    exchange[i] = (c, d)

queue = PQ()
# queue of (<time>, <position>, <money>)
queue.put((0, 1, S))
ans = {1: 0}
done = {(0, 1, S)}
while len(ans) < N:
    t, pos, money = queue.get()
    if pos not in ans:
        ans[pos] = t

    for city in edge[pos]:
        a, b = edge[pos][city]
        key = (t + b, city, money - a)
        if a <= money and key not in done:
            done.add(key)
            queue.put(key)

    c, d = exchange[pos]
    n = 1
    while money + n * c <= max_price:
        key = (t + n * d, pos, money + n * c)
        if key not in done:
            done.add(key)
            queue.put(key)
        n += 1

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

Submission status: Time Limit Exceeded

Solution code:
import heapq
def Dijkstra(edge,start):
    d = [float('inf')]*n
    d[start] = 0
    pq = [(0,start)]
    heapq.heapify(pq)
    while pq:
        dist,p = heapq.heappop(pq)
        for to,cost in edge[p].items():
            if d[to] <= dist + cost:continue
            d[to] = dist + cost
            heapq.heappush(pq, (d[to], to))
    return d

def Dijkstra(start):
    inf = float('inf')
    d = [[inf]*(A+1) for _ in range(n)]
    d[start][min(s,A)] = 0
    pq = [(0,start,min(s,A))]
    heapq.heapify(pq)
    while pq:
        dist,p,money = heapq.heappop(pq)
        while True:
            if money >= A:
                money = A
            for to,(cost,time) in path[p].items():
                if money < cost or d[to][money - cost] <= dist + time:continue
                d[to][money - cost] = dist + time
                heapq.heappush(pq, (d[to][money - cost],to,money - cost))
            if money == A:break
            money += C[p]
            dist += D[p]
        m = inf
    return d

n,m,s = map(int,input().split())
path = [{} for _ in range(n)]
A = 0
for i in range(m):
    u,v,a,b = map(int,input().split())
    A += a
    u -= 1
    v -= 1
    path[u][v] = (a,b)
    path[v][u] = (a,b)
A *= 2
C = [0]*n
D = [0]*n
for i in range(n):
    C[i],D[i] = map(int,input().split())
ans = Dijkstra(0)
for a in ans[1:]:
    print(min(a))

Submission status: Time Limit Exceeded

Solution code:
def Int():
    return int(input())
def Ints():
    return map(int,input().split())
def IntList():
    return list(Ints())
def IntMat(N):
    return [IntList() for i in range(N)]

N,M,S = Ints()
from collections import defaultdict
Graph  = defaultdict(list)

for i in range(M):
    u,v,a,b = Ints()
    Graph[u].append([v,a,b])
    Graph[v].append([u,a,b])

City = [0]*N
for i in range(N):
    c,d = Ints()
    City[i] = [c,d]

import heapq
visited = [-1]*(N+1)
visited[0] = 1
que = []
# [time, nowhere, money, flag, visited]
heapq.heappush(que, [0, 1, S, 0])
ans = [-1]*(N+1)
#print(Graph)
while visited != [1]*(N+1):
    #print(que)
    time, nowhere, money, flag = heapq.heappop(que)
    #print(time, nowhere, money, flag)
    #route[nowhere] = 1
    if visited[nowhere] == -1:
        visited[nowhere] = 1
        ans[nowhere] = time
    if flag == 0:
        c,d = City[nowhere-1]
        if money >= 5000:
            heapq.heappush(que, [time+d, nowhere, money+c, 1])
        else:
            heapq.heappush(que, [time+d, nowhere, money+c, 0])
    for (to,a,b) in Graph[nowhere]:
        #if not to in route:
        if money-a >= 0:
          heapq.heappush(que, [time+b, to, money-a, flag])
            
for i in range(2,N+1):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
n,m,s = map(int,input().split())
road = [[] for _ in range(n)]
#print(road)
for _ in range(m):
  u,v,a,b = map(int,input().split())
  u -= 1
  v -= 1
  road[u].append([v,a,b])
  road[v].append([u,a,b])
#print(road)
coin = []
for _ in range(n):
  c,d = map(int,input().split())
  coin.append([c,d])
if s >= 2500:
  s = 2499
inf = 10**18
#print('#')
arr = [[inf for _ in range(2500)] for _ in range(n)]
c,d = coin[0]
#print(c,d)
#print(len(arr[0]))
for i in range(2500):
  if i <= s:
    arr[0][i] = 0
  elif i - c < 0:
    arr[0][i] = arr[0][0]+d
  else:
    arr[0][i] = arr[0][i-c]+d
now = {0}
#print(road)
for _ in range(2500):
  #print(now)
  last = now
  now = set()
  for x in last:
    for y in road[x]:
      #print('#',x,y)
      v,a,b = y
      now.add(v)
      c,d = coin[v]
      for i in range(2500):
        if i + a < 2500:
          arr[v][i] = min(arr[v][i],arr[x][i+a]+b)
      for i in range(2500):
        if i - c < 0:
          arr[v][i] = min(arr[v][i],arr[v][0]+d)
        else:
          arr[v][i] = min(arr[v][i],arr[v][i-c]+d)
for ii in range(1,n):
  print(arr[ii][0])
#print(arr[0])

Submission status: Time Limit Exceeded

Solution code:
import heapq


n, m, s = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]
change = [list(map(int, input().split())) for i in range(n)]
INF = 10 ** 18

graph = [[] for i in range(n)]
for u, v, cost, time in info:
    u -= 1
    v -= 1
    graph[u].append((v, cost, time))
    graph[v].append((u, cost, time))
    
dist = [[INF] * 3001 for i in range(n)]
dist[0][min(s, 3000)] = 0

q = [(0, min(s, 3000), 0)] # q = [(時間, 銀貨, 現在地)]
while q:
    d, gin, v = heapq.heappop(q)

    if dist[v][gin] < d:
        continue

    cc, dd = change[v]
    tmp = gin
    r = [gin]
    while True:
        if tmp + cc <= 3000:
            if dist[v][tmp + cc] > dist[v][tmp] + dd:
                dist[v][tmp + cc] = dist[v][tmp] + dd
                r.append(tmp)
            else:
                break
            tmp += cc
        else:
            break

    for nxt_v, cost, time in graph[v]:
        for g in r:
            if g - cost < 0:
                continue
            if dist[v][g] + time < dist[nxt_v][g - cost]:
                dist[nxt_v][g - cost] = dist[v][g] + time
                heapq.heappush(q, (dist[nxt_v][g - cost], g - cost, nxt_v))

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

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
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)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,m,s = LI()
    v = [[] for i in range(n)]
    M = 0
    for _ in range(m):
        x,y,a,b = LI()
        x -= 1
        y -= 1
        v[x].append((y,a,b))
        v[y].append((x,a,b))
        M += a
    g = LIR(n)
    d = defaultdict(lambda : float("inf"))
    d[(0,s)] = 0
    ans = [float("inf")]*n
    q = [(0,-s,0)]
    k = 0
    f = [0]*n
    f[0] = s
    while q:
        dx,s,x = heappop(q)
        s *= -1
        if f[x] > s:
            continue
        f[x] = s
        if ans[x] == float("inf"):
            k += 1
            ans[x] = dx
            if k >= n:
                break
        c,e = g[x]
        for y,a,b in v[x]:
            if s < a:
                continue
            nd = dx+b
            ns = s-a
            if nd < d[(y,ns)]:
                d[(y,ns)] = nd
                heappush(q,(nd,-ns,y))
        s += c
        dx += e
        while s <= M:
            for y,a,b in v[x]:
                if s < a:
                    continue
                nd = dx+b
                ns = s-a
                if nd < d[(y,ns)]:
                    d[(y,ns)] = nd
                    heappush(q,(nd,-ns,y))
            s += c
            dx += e
    for i in ans[1:]:
        print(i)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
import heapq
import os
from collections import defaultdict

import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353


N, M, S = list(map(int, sys.stdin.buffer.readline().split()))
UVAB = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(M)]
CD = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(N)]
CD = [(0, 0)] + CD

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

mada = set(list(range(2, N + 1)))
heap = [(0, 1, S)]
# dp[v, s]: v にお金を s 持ってる状態で来たときの最小値
dp = defaultdict(lambda: INF)
dp[1, S] = 0
while heap and mada:
    d, v, s = heapq.heappop(heap)
    if d > dp[v, s]:
        continue
    if v in mada:
        mada.remove(v)
    for u, a, b in graph[v]:
        if s - a < 0:
            continue
        if d + b < dp[u, s - a]:
            dp[u, s - a] = d + b
            heapq.heappush(heap, (d + b, u, s - a))
    c, dd = CD[v]
    heapq.heappush(heap, (d + dd, v, s + c))

ans = [INF] * (N + 1)
ans[1] = 0
for (v, s), d in dp.items():
    ans[v] = min(ans[v], d)
print(*ans[2:], sep='\n')

Submission status: Time Limit Exceeded

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 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__':
    examE()

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

Submission status: Time Limit Exceeded

Solution code:
import heapq


n, m, s = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]
change = [list(map(int, input().split())) for i in range(n)]
INF = 10 ** 18

graph = [[] for i in range(n)]
for u, v, cost, time in info:
    u -= 1
    v -= 1
    graph[u].append((v, cost, time))
    graph[v].append((u, cost, time))
    
dist = [[INF] * 3001 for i in range(n)]
dist[0][min(s, 3000)] = 0

q = [(0, min(s, 3000), 0)] # q = [(時間, 銀貨, 現在地)]
while q:
    d, gin, v = heapq.heappop(q)

    if dist[v][gin] < d:
        continue

    cc, dd = change[v]
    tmp = gin
    r = [gin]
    while True:
        if tmp + cc <= 3000:
            if dist[v][tmp + cc] > dist[v][tmp] + dd:
                dist[v][tmp + cc] = dist[v][tmp] + dd
                r.append(tmp)
            tmp += cc
        else:
            break

    for nxt_v, cost, time in graph[v]:
        for g in r:
            if g - cost < 0:
                continue
            if dist[v][g] + time < dist[nxt_v][g - cost]:
                dist[nxt_v][g - cost] = dist[v][g] + time
                heapq.heappush(q, (dist[nxt_v][g - cost], g - cost, nxt_v))

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

Submission status: Time Limit Exceeded

Solution code:
class RangeMinimumQuery:
    def __init__(self, n, F=min, e=float("inf"), fill=None):
        self.n0 = 2**(n-1).bit_length()
        self.F = F
        self.e = e
        if fill is None:
            fill = e
        self.data = [fill]*(2*self.n0)

    def query(self, l,r):
        l += self.n0
        r += self.n0
        res = self.e
        while l < r:
            if r&1:
                r -= 1
                res = self.F(res, self.data[r-1])
            if l&1:
                res = self.F(res, self.data[l-1])
                l += 1
            l >>=1
            r >>=1
        return res

    def update(self, i, x):
        i += self.n0-1
        self.data[i] = x
        while i:
            i = ~-i//2
            self.data[i] = self.F(self.data[2*i+1], self.data[2*i+2])

n,m,s = map(int, input().split())
G = [[] for i in range(n)]
for i in range(m):
    u,v,a,b = map(int, input().split())
    u,v = u-1, v-1
    G[u].append([v, a, b])
    G[v].append([u, a, b])
cd = [list(map(int, input().split())) for i in range(n)]

from heapq import heappop, heappush
max_money = n*60
state = [RangeMinimumQuery(max_money+1) for i in range(n)]
s = min(s, max_money)
heap = [(0,(0,s),1)]

while heap:
    time, (cur, money), flag = heappop(heap)
    if state[cur].query(money, max_money+1) <= time:
        continue
    state[cur].update(money, time)
    if flag:
        n_money = money
        n_time = time
        f = False
        for i in range(10000):
            n_money += cd[cur][0]
            n_time += cd[cur][1]
            if n_money > max_money:
                n_money = max_money
                f = True
            heappush(heap, (n_time, (cur, n_money), 0))
            if f:
                break
    for to, a,b in G[cur]:
        if money < a or state[to].query(money-a, max_money+1) <= time+b:
            continue
        heappush(heap, (time+b, (to, money-a), 1))

for i in range(1, n):
    print(state[i].query(0, max_money+1))

Submission status: Time Limit Exceeded

Solution code:
import heapq
from collections import defaultdict
import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines

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

connect = defaultdict(list)
for i in range(m):
    u, v, a, b = map(int, input().split())
    connect[u].append((v, a, b))
    connect[v].append((u, a, b))

c, d = [-1], [-1]
for i in range(n):
    c_, d_ = map(int, input().split())
    c.append(c_)
    d.append(d_)

ans = [-1] * (n+1)
dp = [{} for _ in range(n+1)]

h = [(0, s, 1)]
heapq.heapify(h)

while heapq:
    t, coin, city = heapq.heappop(h)

    if ans[city] == -1:
        ans[city] = t
        if all([v >= 0 for v in ans[2:]]):
            break

    if coin not in dp[city]:
        dp[city][coin] = t
    else:
        continue

    for neighbor, a, b in connect[city]:
        if coin - a >= 0 and neighbor != city:
            if coin-a not in dp[neighbor]:
                heapq.heappush(h, (t+b, coin-a, neighbor))

    if coin+c[city] not in dp[city]:
        heapq.heappush(h, (t+d[city], coin+c[city], city))

print('\n'.join(map(str, ans[2:])))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
##################################
# University of Wisconsin-Madison
# Author: Yaqi Zhang
##################################

# standard library
import collections
import heapq
import sys
from functools import lru_cache

sys.setrecursionlimit(10**9)

Input = lambda: sys.stdin.readline().rstrip()
IntRead = lambda: int(Input())
LineRead = lambda: list(map(int, Input().split()))


INF = 10**18

def main():
    N, M, S = LineRead()
    # state: start at 1, for 2 ... N
    graph = [[] for _ in range(N + 1)]
    cs = [-1]
    ds = [-1]
    for _ in range(M):
        u, v, a, b = LineRead()
        graph[u].append((v, a, b))
        graph[v].append((u, a, b))
    for _ in range(N):
        c, d = LineRead()
        cs.append(c)
        ds.append(d)
    def dijkstra(start, end):
        pq = [(0, start, S)]
        dist = {}
        dist[(start, S)] = 0
        # print("Hello")
        while pq:
            t, u, s = heapq.heappop(pq)
            # print(t, u, s)
            if u == end:
                return t
            for v, a, b in graph[u]:
                if s >= a:
                    if (v, s - a) not in dist or dist[v, s - a] > t + b:
                        dist[v, s - a] = t + b
                        heapq.heappush(pq, (t + b, v, s - a))
            # exchange
            c = cs[u]
            d = ds[u]
            if (u, s + c) not in dist or dist[u, s + c] > t + d:
                dist[u, s + c] = t + d
                heapq.heappush(pq, (t + d, u, s + c))
    for i in range(2, N + 1):
        print(dijkstra(1, i))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from heapq import *
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():

    inf=10**16
    n,m,s=MI()
    to=[[] for _ in range(n)]
    for _ in range(m):
        u,v,a,b=MI()
        to[u-1].append((v-1,a,b))
        to[v-1].append((u-1,a,b))
    cd=LLI(n)

    dp=[[inf]*5005 for _ in range(n)]
    hp=[]
    heappush(hp,(0,min(s,5000),0))
    fin=[False]*n
    while hp:
        t,g,u=heappop(hp)
        if dp[u][g]<t:continue
        fin[u]=True
        if sum(fin)==n:break
        c,d=cd[u]
        for i in range(1,10000):
            if g+c*i>5000:
                if dp[u][5000] <= t + d * i: continue
                dp[u][5000] = t + d * i
                heappush(hp, (t + d * i, 5000, u))
                break
            if dp[u][g+c*i]<=t+d*i:continue
            dp[u][g + c * i]=t+d*i
            heappush(hp,(t+d*i,g+c*i,u))
        for v,a,b in to[u]:
            if g-a<0:continue
            if dp[v][g-a]<=t+b:continue
            dp[v][g - a] = t + b
            heappush(hp,(t+b,g-a,v))
    for u in range(1,n):
        print(min(dp[u]))

main()

Submission status: Time Limit Exceeded

Solution code:
import heapq
from collections import defaultdict
import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines

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

connect = defaultdict(list)
for i in range(m):
    u, v, a, b = map(int, input().split())
    connect[u].append((v, a, b))
    connect[v].append((u, a, b))

c, d = [-1], [-1]
for i in range(n):
    c_, d_ = map(int, input().split())
    c.append(c_)
    d.append(d_)

ans = [-1] * (n+1)
dp = [{} for _ in range(n+1)]

h = [(0, s, 1)]
heapq.heapify(h)

while heapq:
    t, coin, city = heapq.heappop(h)

    if ans[city] == -1:
        ans[city] = t
        if all([v >= 0 for v in ans[2:]]):
            break

    if coin not in dp[city]:
        dp[city][coin] = t
    else:
        continue

    for neighbor, a, b in connect[city]:
        if coin - a >= 0 and neighbor != city:
            heapq.heappush(h, (t+b, coin-a, neighbor))

    heapq.heappush(h, (t+d[city], coin+c[city], city))

print('\n'.join(map(str, ans[2:])))

Submission status: Time Limit Exceeded

Solution code:
n,m,s = map(int, input().split())
G = [[] for i in range(n)]
for i in range(m):
    u,v,a,b = map(int, input().split())
    u,v = u-1, v-1
    G[u].append([v, a, b])
    G[v].append([u, a, b])
cd = [list(map(int, input().split())) for i in range(n)]

from heapq import heappop, heappush
max_money = n*60
state = [[float("inf")]*(max_money+1) for i in range(n)]
s = min(s, max_money)
heap = [(0,(0,s),1)]

while heap:
    time, (cur, money), flag = heappop(heap)
    if state[cur][money] <= time:
        continue
    state[cur][money] = time
    if flag:
        n_money = money
        n_time = time
        f = False
        for i in range(10000):
            n_money += cd[cur][0]
            n_time += cd[cur][1]
            if n_money > max_money:
                n_money = max_money
                f = True
            if state[cur][n_money] < n_time:
                break
            heappush(heap, (n_time, (cur, n_money), 0))
            if f:
                break
    for to, a,b in G[cur]:
        if money < a or state[to][money-a] <= time+b:
            continue
        heappush(heap, (time+b, (to, money-a), 1))

for i in range(1, n):
    print(min(state[i]))

Submission status: Time Limit Exceeded

Solution code:
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)]


import math

M = 50 * n + 1

dp = [[float('inf')] * M for _ in range(n)]
s = min(s, M - 1)
dp[0][s] = 0

def inc(dp, i, j):
    c, d = cd[i][0], cd[i][1]

    for jj in range(j):
        dp[i][jj] = min(dp[i][jj], dp[i][j])

    for jj in range(j + 1, M):
        dp[i][jj] = min(dp[i][jj], dp[i][j] + math.ceil((jj - j) / c) * d)

    return dp

dp = inc(dp, 0, s)


while True:
    flag = False

    for i in range(m):
        u, v, a, b = uvab[i][0] - 1, uvab[i][1] - 1, uvab[i][2], uvab[i][3]
        for j in range(M):
            if j + a < M and dp[u][j + a] + b < dp[v][j]:
                dp[v][j] = dp[u][j + a] + b
                dp = inc(dp, v, j)
                flag = True

        u, v = v, u
        for j in range(M):
            if j + a < M and dp[u][j + a] + b < dp[v][j]:
                dp[v][j] = dp[u][j + a] + b
                dp = inc(dp, v, j)
                flag = True

    if flag == False:
        break

for t in range(1, n):
    print(min(dp[t]))