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: Runtime Error

Solution code:
from heapq import heappop, heappush
import numpy as np


def solve(nn, mm, ss, line_list, cd_list):
    g = dict()
    for i in range(1, nn + 1):
        for s in range(5001):
            g[i * 10000 + s] = dict()
            if s + cd_list[i - 1][0] < 5000:
                g[i * 10000 + s][i * 10000 + s + cd_list[i - 1][0]] = cd_list[i - 1][1]
            elif s < 5000:
                g[i * 10000 + s][i * 10000 + 5000] = cd_list[i - 1][1]
    for u, v, a, b in line_list:
        for s in range(a, 5001):
            g[u * 10000 + s][v * 10000 + s - a] = b
            g[v * 10000 + s][u * 10000 + s - a] = b

    # start from 1
    # d[i, j] = best time at city i with silver j
    d = (10 ** 18) * np.ones((nn + 1) * 10000, dtype=np.int)
    d[10000 + ss] = 0
    h = []
    heappush(h, (0, 10000 + ss))
    while len(h) > 0:
        t, u = heappop(h)
        for v in g[u].keys():
            if t + g[u][v] < d[v]:
                d[v] = t + g[u][v]
                heappush(h, (t + g[u][v], v))

    res = []
    for i in range(2, nn + 1):
        res.append(d[i * 10000:(i + 1) * 10000].min())
    # print(res)
    return res


def main():
    n, m, s = map(int, input().split())
    line_list = [list(map(int, input().split())) for _ in range(m)]
    cd_list = [list(map(int, input().split())) for _ in range(n)]
    res = solve(n, m, s, line_list, cd_list)
    for r in res:
        print(r)


def test():
    assert solve(3, 2, 1, [[1, 2, 1, 2], [1, 3, 2, 4]], [[1, 11], [1, 2], [2, 5]]) == [2, 14]
    assert solve(
        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]]
    ) == [5, 5, 7]


if __name__ == "__main__":
    test()
    main()

Submission status: Runtime Error

Solution code:
INF=1000000000000000 # 1e15
MAX=50*50 # 2500

n,m,s=map(int,input().split())
u,v,a,b,c,d=[0]*m,[0]*m,[0]*m,[0]*m,[0]*n,[0]*n
for i in range(m):
  u[i],v[i],a[i],b[i]=map(int,input().split())
  u[i] -= 1
  v[i] -= 1
for i in range(n):
  c[i],d[i]=map(int,input().split())

dp=[[INF] * (MAX + 1) for _ in range(n)]
#dp[i][j]=k <=> 最短k分後に街iに所持銀貨j枚で行ける
dp[0][s] = 0
for _ in range(n * n):
  for i in range(n):
    for j in range(MAX + 1):
      dest = min(MAX, j + c[i])
      dp[i][dest] = min(dp[i][dest], dp[i][j] + d[i])
  for i in range(m):
    for j in range(a[i], MAX+1):
      # u[i] -> v[i]
      dp[v[i]][j - a[i]] = min(dp[v[i]][j - a[i]], dp[u[i]][j] + b[i])
      # v[i] -> u[i]
      dp[u[i]][j - a[i]] = min(dp[u[i]][j - a[i]], dp[v[i]][j] + b[i])
for i in range(1, n):
  print(min(dp[i]))

Submission status: Runtime Error

Solution code:
# スペース区切りの整数入力
N,M,S = map(int, input().split())

U=[]
V=[]
A=[]
B=[]

for i in range(M):
    u,v,a,b = map(int, input().split())
    U.append(u)
    V.append(v)
    A.append(a)
    B.append(b)

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

for pp in range(2,N+1):
    p0 = [[0,1,100,S]]

    res = 999999999999999999
    while True:
        p0.sort()
        t,p,g,s = p0.pop(0)
        if t >= res:
            break
        #g2s
        if g > 0:
            if [t+D[p-1],p,g-1,s+C[p-1]] in p0:
                pass
            else:
                p0.append([t+D[p-1],p,g-1,s+C[p-1]])
        #move
        for i in range(M):
            if U[i] == p and A[i] <= s:
                if [t+B[i],V[i],g,s-A[i]] in p0:
                    pass
                else:
                    p0.append([t+B[i],V[i],g,s-A[i]])
                    if V[i] == pp:
                        res = min(res,t+B[i])
            if V[i] == p and A[i] <= s:
                if [t+B[i],U[i],g,s-A[i]] in p0:
                    pass
                else:
                    p0.append([t+B[i],U[i],g,s-A[i]])
                    if U[i] == pp:
                        res = min(res,t+B[i])
        p0len = len(p0)
        if res < 999999999999999999:
            for i in range(p0len-1,-1,-1):
                if p0[i][0] >= res:
                    del p0[i]
            if len(p0) == 0:
                break
    print(res)

Submission status: Runtime Error

Solution code:
import heapq
N,M,S = [int(i) for i in input().split()]
Train = [[] for p in range(N)]
for j in range(M):
    U,V,A,B = [int(hoge) for hoge in input().split()]
    Train[U-1].append((V-1,(A,B)))#(次、(運賃,時間))
    Train[V-1].append((U-1,(A,B)))

CD = [[int(hoge) for hoge in input().split()] for k in range(N)]

num = N*2501          # グラフのノード数
dist = [float('inf') for i in range(num)] # 始点から各頂点までの最短距離を格納する
prev = [float('inf') for i in range(num)] # 最短経路における，その頂点の前の頂点のIDを格納する
    
start = 0 * 2501 + S
dist[start] = 0 #ID = Point * 2501 + Money(P=ID//2501 M = ID%2501)
q = []                  # プライオリティキュー．各要素は，(startからある頂点vまでの仮の距離, 頂点vのID)からなるタプル
heapq.heappush(q, (0, start)) # 始点をpush
while len(q) != 0:
    prov_cost, src = heapq.heappop(q) # pop(仮の距離,ID)
    
    # プライオリティキューに格納されている最短距離が，現在計算できている最短距離より大きければ，distの更新をする必要はない
    if dist[src] < prov_cost:
        continue

    # 他の頂点の探索
    src_Point = src//2501
    src_Money = src%2501
    src_RyogaeM = CD[src_Point][0]
    src_RyogaeTime = CD[src_Point][1]

    RyogaeAfter = min(2500,src_Money + src_RyogaeM)
    RyogaeID = src - src_Money + RyogaeAfter
    cost = src_RyogaeTime

    if dist[RyogaeID] > dist[src] + cost:
        dist[RyogaeID] = dist[src] + cost#distの更新
        heapq.heappush(q,(dist[RyogaeID],RyogaeID))

    for togo,trainfo in Train[src//2501]:#つながってる線路について
        cost = trainfo[1]#src→dest間の距離
        fee = trainfo[0]
        dest = togo * 2501 + src_Money - fee
        if src_Money >= fee and dist[dest] > dist[src] + cost:
            dist[dest] = dist[src] + cost # distの更新
            heapq.heappush(q, (dist[dest], dest)) # キューに新たな仮の距離の情報をpush
            prev[dest] = src                      # 前の頂点を記録

curpoint = 0
TheEnd = 2500
curmin = float("inf")
for point,d in enumerate(dist):
    if d < curmin:
        curmin = d
    if point == TheEnd:
        TheEnd += 2501
        if point > 2500:
            print(curmin)
        curmin = float("inf")

Submission status: Runtime Error

Solution code:
import copy
# スペース区切りの整数入力
N,M,S = map(int, input().split())

U=[]
V=[]
A=[]
B=[]

for i in range(M):
    u,v,a,b = map(int, input().split())
    U.append(u)
    V.append(v)
    A.append(a)
    B.append(b)

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

for pp in range(2,N+1):
    p0 = [[0,1,100,S]]

    res = 999999999999999999
    while True:
        p0.sort()
        t,p,g,s = p0.pop(0)
        if t >= res:
            break
        #g2s
        if g > 0:
            if [t+D[p-1],p,g-1,s+C[p-1]] in p0:
                pass
            else:
                p0.append([t+D[p-1],p,g-1,s+C[p-1]])
        #move
        for i in range(M):
            if U[i] == p and A[i] <= s:
                if [t+B[i],V[i],g,s-A[i]] in p0:
                    pass
                else:
                    p0.append([t+B[i],V[i],g,s-A[i]])
                    if V[i] == pp:
                        res = min(res,t+B[i])
            if V[i] == p and A[i] <= s:
                if [t+B[i],U[i],g,s-A[i]] in p0:
                    pass
                else:
                    p0.append([t+B[i],U[i],g,s-A[i]])
                    if U[i] == pp:
                        res = min(res,t+B[i])
    print(res)

Submission status: Runtime Error

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
            if (u, s) in dist and d < dist[u, s]:
                continue
            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: Runtime Error

Solution code:
def main():
    n, m, s = map(int, input().split())
    fr, al, bl, cl, dl = [dict() for _ in range(n)], [None]*m, [None]*m, [None]*n, [None]*n
    for i in range(m):
        u, v, a, b = map(int, input().split())
        fr[u-1][i] = v-1
        fr[v-1][i] = u-1
        al[i] = a
        bl[i] = b
    for i in range(n):
        c, d = map(int, input().split())
        cl[i] = c
        dl[i] = d
    if s > sum(al):
        dp = [10**13]*n
        dp[0] = 0
        for i in range(1, n):
            di = dp[i]
            for j, f in fr[i].items():
                time = dp[f] + bl[j]
                if di > time:
                    di = time
            dp[i] = di
            print(di)
    else:
        dp = [[10**13]*5001 for _ in range(n)]
        for i in range(s+1):
            dp[0][i] = 0
        for i in range(1, n):
            di = dp[i]
            for j, f in fr[i].items():
                # for i in range(1, 101):
                #     additionalcoin = ccc*i
                #     additionaltime = ddd+i
                #     dp[i][j] = dp[i][] + additionaltime
                cost = al[j]
                time = bl[j]
                cost2 = min(cost - cl[j], 5000)
                time2 = time + dl[j]
                for costi, timei in [[cost, time], [cost2, time2]]:
                    for si in range(5001-costi):
                        if si + costi >= 0:
                            di[si] = min(di[si], dp[f][si+costi] + timei)
            dp[i] = di
            print(min(di))
        
        
        
        
        
    
    

if __name__ == "__main__":
    main()

Submission status: Runtime Error

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)
Min = [[10**16]*5000 for i in range(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
    Min[nowhere][money] = min(Min[nowhere][money], time)
    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:
            if Min[to][money-a] > time+b:
                heapq.heappush(que, [time+b, to, money-a, flag])

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

Submission status: Runtime Error

Solution code:
import math
import sys
from collections import defaultdict as dd
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
from scipy.sparse.csgraph import floyd_warshall as fw
from scipy.sparse.csgraph import csgraph_from_dense
import numpy as np
N,M,S = map(int,input().split())
uvab = [ tuple(map(int,input().split())) for _ in range(M) ]
cd = [ tuple(map(int,input().split())) for _ in range(N) ]
if S!=0:
    assert()
edge = dd(list)
cost_mat = np.zeros((N, N))
time_mat = np.zeros((N, N))
all_mat = np.zeros((N, N))
for i in range(M):
    tmp1 = uvab[i][0]
    tmp2 = uvab[i][1]
    cost = uvab[i][2]
    time = uvab[i][3]
    edge[tmp1].append(tmp2)
    edge[tmp2].append(tmp1)
    cost_mat[tmp1-1][tmp2-1] = cost
    cost_mat[tmp2-1][tmp1-1] = cost
    time_mat[tmp1-1][tmp2-1] = time
    time_mat[tmp2-1][tmp1-1] = time

# cost_G = csgraph_from_dense(cost_mat, null_value=10**9)
cost_d = fw(cost_mat)
# time_G = csgraph_from_dense(time_mat, null_value=10**9)
time_d = fw(time_mat)

for i in range(N):
    now_min = cd[i][1]
    for j in range(N):
        all_mat[i,j] = math.ceil(cost_d[i,j]/cd[i][0]) + cost_d[i,j]*now_min

# print(cost_d)
# print(time_d)
# print(all_mat)
all_G = csgraph_from_dense(all_mat, null_value=10**9)
all_d = fw(all_G)
for val in all_d[0][1:]:
    print(int(val))

Submission status: Runtime Error

Solution code:
import math
import sys
from collections import defaultdict as dd
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
from scipy.sparse.csgraph import floyd_warshall as fw
from scipy.sparse.csgraph import csgraph_from_dense
import numpy as np
N,M,S = map(int,input().split())
uvab = [ tuple(map(int,input().split())) for _ in range(M) ]
cd = [ tuple(map(int,input().split())) for _ in range(N) ]
if S!=0:
    assert()
edge = dd(list)
cost_mat = np.zeros((N, N))
time_mat = np.zeros((N, N))
all_mat = np.zeros((N, N))
for i in range(M):
    tmp1 = uvab[i][0]
    tmp2 = uvab[i][1]
    cost = uvab[i][2]
    time = uvab[i][3]
    edge[tmp1].append(tmp2)
    edge[tmp2].append(tmp1)
    cost_mat[tmp1-1][tmp2-1] = cost
    cost_mat[tmp2-1][tmp1-1] = cost
    time_mat[tmp1-1][tmp2-1] = time
    time_mat[tmp2-1][tmp1-1] = time

# cost_G = csgraph_from_dense(cost_mat, null_value=10**9)
cost_d = fw(cost_mat)
# time_G = csgraph_from_dense(time_mat, null_value=10**9)
time_d = fw(time_mat)

for i in range(N):
    now_min = cd[i][1]
    for j in range(N):
        all_mat[i,j] = math.floor(cost_d[i,j]/cd[i][0]) + cost_d[i,j]*now_min

# print(cost_d)
# print(time_d)
# print(all_mat)
all_G = csgraph_from_dense(all_mat, null_value=10**9)
all_d = fw(all_G)
for val in all_d[0][1:]:
    print(int(val))

Submission status: Runtime Error

Solution code:
import heapq
inf = 10**18
def dijkstra(s, n, G):#スタート, 頂点数, グラフ:[[(cost, v)], ...]
    dist = [inf]*n
    edges = []#(sからvまでのコストの候補, v)
    dist[s] = 0
    for e in G[s]:
        heapq.heappush(edges, e)
    while edges:
        cost, v = heapq.heappop(edges)
        if dist[v] != inf:
            continue
        dist[v] = cost
        for c, nv in G[v]:
            if dist[nv] == inf:
                heapq.heappush(edges, (cost + c, nv))
    return dist
mx = 5005
n, m, s = map(int, input().split())
g = [[] for _ in range(n*mx)]
for i in range(m):
    u, v, a, b = map(int, input().split())
    u-=1
    v-=1
    for j in range(mx):
        if j>=a:
            g[u*mx+j].append((b, v*mx+j-a))
            g[v*mx+j].append((b, u*mx+j-a))
for i in range(n):
    c, d = map(int, input().split())
    for j in range(mx-c):
        g[i*mx+j].append((d, i*mx+j+c))
dist = dijkstra(s, len(g), g)
for i in range(1, n):
    res = inf
    for j in range(mx):
        res = min(res, dist[i*mx+j])
    print(res)

Submission status: Runtime Error

Solution code:
import math
import sys
from collections import defaultdict as dd
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
from scipy.sparse.csgraph import floyd_warshall as fw
from scipy.sparse.csgraph import csgraph_from_dense
import numpy as np
N,M,S = map(int,input().split())
uvab = [ tuple(map(int,input().split())) for _ in range(M) ]
cd = [ tuple(map(int,input().split())) for _ in range(N) ]
if S!=0:
    assert()
edge = dd(list)
cost_mat = np.zeros((N, N))
time_mat = np.zeros((N, N))
all_mat = np.zeros((N, N))
for i in range(M):
    tmp1 = uvab[i][0]
    tmp2 = uvab[i][1]
    cost = uvab[i][2]
    time = uvab[i][3]
    edge[tmp1].append(tmp2)
    edge[tmp2].append(tmp1)
    cost_mat[tmp1-1][tmp2-1] = cost
    cost_mat[tmp2-1][tmp1-1] = cost
    time_mat[tmp1-1][tmp2-1] = time
    time_mat[tmp2-1][tmp1-1] = time

# cost_G = csgraph_from_dense(cost_mat, null_value=10**9)
cost_d = fw(cost_mat)
# time_G = csgraph_from_dense(time_mat, null_value=10**9)
time_d = fw(time_mat)

for i in range(N):
    now_min = cd[i][1]
    for j in range(N):
        all_mat[i,j] = math.floor(cost_d[i,j]/cd[i][0]) + cost_d[i,j]*now_min

# print(cost_d)
# print(time_d)
# print(all_mat)
all_G = csgraph_from_dense(all_mat, null_value=10**9)
all_d = fw(all_G)
for val in all_d[0]:
    print(int(val))

Submission status: Runtime Error

Solution code:
n, m, s = [int(i) for i in input().split()]

e = []
for _ in range(m):
    u, v, a, b = [int(i) for i in input().split()]
    u -= 1
    v -= 1
    e.append([u, v, a, b])

co = [[int(i) for i in input().split()] for _ in range(n)]

dp = [[10 ** 18] * 6000 for _ in range(n)]
dp[0][s] = 0
for i in range(6000):
    if i + co[0][0] < 6000:
        dp[0][i + co[0][0]] = min(dp[0][i + co[0][0]], dp[0][i] + co[0][1])

for _ in range(n):
    for u, v, a, b in e:
        for j in range(a, 6000):
            dp[v][j - a] = min(dp[v][j - a], dp[u][j] + b)
        for i in range(6000):
            if i + co[v][0] < 6000:
                dp[v][i + co[v][0]] = min(dp[v][i + co[v][0]], dp[v][i] + co[v][1])

        for j in range(a, 6000):
            dp[u][j - a] = min(dp[u][j - a], dp[v][j] + b)
        for i in range(6000):
            if i + co[u][0] < 6000:
                dp[u][i + co[u][0]] = min(dp[u]
                                          [i + co[u][0]], dp[u][i] + co[u][1])

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

Submission status: Runtime Error

Solution code:
s = input()
count = 0
l = len(s)
for i in range(l-4):
    tmp = int(s[i:i+6])
    tmp2 = int(s[i:i+5])
    tmp3 = int(s[i:i+4])
    if tmp%2019==0:
        count +=1
    if tmp2%2019==0:
        count +=1
    if tmp3%2019==0:
        count +=1

print(count)

Submission status: Runtime Error

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,s,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: Runtime Error

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]:
                    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))
    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: Runtime Error

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 = [defaultdict(lambda :inf) for _ in range(n)]
        dist[start][silver] = 0
        Q = [(0, start, silver)]  # (dist,vertex)
        while (Q):
            d, v, c = heapq.heappop(Q)
            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]:
                    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))
    for i in range(1,N):
        print(min(D[i].values()))
    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
"""