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:
import heapq

INF = 10**9


class Dijkstra(object):

    """ 使用例
    dik = Dijkstra()
    edge = defaultdict(list)
    edge[(1, 1)].append([1, (1, 2)])
    edge[(1, 2)].append([1, (1, 1)])
    edge[(1, 2)].append([2, (2, 1)])
    edge[(2, 1)].append([2, (1, 2)])
    edge[(2, 1)].append([5, (2, 2)])
    edge[(2, 2)].append([5, (2, 1)])
    edge[(2, 2)].append([3, (1, 2)])
    edge[(1, 2)].append([3, (2, 2)])

    s0 = (1, 1)
    ans = dik(s0, edge)

    """

    def __init(self):
        pass

    def __call__(self, s0, edge):

        # s0:始点 (,,,)
        # edge[(,,,)] = [コスト、(,,,)], [コスト、(,,,)]

        d = dict()
        used = dict()

        edgelist = edge[s0]
        heapq.heapify(edgelist)

        d[s0] = 0
        used[s0] = False

        while len(edgelist):
            minedge = heapq.heappop(edgelist)
            if not used.get(minedge[1], True):
                continue
            v = minedge[1]
            d[v] = minedge[0]
            used[v] = False

            for e in edge[v]:
                if used.get(e[1], True):
                    if d.get(e[1], INF) <= d[v] + e[0]:
                        continue
                    heapq.heappush(edgelist, [d[v] + e[0], e[1]])

        return d


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

    s_max = 2500
    S = min(S, s_max)

    dik = Dijkstra()
    edge = dict()
    s0 = (1, S)

    for m in range(1, M + 1):
        U, V, A, B = map(int, input().split())
        for s in range(A, s_max + 1):
            if not (U, s) in edge:
                edge[(U, s)] = []
            if not (V, s) in edge:
                edge[(V, s)] = []
            edge[(U, s)].append([B, (V, s - A)])
            edge[(V, s)].append([B, (U, s - A)])

    for n in range(1, N + 1):
        C, D = map(int, input().split())
        for s in range(s_max + 1):
            s1 = min(s + C, s_max)
            if not (n, s) in edge:
                edge[(n, s)] = []
            edge[(n, s)].append([D, (n, s1)])

    d = dik(s0, edge)

    for n in range(2, N + 1):
        ans = INF
        for s in range(s_max + 1):
            ans = min(ans, d.get((n, s)), INF)
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
input=lambda: sys.stdin.readline().rstrip()
import heapq
n,m,s=map(int,input().split())
E=[]
for _ in range(m):
  E.append(tuple(map(int,input().split())))
CD=[]
for _ in range(n):
  CD.append(tuple(map(int,input().split())))
nn=n*2500
edge=[[] for i in range(nn)]
for u,v,a,b in E:
  u-=1
  v-=1
  for i in range(a,2500):
    edge[u*2500+i].append(b*10**6+v*2500+i-a)
    edge[v*2500+i].append(b*10**6+u*2500+i-a)
for i in range(n):
  c,d=CD[i]
  for j in range(2500):
    if j+c<2500:
      edge[i*2500+j].append(d*10**6+i*2500+j+c)

def dijkstra_heap(s):
  d=[float("inf")]*nn
  used=[True]*nn
  d[s]=0
  used[s]=False
  edgelist=[]
  for e in edge[s]:
    heapq.heappush(edgelist,e)
  while edgelist:
    minedge=heapq.heappop(edgelist)
    minedge_cost=minedge//(10**6)
    minedge_v=minedge%(10**6)
    if not used[minedge_v]:
      continue
    d[minedge_v] = minedge_cost
    used[minedge_v] = False
    for e in edge[minedge_v]:
      e_cost=e//(10**6)
      e_v=e%(10**6)
      if used[e_v]:
        heapq.heappush(edgelist,e+minedge_cost*10**6)
  return d
D=dijkstra_heap(s)
for i in range(1,n):
  ans=D[i*2500]
  for j in range(1,2500):
    ans=min(ans,D[i*2500+j])
  print(ans)

Submission status: Runtime Error

Solution code:
from heapq import *
import sys
input = sys.stdin.buffer.readline
n, m, s = map(int, input().split())
lim = 2510
di = [[float("inf")] * lim for _ in range(n)]
di[0][s] = 0
con = [[] for _ in range(n)]
for _ in range(m):
	u, v, a, b = map(int, input().split())
	con[u - 1].append((v - 1, a, b))
	con[v - 1].append((u - 1, a, b))
q = [(0, s, 0)]
cd = [list(map(int, input().split())) for _ in range(n)]
while q:
	time, have, cur = heappop(q)
	if di[cur][have] < time:
		continue
	c, d = cd[cur]
	if have + c < lim and di[cur][have + c] > time + d:
		di[cur][have + c] = time + d
		heappush(q, (time + d, have + c, cur))
	for nxt, dh, dt in con[cur]:
		if have >= dh and di[nxt][have - dh] > time + dt:
			di[nxt][have - dh] = time + dt
			heappush(q, (time + dt, have - dh, nxt))
for p in di[1:]:
	print(min(p))

Submission status: Runtime Error

Solution code:

import sys
input = lambda : sys.stdin.readline().rstrip()

import heapq
h = []
heapq.heapify(h)

n, m, s = list(map(int, input().split()))
a, b = [[None] * m for _ in range(2)]
c, d = [[None] * n for _ in range(2)]

ns = {}
uv2e = {}
for i in range(m):
    u,v,a[i],b[i] = list(map(int, input().split()))
    ns.setdefault(u-1, set())
    ns.setdefault(v-1, set())
    ns[u-1].add(v-1)
    ns[v-1].add(u-1)
    uv2e[u-1,v-1] = i
    uv2e[v-1,u-1] = i
for i in range(n):
    c[i], d[i] = list(map(int, input().split()))

maxs = max(a)*(n-1)
s = min(s, maxs)
state = (0, 0, s) # (距離, ノード, 銀貨枚数)
ans = [[None] * (maxs+1) for _ in range(n)]
ans[0][s] = 0
done = [[None] * (maxs+1) for _ in range(n)]
heapq.heappush(h, state)
count = 0
while h:
    count += 1
    dd, u, ss = heapq.heappop(h)
#     if ans[u][ss] is not None and ans[u][ss] <= dd:
#         continue
#     ans[u][ss] = dd
    
    if done[u][ss]:
        continue
    done[u][ss] = True
    
    # グラフの隣接点
    for v in ns[u]:
        e= uv2e[u,v]
        if ss<a[e] or done[v][ss-a[e]] :
            continue
        ans[v][ss-a[e]] = min(ans[v][ss-a[e]], dd + b[e]) if ans[v][ss-a[e]] is not None else dd+b[e]
#         if ss<a[e] or ans[v][ss-a[e]] is not None:
#             continue
        heapq.heappush(h, (dd + b[e], v, ss-a[e]))
    # 両替
    if ss+c[u] <= maxs:
        sss = ss+c[u]
    elif ss < maxs:
        sss = maxs
    heapq.heappush(h, (dd + d[u], u, sss))
    ans[u][sss] = min(ans[u][sss], dd + d[u]) if ans[u][sss] is not None else dd+d[u]

for item in ans[1:]:
    print(min(item))

Submission status: Runtime Error

Solution code:

import sys
input = lambda : sys.stdin.readline().rstrip()

def _input():
    lines = open("../tmp_in").readlines()
    for ss in lines:
        yield ss.rstrip()
input = _input().__next__


import heapq
h = []
heapq.heapify(h)

n, m, s = list(map(int, input().split()))
a, b = [[None] * m for _ in range(2)]
c, d = [[None] * n for _ in range(2)]

ns = {}
uv2e = {}
for i in range(m):
    u,v,a[i],b[i] = list(map(int, input().split()))
    ns.setdefault(u-1, set())
    ns.setdefault(v-1, set())
    ns[u-1].add(v-1)
    ns[v-1].add(u-1)
    uv2e[u-1,v-1] = i
    uv2e[v-1,u-1] = i
for i in range(n):
    c[i], d[i] = list(map(int, input().split()))

maxs = max(a)*(n-1)
s = min(s, maxs)
state = (0, 0, s) # (距離, ノード, 銀貨枚数)
ans = [[None] * (maxs+1) for _ in range(n)]
heapq.heappush(h, state)
count = 0
while h:
    count += 1
    dd, u, ss = heapq.heappop(h)
#     print(dd, u, ss)
    if ans[u][ss] is not None and ans[u][ss] <= dd:
        continue
    ans[u][ss] = dd
    
    # グラフの隣接点
    for v in ns[u]:
        e= uv2e[u,v]
        if ss<a[e] or ans[v][ss-a[e]] is not None:
            continue
        heapq.heappush(h, (dd + b[e], v, ss-a[e]))
    # 両替
    if ss+c[u] <= maxs:
        heapq.heappush(h, (dd + d[u], u, ss+c[u]))
    elif ss < maxs:
        heapq.heappush(h, (dd + d[u], u, maxs))

for item in ans[1:]:
    print(min(item))

Submission status: Runtime Error

Solution code:
def main():
    import heapq

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

    edges = [[] for _ in range(n)]
    max_cost = 0
    for _ in range(m):
        from_, to, cost, time = map(int, input().split())
        edges[from_-1].append((to-1, cost, time))
        edges[to-1].append((from_-1, cost, time))
        if cost > max_cost:
            max_cost = cost

    banks = []
    for i in range(n):
        coin, time = map(int, input().split())
        banks.append((coin, time))

    max_coin = max_cost * (n-1)
    if s > max_coin:
        s = max_coin

    INF = float('INF')
    DP = [[INF] * max_coin for _ in range(n)]
    DP[0][s] = 0
    ans = [INF] * n

    def push_todo(node, coin, time):
        if coin < 0:
            return
        if time >= DP[node][coin]:
            return
        heapq.heappush(todo, (time, node, coin))
        DP[node][coin] = time

    def charge(node, current_coin, current_time):
        coin, time = banks[node]
        new_coin = current_coin + coin
        if new_coin >= max_coin:
            new_coin = max_coin-1
        push_todo(node, new_coin, current_time+time)

    todo = [(0, 0, s)]  # time, node, coin
    while todo:
        current_time, node, current_coin = heapq.heappop(todo)
        if current_time > DP[node][current_coin]:
            continue

        if current_time < ans[node]:
            ans[node] = current_time

        charge(node, current_coin, current_time)

        for to, cost, time in edges[node]:
            push_todo(to, current_coin-cost, current_time+time)

    for a in ans[1:]:
        print(a)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N, M, S = map(int, input().split())
road = [[] for i in range(M+1)]#road[i]がとしiから伸びる[to, cost, time]が入る
for i in range(M):
    u,v,a,b = map(int, input().split())
    road[u].append([v,a,b])
    road[v].append([u,a,b])
city = [[]]#city[i]がi番目の都市の[枚数, 時間]になってる
for i in range(N):
    c,d = map(int, input().split())
    city.append([c,d])
cosa = []
for item in road:
    cosa.append(item[1])

import heapq
d = [0]*(N+1)#d[i]には都市iでの最短時間が入ってる dp[0]は無意味
used = [False]*(N+1)
que = []#queには[時間,位置,所持銀貨の枚数が入ってる]
que.append([0,0,S])
ma = max(cosa)
maa = ma*(N+1)
while len(que) > 0:
    mn = heapq.heappop(que)
    if used[mn[1]]:
        continue
    dp[mn[1]] = mn[0]
    used[mn[1]] = True
    for item in road[mn[1]]:
        if mn[2] < item[1]:
            a = int((item[1]-mn[2])/city[mn[1]][0])
            if not a*city[item[0]] == item[1]-mn[2]:
                a += 1
            si = a*city[mn[1][0]]-item[1] #渡ったあとのシルバーの数
            ti = a*city[mn[1][1]] + item[2] + mn[0]
            if si > maa:
                si = maa
            heapq.heappush(que,[ti,item[0],si])
        else:
            si = mn[2]-item[1]
            ti = mn[0]+item[2]
            heapq.heappush(que,[ti,item[0],si])

print(d)

Submission status: Runtime Error

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

inf = float('inf')
cost=[[]*N for _ in range(N)]
exc=[]


for _ in range(M):
    u,v,a,b=map(int,input().split())
    u,v=u-1,v-1
    cost[u].append((v,a,b))
    cost[v].append((u,a,b))
for _ in range(N):
    c,d=map(int,input().split())
    exc.append((c,d))

used=[False]*2451*N
di=[inf]*2451*N
di[S]=0

while True:
    v=-1
    for i in range(2451*N):
        if not used[i] and v==-1:
            v=i
        elif not used[i] and di[i]<di[v]:
            v=i
    if v==-1:
        break
    used[v]=True
    u=v//2451 #都市名
    s=v%2451 #所持金

    for x,a,b in cost[u]:
        if s>=a:
            di[x*2451+s-a]=min((di[x*2451+s-a],di[v]+b))
    c,d=exc[u]
    if s+c>2450:
        c=2450-s
    di[v+c]=min(di[v+c],di[v]+d)

for i in range(1,N):
    m=inf
    for j in range(2451):
        m=min(m,di[i*2451+j])
    print(m)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
# E

from heapq import heappop, heappush

MAX_V = 50
MAX_S = MAX_V*50 + 5


class Dijkstra(object):
    def __init__(self, n:int):
        self.adjacency_dict = {}
        self.n = n
        self.dp = [[float('inf')] * (MAX_S+5) for _ in range(self.n)]
        for i in range(n):
            self.add_vertex(i)
        self.heap_q = []

    def add_vertex(self, v: int):
        """ ノードを追加する """
        self.adjacency_dict[v] = {}
        self.C = []
        self.D = []

    def add_edge(self, v1: int, v2: int, a, b, undirected=False):
        self.adjacency_dict[v1][v2] = {"a":a,"b":b}
        if undirected:
            self.adjacency_dict[v2][v1] = {"a":a,"b":b}

    def push(self, v, m, x):
        if m < 0:  #お金がない
            return
        if self.dp[v][m] <= x:  #最短ではない
            return
        self.dp[v][m] = x
        heappush(self.heap_q, (x, v, m))

    def run(self, start: int, money: int) -> (list, list):
        # sからの距離とその前のノードを管理する
        # self.dp[start][money] = 0

        # プライオリティキューでstartから各ノードの(最短距離, ノードindex)を管理する
        self.push(start, money, 0)

        while len(self.heap_q) > 0:
            # 未確定な中から最小のノードを取得し、確定する
            x, v, m = heappop(self.heap_q)
            if self.dp[v][m] != x:
                continue

            # お金の更新
            nm = min(MAX_S, m + self.C[v])
            self.push(v, nm, x + self.D[v])

            # 最小のノードから直接リンクしているノードについて、時間(b)とお金(a)を更新する
            # print(v, self.adjacency_dict[v])
            for node in self.adjacency_dict[v].keys():
                self.push(node, m - self.adjacency_dict[v][node]['a'], x + self.adjacency_dict[v][node]['b'])

        return self.dp


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

g = Dijkstra(N)

for _ in range(M):
    v1, v2, a, b = map(int, input().split())
    g.add_edge(v1 - 1, v2 - 1, a, b, undirected=True)

for _ in range(N):
    c, d = map(int, input().split())
    g.C.append(c)
    g.D.append(d)


# print(g.adjacency_dict)
# print(g.C, g.D)
res = g.run(start=0, money=S)

# print(res)

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

Submission status: Runtime Error

Solution code:
def main():
  import sys
  input = sys.stdin.readline
  
  n = int(input())
  s = [[],[]]
  for i in range(2):
    s[i] = tuple(map(int,input().split()))
  u = [[],[]]
  for i in range(2):
    u[i] = tuple(map(int,input().split()))
  
  val = [[0 for _ in range(n)] for _ in range(2)]
  d = [[0 for _ in range(n)] for _ in range(n)]
  ans = [[0 for _ in range(n)] for _ in range(n)]
  
  def flip():
    for i in range(n):
      for j in range(i,n):
        d[i][j],d[j][i] = d[j][i],d[i][j]
    
  def solve():
    for i in range(n):
      for j in range(n):
        d[i][j] = -1
    for k in range(1):
      for i in range(n):
        if s[k][i] != val[k][i]:
          for j in range(n):
            if d[i][j] != -1 and d[i][j] != val[k][i]:
              return False
            d[i][j] = val[k][i]
      flip()
    #print(d)
    for l in range(2):
      for k in range(2):
        for i in range(n):
          if s[k][i] == val[k][i]:
            p = []
            ok = False
            for j in range(n):
              if d[i][j] == val[k][i]:
                ok = True
              if d[i][j] == -1:
                p.append(j)
            if ok:
              continue
            if len(p) == 0:
              return False
            elif len(p) == 1:
              d[i][p[0]] = val[k][i]
        flip()
    #print(d)
    start = 0
    for i in range(n):
      num = start
      flag = False
      for j in range(n):
        if d[i][j] == -1:
          flag = True
          d[i][j] = num
          num ^= 1
      if flag:
        start ^= 1
    return True
  
  for b in range(64):
    for i in range(2):
      for j in range(n):
        val[i][j] = (u[i][j]>>b)&1
    if solve():
      for i in range(n):
        for j in range(n):
          ans[i][j] |= d[i][j]<<b
    else:
      print(-1)
      exit()
  
  for i in range(n):
    print(*ans[i])

main()

Submission status: Runtime Error

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

from heapq import heappush, heappop

N,M,S = map(int,readline().split())
ABC = [list(map(int,readline().split())) for _ in range(M)]
m = map(int,read().split())
CD = list(zip(m,m))

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

def f():
  INF = 10 ** 18
  arrive = [False]*n
  ans = []
  qq = 2500
  dist = [[INF] * qq for _ in range(N)]
  dist[0][min(qq-1,S)] = 0
  q = [(0,min(qq-1,S),0)]
  while q:
      st,ss,v = heappop(q) # 総時間、銀貨、今いる頂点
      if dist[v][ss] < st:
        continue
      if not arrive[v]:
        arrive[v] = True
        ans.append((v,st))
        if all(arrive):
          break
      c,d = CD[v]
      # 銀貨の購入
      if ss < qq-1:
          ns = min(ss + c, qq-1)
          nt = st + d
          if dist[v][ns] > nt:
              dist[v][ns] = nt
              heappush(q,(nt,ns,v))
      # 移動
      for nex,g,tt in graph[v]:
          if ss-g < 0:
              continue
          dt = st + tt
          if dist[nex][ss-g] <= dt:
              continue
          dist[nex][ss-g] = dt
          heappush(q,(dt,ss-g,nex))
  return ans

ab = f()
from operator import itemgetter
ab = sorted(ab,key=itemgetter(0))
for i in range(N-1):
  print(ab[i][1])

Submission status: Runtime Error

Solution code:
from heapq import *

T = [[10**18 for _ in range(2451)] for _ in range(N)]

act = [[] for _ in range(N)]

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

for i in range(M):
  U, V, A, B = tuple(map(int, input().split()))
  U -= 1
  V -= 1
  act[U] += [(V, A, B)]
  act[V] += [(U, A, B)]

for i in range(N):
  C, D = tuple(map(int, input().split()))
  act[i] += [(i, -C, D)]

que = [(0, 0, S)]

while que:
  (currentT, n, coins) = heappop(que)
  for m, cost, t in act[n]:
    # もし「払える金額で」「最小時間T[移動先][所持金]を更新できるとき」に値を更新、キューに状態を追加。
    if coins >= cost and currentT + t < T[m][min(2450, coins - cost)]:
      T[m][min(2450, coins - cost)] = currentT + t
      heappush(que, (currentT + t, m, min(2450, coins - cost)))

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

Submission status: Runtime Error

Solution code:
from heapq import *

T = [[10**18 for _ in range(2451)] for _ in range(N)]

act = [[] for _ in range(N)]

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

for i in range(M):
  U, V, A, B = tuple(map(int, input().split()))
  maxV = max(maxV, A)
  U -= 1
  V -= 1
  act[U] += [(V, A, B)]
  act[V] += [(U, A, B)]

for i in range(N):
  C, D = tuple(map(int, input().split()))
  act[i] += [(i, -C, D)]

que = [(0, 0, S)]

while que:
  (currentT, n, coins) = heappop(que)
  for m, cost, t in act[n]:
    # もし「払える金額で」「最小時間T[移動先][所持金]を更新できるとき」に値を更新、キューに状態を追加。
    if coins >= cost and currentT + t < T[m][min(2450, coins - cost)]:
      T[m][min(2450, coins - cost)] = currentT + t
      heappush(que, (currentT + t, m, min(2450, coins - cost)))

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

Submission status: Runtime Error

Solution code:
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra
import numpy as np

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

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

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

graph = np.zeros((Nv,Nv))

if S > Ns:
    S = Ns

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

# -----

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

graph=csr_matrix(graph)

s=V[(0,S)]
dist_matrix = dijkstra(csgraph=graph, directed=True, indices = s)

for i in range(1,N):
    ans = min([dist_matrix[i*(Ns+1)+v] for v in range(Ns+1)])
    print(int(ans))

Submission status: Runtime Error

Solution code:
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra
import numpy as np

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

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

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

graph = np.zeros((Nv,Nv),dtype=np.int64)

if S > Ns:
    S = Ns

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

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

s=V[(0,S)]
dist_matrix = dijkstra(csgraph=graph, directed=True, indices = s)

for i in range(1,N):
    ans = min([dist_matrix[i*(Ns+1)+v] for v in range(Ns+1)])
    print(int(ans))

Submission status: Runtime Error

Solution code:
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra
import numpy as np

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

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

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

graph = np.zeros((Nv,Nv),dtype=np.int8)
if S > Ns:
    S = Ns

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

# -----

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

s=V[(0,S)]
dist_matrix = dijkstra(csgraph=graph, directed=True, indices = s)

for i in range(1,N):
    ans = min([dist_matrix[i*(Ns+1)+v] for v in range(Ns+1)])
    print(int(ans))

Submission status: Runtime Error

Solution code:
from heapq import *

n, m, s = map(int, input().split())
tree = [[] for _i in range(n+1)]
for _i in range(m):
    u, v, a, b = map(int, input().split())
    tree[u].append([v, a, b])
    tree[v].append([u, a, b])

cd = [[0,0]]
for _i in range(n):
    cd.append(list(map(int, input().split())))

dp = [[float('inf') for _i in range(50*n+1)] for _j in range(n+1)]
hq = [[0, 1, s]]
dp[1][s] = 0
heapify(hq)
while hq:
    t, p, g = heappop(hq)
    if g+cd[p][0] <= 50*n:
        x, y = t+cd[p][1], min([g+cd[p][0], 50*n])
        if dp[p][y] > x:
            dp[p][y] = x
            heappush(hq, [x, p, y])
    for x, y, z in tree[p]:
        if g-y >= 0 and dp[x][g-y] > t+z:
            dp[x][g-y] = t+z
            heappush(hq, [t+z, x, g-y])

for i in dp[2:]:
    print(min(i))

Submission status: Runtime Error

Solution code:
from heapq import *

n, m, s = map(int, input().split())
tree = [[] for _i in range(n+1)]
for _i in range(m):
    u, v, a, b = map(int, input().split())
    tree[u].append([v, a, b])
    tree[v].append([u, a, b])

cd = [[0,0]]
for _i in range(n):
    cd.append(list(map(int, input().split())))

dp = [[float('inf') for _i in range(50*n+1)] for _j in range(n+1)]
hq = [[0, 1, s]]
dp[1][s] = 0
heapify(hq)
visit = [[-1 for _i in range(50*n+1)] for _j in range(n+1)]
while hq:
    t, p, g = heappop(hq)

    if g+cd[p][0] <= 50*n:
        x, y = t+cd[p][1], min([g+cd[p][0], 50*n])
        if dp[p][y] > x:
            dp[p][y] = x
            heappush(hq, [x, p, y])
    for x, y, z in tree[p]:
        if g-y >= 0 and dp[x][g-y] > t+z:
            dp[x][g-y] = t+z
            heappush(hq, [t+z, x, g-y])

for i in dp[2:]:
    print(min(i))

Submission status: Runtime Error

Solution code:
# ABC 164 E 草案
import sys
sys.setrecursionlimit(10**6)

n,m,s= map(int, input().split())
g= [list(map(int, input().split())) for i in range(m)]
# 両替所
c= [list(map(int, input().split())) for i in range(n)]

x=2501
# 作るグラフ (点,所有銀貨,必要時間)
gg=[[]*x for i in range(n)]
for i in range(n):
    for j in range(x-1):
        # 金貨を銀貨に交換
        y=j+c[i][0]
        if y>=x-1:
            y=x-1
        gg[i][j].append((i,y,c[i][1]))


for i in range(1,x):
    for u,v,a,b in g:
        u-=1
        v-=1
        # 銀貨足りる時移動できる
        if i-a>=0:
            gg[v][i].append((u,i-a,b))
            gg[u][i].append((v,i-a,b))





#ダイクストラ法
from heapq import heappush, heappop

def dijkstra(edges, size, source,gold):
    # edge=探索するグラフ
    # size=グラフの点の数
    # source=スタート点
    distance = [[float('inf')]*x for i in range(n)]
    distance[source][gold] = 0
    visited = [[False]*x for i in range(n)]
    pq = []
    heappush(pq, (0, source,gold))
    while pq:
        dist_v, u,v = heappop(pq)
        visited[u][v] = True
        for u,v, weight in edges[u][v]:
            if not visited[u][v]:
                new_dist = dist_v + weight
                if distance[u][v] > new_dist:
                    distance[u][v] = new_dist
                    heappush(pq, (new_dist, u,v))
    return distance
s=min(2500,s)
ans=dijkstra(gg,n,0,s)

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

Submission status: Runtime Error

Solution code:
from heapq import *
n,m,s=map(int,input().split())
c=[0]*n
d=[0]*n
g=[[]for i in range(n)]

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

flag=0 #if this == (1<<n)-1 then finish roop
lasttime=[[10**15]*2501 for i in range(n)]
lasttime[0][min(2500,s)]=0
mintimes=[10**15]*n
hp=[(0,min(2500,s),0)]#(time,silver,node)

while flag!=((1<<n)-1):
    time,silver,node = heappop(hp)
    flag=flag|(1<<node)
    mintimes[node]=min(mintimes[node],time)

    for atnode,costmoney,costtime in g[node]:
        if costmoney<=silver and lasttime[atnode][silver-costmoney]>time+costtime:
            heappush(hp,(time+costtime,silver-costmoney,atnode))
            lasttime[atnode][silver-costmoney]=min(lasttime[atnode][silver-costmoney],time+costtime)

    if silver!=2500 and lasttime[node][min(silver+c[node],2500)]>time+d[node]:
        heappush(hp,(time+d[node],min(silver+c[node],2500),node))
        lasttime[node][silver+c[node]]=min(lasttime[node][min(silver+c[node],2500)],time+d[node])
        
print(*mintimes[1:],sep="\n")

Submission status: Runtime Error

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