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:
from queue import PriorityQueue
from collections import defaultdict

n, m, s = map(int, input().split())
graph = defaultdict(dict)
for i in range(m):
    u, v, a, b = map(int, input().split())
    graph[u][v] = (a, b)
    graph[v][u] = (a, b)

town = [None]*(n+1)
for i in range(n):
    c, d = map(int, input().split())
    town[i+1] = (c, d)

if s >= 2501:
    s = 2501
x = (1, s)
cost = 0
visit = set()
pq = PriorityQueue()
pq.put((cost, x), block=False)
ans = [1000000000000000]*(n+1)
while not pq.empty():
    cost, x = pq.get_nowait()
    if x in visit:
        continue
    visit.add(x)
    p, m = x
    ans[p] = min(ans[p], cost)
    c, d = town[p]
    if m <= 2501:
        pq.put((cost+d, (p, m+c)), block=False)
    for q, edge in graph[p].items():
        a, b = edge
        if m-a >= 0:
            pq.put((cost+b, (q, m-a)), block=False)
for i in range(2, n+1):
    print(ans[i])

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 = (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,(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
from collections import defaultdict

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:
from queue import PriorityQueue
from collections import defaultdict

n, m, s = map(int, input().split())
graph = defaultdict(dict)
for i in range(m):
    u, v, a, b = map(int, input().split())
    graph[u][v] = (a, b)
    graph[v][u] = (a, b)

town = [None]*(n+1)
for i in range(n):
    c, d = map(int, input().split())
    town[i+1] = (c, d)

if s >= 2501:
    s = 2501
x = (1, s)
cost = 0
visit = set()
pq = PriorityQueue()
pq.put((cost, x))
ans = [1000000000000000]*(n+1)
while not pq.empty():
    cost, x = pq.get()
    if x in visit:
        continue
    visit.add(x)
    p, m = x
    ans[p] = min(ans[p], cost)
    c, d = town[p]
    if m <= 2501:
        pq.put((cost+d, (p, m+c)))
    for q, edge in graph[p].items():
        a, b = edge
        if m-a >= 0:
            pq.put((cost+b, (q, m-a)))
for i in range(2, n+1):
    print(ans[i])

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 = n*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,N*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:
#!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
    while q:
        dx,s,x = heappop(q)
        s *= -1
        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:
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,-s,0)]
while heap:
    time, money, cur = heappop(heap)
    money = -money
    if state[cur][money] <= time:
        continue
    state[cur][money] = time
    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, -n_money, cur))
        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, -(money-a), to))

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

Submission status: Time Limit Exceeded

Solution code:
import heapq
from collections import defaultdict

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)

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

    for neighbor, a, b in connect[city]:
        if coin - a >= 0:
            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:
import heapq


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


N, M, S = inpl()
A = 51  # max A
S = min(S, M * A - 1)

lines = [[] for _ in range(N * (M * A))]
for _ in range(M):
    in_s, in_t, cost, time = inpl()
    in_s -= 1
    in_t -= 1

    for n in range(cost, M * A):
        s = in_s + n * N
        t = in_t + (n - cost) * N
        lines[s].append((t, time))

        s = in_s + (n - cost) * N
        t = in_t + n * N
        lines[t].append((s, time))


for i in range(N):
    cost, time = inpl()
    for n in range(0, M * A):
        s = i + n * N
        if n + cost >= M * A:
            t = i + (M * A - 1) * N
        else:
            t = i + (n + cost) * N
        lines[s].append((t, time))


INF = 10**20


def dijkstra(N, S):
    weight = [INF] * N
    weight[S] = 0
    q = [[0, S]]
    heapq.heapify(q)
    while q:
        w0, s = heapq.heappop(q)
        for t, w in lines[s]:
            w += w0
            if weight[t] > w:
                heapq.heappush(q, [w, t])
                weight[t] = w

    return weight


weight = dijkstra(N * (M * A), 0 + S * N)

for i in range(1, N):
    ans = INF
    for n in range(M * A):
        ans = min(ans, weight[i + n * N])
    print(ans)

Submission status: Time Limit Exceeded

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

class RMQ:
    def __init__(self, size):
        n = 1
        while n < size:
            n <<= 1
        self.n = n
        self.data = [float('inf')] * (2*n-1)
        self.ix = [-1] * (2*n-1)

    # change the value of the ith element to x
    def update(self, i, x):
        i += self.n-1  # the leaf
        self.data[i] = x
        self.ix[i] = i-(self.n-1)
        while i > 0:
            i = (i-1)//2
            vl = self.data[i*2+1]
            vr = self.data[i*2+2]
            if vl < vr:
                self.data[i] = vl
                self.ix[i] = self.ix[i*2+1]
            else:
                self.data[i] = vr
                self.ix[i] = self.ix[i*2+2]

    # return the minimum value in the range [a, b)
    def query(self, a, b):
        return self._query(a, b, 0, 0, self.n)

    # i is the index of the node, and it corresponds to the range [l, r)
    def _query(self, a, b, i, l, r):
        if r == -1:
            r = self.n

        # if no overlap
        if r <= a or b <= l:
            return float('inf')

        # if [a, b) contains whole [l, r)
        if a <= l and r <= b:
            return self.data[i]

        m = (l+r)//2
        vl = self._query(a, b, i*2+1, l, m)
        vr = self._query(a, b, i*2+2, m, r)
        return min(vl, vr)

def dijkstra(edges, size, source):
    distance = [float('inf')] * size
    distance[source] = 0
    visited = [False] * size
    pq = []
    heappush(pq, (0, source))
    while pq:
        dist_v, v = heappop(pq)
        visited[v] = True
        for u, weight in edges[v]:
            if not visited[u]:
                new_dist = dist_v + weight
                if distance[u] > new_dist:
                    distance[u] = new_dist
                    heappush(pq, (new_dist, u))
    return distance

def main():
    N, M, S = map(int, input().split())
    MAX = 10001
    AB = [[None] * N for _ in range(N)]
    for _ in range(M):
        U, V, A, B = map(int, input().split())
        U -= 1
        V -= 1
        AB[U][V] = AB[V][U] = (A, B)
    CD = [tuple(map(int, input().split())) for _ in range(N)]
    edges = [[] for _ in range(N*MAX)]
    for v in range(N):
        C, D = CD[v]
        for i in range(MAX-1):
            edges[v*MAX+i].append((min(v*MAX+i+C, (v+1)*MAX-1), D))
    for u in range(N-1):
        for v in range(u+1, N):
            if not AB[u][v]:
                continue
            A, B = AB[u][v]
            for i in range(A, MAX):
                edges[u*MAX+i].append((v*MAX+i-A, B))
                edges[v*MAX+i].append((u*MAX+i-A, B))
    dist = dijkstra(edges, N*MAX, min(S, MAX-1))
    rmq = RMQ(N*MAX)
    for i in range(N*MAX):
        rmq.update(i, dist[i])
    for v in range(1, N):
        print(rmq.query(v*MAX, (v+1)*MAX))

main()

Submission status: Time Limit Exceeded

Solution code:
import heapq


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


N, M, S = inpl()
A = 101  # max A
S = min(S, M * A - 1)

lines = [[] for _ in range(N * (M * A))]
for _ in range(M):
    in_s, in_t, cost, time = inpl()
    in_s -= 1
    in_t -= 1

    for n in range(cost, M * A):
        s = in_s + n * N
        t = in_t + (n - cost) * N
        lines[s].append((t, time))

        s = in_s + (n - cost) * N
        t = in_t + n * N
        lines[t].append((s, time))


for i in range(N):
    cost, time = inpl()
    for n in range(0, M * A):
        s = i + n * N
        if n + cost >= M * A:
            t = i + (M * A - 1) * N
        else:
            t = i + (n + cost) * N
        lines[s].append((t, time))


INF = 10**20


def dijkstra(N, S):
    weight = [INF] * N
    weight[S] = 0
    q = [[0, S]]
    heapq.heapify(q)
    while q:
        w0, s = heapq.heappop(q)
        for t, w in lines[s]:
            w += w0
            if weight[t] > w:
                heapq.heappush(q, [w, t])
                weight[t] = w

    return weight


weight = dijkstra(N * (M * A), 0 + S * N)

for i in range(1, N):
    ans = INF
    for n in range(M * A):
        ans = min(ans, weight[i + n * N])
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from heapq import heappop, heappush

n, m, ss = map(int, input().split())
lines = sys.stdin.readlines()
links = [set() for _ in range(n)]
aaa = []
for line in lines[:m]:
    u, v, a, b = map(int, line.split())
    u -= 1
    v -= 1
    links[u].add((v, a, b))
    links[v].add((u, a, b))
    aaa.append(a)

exchanges = []
for line in lines[m:]:
    c, d = map(int, line.split())
    exchanges.append((c, d))

req = sum(sorted(aaa, reverse=True)[:n])
INF = 10 ** 18
ans = [INF] * n
ans_silver = [-1] * n

q = [(0, ss, 0, 0)]  # (time, silver, city, type)
visited = set()
fixed = 0
while q:
    t, s, v, z = heappop(q)
    if (s, v) in visited or ans_silver[v] >= s:
        continue
    visited.add((s, v))
    if ans[v] == INF:
        ans[v] = t
        ans_silver[v] = s
        fixed += 1
        if fixed == n:
            break

    for u, a, b in links[v]:
        if s < a:
            continue
        ns = s - a
        nt = t + b
        if (ns, u) in visited or ans_silver[u] >= ns:
            continue
        heappush(q, (nt, ns, u, 0))

    if z == 1:
        continue

    ts = s
    tt = t
    c, d = exchanges[v]
    while ts <= req:
        ts += c
        tt += d
        if (ts, v) in visited:
            break
        heappush(q, (tt, ts, v, 1))

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

Submission status: Time Limit Exceeded

Solution code:
def main():
    import heapq
    inf = 10**20
    n, m, s = map(int, input().split())
    uvab = [list(map(int, input().split())) for _ in [0]*m]
    cd = [list(map(int, input().split())) for _ in [0]*n]
    g = [[] for _ in [0]*n]
    [g[a-1].append([b-1, c, d]) for a, b, c, d in uvab]
    [g[b-1].append([a-1, c, d]) for a, b, c, d in uvab]
    vertex = [[inf]*5001 for _ in [0]*n]
    h = [(0, 0, min(s, 5000))]  # 時刻、位置、所持金
    heapq.heapify(h)
    while h:
        t, p, money = heapq.heappop(h)
        if vertex[p][money] != inf:
            continue
        vertex[p][money] = t
        newmoney = min(money+cd[p][0], 5000)
        if vertex[p][newmoney] == inf:
            heapq.heappush(h, (t+cd[p][1], p, newmoney))
        for a, b, c in g[p]:  # 行き先、運賃、時間
            if money < b:
                continue
            if vertex[a][money-b] != inf:
                continue
            heapq.heappush(h, (t+c, a, money-b))
    for i in vertex[1:]:
        print(min(i))


main()

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] * 5051 for i in range(n)]
dist[0][min(s, 5050)] = 0

q = [(0, min(s, 5050), 0)] # q = [(時間, 銀貨, 現在地)]
while q:
    d, gin, v = heapq.heappop(q)
    if dist[v][gin] < d:
        continue
    tmp = gin
    cc, dd = change[v]
    while True:
        if tmp + cc <= 5050:
            dist[v][tmp + cc] = min(dist[v][tmp + cc],  dist[v][tmp] + dd)
            tmp += cc
        else:
            break

    for nxt_v, cost, time in graph[v]:
        for g in range(5051):
            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:
import sys
from heapq import heappop, heappush

n, m, ss = map(int, input().split())
lines = sys.stdin.readlines()
links = [set() for _ in range(n)]
aaa = []
for line in lines[:m]:
    u, v, a, b = map(int, line.split())
    u -= 1
    v -= 1
    links[u].add((v, a, b))
    links[v].add((u, a, b))
    aaa.append(a)

exchanges = []
for line in lines[m:]:
    c, d = map(int, line.split())
    exchanges.append((c, d))

req = sum(sorted(aaa, reverse=True)[:n])
INF = 10 ** 18
ans = [INF] * n
ans_silver = [-1] * n

q = [(0, ss, 0, 0)]  # (time, silver, city, type)
visited = set()
fixed = 0
while q:
    t, s, v, z = heappop(q)
    if (s, v) in visited:
        continue
    visited.add((s, v))
    if ans[v] == INF:
        ans[v] = t
        ans_silver[v] = s
        fixed += 1
        if fixed == n:
            break

    for u, a, b in links[v]:
        if s < a:
            continue
        ns = s - a
        nt = t + b
        if (ns, u) in visited or ans_silver[u] >= ns:
            continue
        heappush(q, (t + b, ns, u, 0))

    if z == 1:
        continue

    ts = s
    tt = t
    c, d = exchanges[v]
    while ts <= req:
        ts += c
        tt += d
        if (ts, v) in visited:
            break
        heappush(q, (tt, ts, v, 1))

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

Submission status: Time Limit Exceeded

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

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

out = [-1] * n

LARGE = 10000

done = dict()
from heapq import *
q = []
if s > LARGE:
    s = LARGE
heappush(q, (0, 0, s))

while q:
    time, loc, curr = heappop(q)
    if out[loc] == -1:
        out[loc] = time
    for nex, cost, timeD in adj[loc]:
        currNex = curr + cost
        timeNex = time + timeD
        if currNex > LARGE:
            currNex = LARGE
        if currNex < 0:
            continue
        if (nex, currNex) not in done or timeNex < done[(nex, currNex)]:
            done[(nex, currNex)] = timeNex
            heappush(q, (timeNex, nex, currNex))
print(*out[1:], 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 = n*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)
            loop = (n*50-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]:
                    if nextc-coin<0:
                        continue
                    if dist[u][nextc-coin] > nextd + cost:
                        dist[u][nextc-coin] = nextd + cost
                        heapq.heappush(Q, (dist[u][nextc-coin], u, nextc-coin))
        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,N*50))
    #print(D)
    ans = [0]*N
    for i in range(N):
        ans[i] = min(D[i])
    for v in ans[1:]:
        print(v)
    return

def examF():
    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
"""