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: Accepted

Solution code:
def dijkstra(v, G):
    import heapq

    ret = [10 ** 20] * len(G)
    ret[v] = 0
    q = [(ret[i], i) for i in range(len(G))]
    heapq.heapify(q)

    while len(q):
        tmpr, u = heapq.heappop(q)
        if tmpr == ret[u]:
            for w, l in G[u]:
                if ret[w] > ret[u] + l:
                    ret[w] = ret[u] + l
                    heapq.heappush(q, (ret[w], w))
    return ret


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

maxA = max([a for u, v, a, b in UVAB])
Q = maxA * (N - 1) + 1
G = [[] for _ in range(Q * N)]

for u, v, a, b in UVAB:
    for q in range(Q):
        if q >= a:
            G[Q * (u - 1) + q].append((Q * (v - 1) + q - a, b))
            G[Q * (v - 1) + q].append((Q * (u - 1) + q - a, b))

for n, (c, d) in enumerate(CD):
    for q in range(Q):
        G[Q * n + q].append((Q * n + min(Q - 1, c + q), d))

ans = dijkstra(min(S, Q - 1), G)
for n in range(1, N):
    print(min(ans[Q * n:Q * (n + 1)]))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

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

def print_l(l):
    print(' '.join(map(str, l)))

class Interval():
    def __init__(self, li):
        self.li = li
        self.n = len(li)
        self.sum_li = [li[0]]
        for i in range(1, self.n):
            self.sum_li.append(self.sum_li[i-1] + li[i])

    def sum(self, a, b=None):
        if b is None:
            return self.sum(0, a)

        res = self.sum_li[min(self.n-1, b-1)]
        if a > 0:
            res -= self.sum_li[a-1]
        return res

n,m,s=l_in()

uvab=[]
edges = [[] for _ in range(n)]
for _ in range(m):
    u,v,a,b = l_in()
    edges[u-1].append((v-1,a,b))
    edges[v-1].append((u-1,a,b))

cd = [l_in() for _ in range(n)]

# dp[i][g] city i で g まいの銀貨をもつための最小時間
m = 50*n+1
#m = 4
dp = [[-1]*m for _ in range(n)]


from heapq import heappush,heappop
h = []

for g in range(min(s+1,m+3)):
    heappush(h, (0,-g,0))

while len(h) > 0:
    t,g,i = h[0]
    g = -g
#    print("t,g,i", t,g,i)
    #

    heappop(h)
    if dp[i][min(g,m-1)] != -1:
        continue

    
    dp[i][min(g,m-1)] = t
    
    for v,a,b in edges[i]:
        if g-a >= 0 and dp[v][min(g-a,m-1)] == -1:
            heappush(h,(t+b,-(g-a),v))
#            print("push", t+b,-g+a,v)

    c,d = cd[i]
    heappush(h,(t+d,-(g+c),i))
    
#    if dp[i][min(g+c,m-1)] == -1:

for d in dp:
    pass
#    print(d)


for i in range(1, n):
    res = -1
    for v,a,b in edges[i]:
        min_t = -1
        for g in range(a,m):
            t = dp[v][g]
            if t == -1:
                continue
            if min_t == -1 or min_t > t:
                min_t = t
#                print("min_t", v,g,min_t)

        if res == -1 or res > min_t+b:
            res = min_t+b

#    print(dp[i])
    for t in dp[i]:
        if t == -1:
            continue
        if res == -1  or t < res:
            continue
            res = t
            
    print(res)

Submission status: Accepted

Solution code:
import collections
import heapq


class Dijkstra:
    def __init__(self):
        self.e = collections.defaultdict(list)

    def add(self, u, v, d):
        self.e[u].append([v, d])
        self.e[v].append([u, d])

    def delete(self, u, v):
        self.e[u] = [_ for _ in self.e[u] if _[0] != v]
        self.e[v] = [_ for _ in self.e[v] if _[0] != u]

    def search(self, s):
        """
        :param s: 始点
        :return: 始点から各点までの最短経路
        """
        d = collections.defaultdict(lambda: float('inf'))
        d[s] = 0
        q = []
        heapq.heappush(q, (0, s))
        v = collections.defaultdict(bool)
        while len(q):
            k, u = heapq.heappop(q)
            if v[u]:
                continue
            v[u] = True

            for uv, ud in self.e[u]:
                if v[uv]:
                    continue
                vd = k + ud
                if d[uv] > vd:
                    d[uv] = vd
                    heapq.heappush(q, (vd, uv))

        return d

N,M,S = map(int,input().split())
train = [list(map(int,input().split())) for i in range(M)]
change = [list(map(int,input().split())) for i in range(N)]

if S > 2500:
    S = 2500

G = Dijkstra()

for u,v,a,b in train:
    for i in range(a,2501):
        G.e[(u,i)].append([(v,i-a),b])
        G.e[(v,i)].append([(u,i-a),b])
for i in range(1,N+1):
    for j in range(2501-change[i-1][0]):
        G.e[(i,j)].append([(i,j+change[i-1][0]),change[i-1][1]])

A = G.search((1,S))

for i in range(2,N+1):
    print(min(A[(i,j)] for j in range(2501)))

Submission status: Accepted

Solution code:
import sys
import math
from collections import Counter, defaultdict
from heapq import heapify, heappop, heappush
import numpy as np
from array import array

# sys.setrecursionlimit(10**6)
# input = sys.stdin.buffer.readline

MAX_INT = 2**62-1
MOD = 10**9 + 7


if __name__ == "__main__":
    n, m, s = map(int, input().split())
    cost = {}
    time = {}
    g = defaultdict(list)

    for _ in range(m):
        u, v, a, b = map(int, input().split())
        cost[u, v] = cost[v, u] = a
        time[u, v] = time[v, u] = b
        g[u].append(v)
        g[v].append(u)

    for i in range(1, n+1):
        c, d = map(int, input().split())
        cost[i, i] = -c
        time[i, i] = d
        g[i].append(i)

    max_money = n * 50
    s = min(max_money, s)
    pq = [(0, 1, s)]
    time_usage = [[float('inf')] * (max_money+1) for _ in range(n+1)]
    time_usage[1][s] = 0

    while pq:
        t, cur, money = heappop(pq)
        if t > time_usage[cur][money]:
            continue
        for nxt in g[cur]:
            nt = t + time[cur, nxt]
            nm = min(money - cost[cur, nxt], max_money)
            if nm >= 0 and nt < time_usage[nxt][nm]:
                time_usage[nxt][nm] = nt
                heappush(pq, (nt, nxt, nm))

    for ts in time_usage[2:]:
        print(min(ts))

Submission status: Accepted

Solution code:
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True  and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

#from collections import defaultdict
import heapq
n,m,s = inm()
ST = 51*(n+1)
dst = [{} for i in range(n+1)]
for i in range(m):
    uu,vv,aa,bb = inm()
    dst[uu][vv] = (aa,bb)
    dst[vv][uu] = (aa,bb)
s = min(s,ST-1)
c = [-1]
d = [-1]
for i in range(n):
    cc,dd = inm()
    c.append(cc)
    d.append(dd)

dst2 = [[] for i in range((n+1)*ST)]
for u in range(1,n+1):
    for p in range(ST-c[u]):
        dst2[u*ST+p].append((u*ST+p+c[u], d[u]))
    for v in dst[u]:
        m = dst[u][v][0]
        t = dst[u][v][1]
        for p in range(m,ST):
            dst2[u*ST+p].append((v*ST+p-m,t))

if DBG:
    print("dst2)")
    for u,p in [(1,50),(2,50),(1,3)]:
        #z,pp = dst2[u*ST+p]
        ddprint("u {u} p {p} d2 {dst2[u*ST+p]}")
        for z in dst2[u*ST+p]:
            ddprint("v {z[0]//ST} q {z[0]%ST} t {z[1]}")

cost = [BIG]*((n+1)*ST)
q = [(0,1*ST+s)]
while len(q)>0:
    dd,u = heapq.heappop(q)
    if cost[u]<=dd:
        continue
    cost[u] = dd
    for v,t in dst2[u]:
        heapq.heappush(q,(dd+t, v))

if DBG:
    print("cost) ST {ST} s {s}")
    for u,p in [(2,204),(3,154),(4,154)]:
        ddprint("u {u} p {p} suf {u*ST+p} cost {cost[u*ST+p]}")

ddprint(cost)
ans = [BIG]*(n+1)
for i in range(2,n+1):
    ans[i] = min(cost[i*ST:(i+1)*ST])
    #ddprint(f"i {i} i*ST {i*ST}")
    ddprint(cost[i*ST:(i+1)*ST])
for i in range(2,n+1):
    print(ans[i])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect, heapq
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n,m,s0 = map(int,input().split())
s0 = min(2500,s0)
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,d = map(int,input().split())
  G[i].append((i,c,d))

def dijktra(g,s):
    n=len(g)
    dist = [[inf]*2501 for i in range(n)]
    dist[s][s0] = 0
    hq=[]
    heapq.heappush(hq,(0,s0,s))
    while hq:
        time,money,u = heapq.heappop(hq)
        if dist[u][money] < time: continue
        for v,money1,time1 in g[u]:
          M = min(2500,money+money1)
          if not M >= 0: continue
          if dist[v][M] > time + time1:
            dist[v][M] = (time + time1)
            heapq.heappush(hq,(time + time1, M,v))
    return dist

dist = dijktra(G,0)
for i in range(1,n):
  print(min(dist[i]))

Submission status: Accepted

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def dijkstra(nodes: list, src: int) -> list:
    from heapq import heappush, heappop

    N = len(nodes)
    MAX = 50**2
    res = list2d(N, MAX+1, INF)
    que = [(0, src, min(S, MAX))]
    res[src][min(S, MAX)] = 0
    while que:
        dist, u, coin  = heappop(que)
        if res[u][coin] < dist:
            continue
        if dist + D[u] < res[u][min(coin+C[u], MAX)]:
            res[u][min(coin+C[u], MAX)] = dist + D[u]
            heappush(que, (dist+D[u], u, min(coin+C[u], MAX)))
        for v, a, b in nodes[u]:
            if coin - a >= 0 and dist + b < res[v][coin-a]:
                res[v][coin-a] = dist + b
                heappush(que, (dist+b, v, coin-a))
    return res

N, M, S = MAP()
nodes = [[] for i in range(N)]
for _ in range(M):
    u, v, a, b = MAP()
    u -= 1; v -= 1
    nodes[u].append((v, a, b))
    nodes[v].append((u, a, b))
C = [0] * N
D = [0] * N
for i in range(N):
    c, d = MAP()
    C[i] = c
    D[i] = d

res = dijkstra(nodes, 0)
for i in range(1, N):
    print(min(res[i]))

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix


N, M, S = map(int, input().split())
uvab = [list(map(int, input().split())) for i in range(M)]
cd = [list(map(int, input().split())) for i in range(N)]

max_a = max([x[2] for x in uvab])
num_coins = max_a * M # <= 50 * 100 = 5,000
num_states = N * (num_coins + 1) # <= 50 * 5,001 = 250,050

d = []
row = []
col = []

for u, v, a, b in uvab:
  u -= 1; v -= 1
  i = (num_coins + 1) * u
  j = (num_coins + 1) * v
  for n in range(a, num_coins+1):
    d.extend([b, b])
    row.extend([i+n, j+n])
    col.extend([j+n-a, i+n-a])

for i, _cd in enumerate(cd):
  get, time = _cd
  start = i * (num_coins + 1)
  end = (i + 1) * (num_coins + 1)
  for j in range(start, end):
    if j + get < end:
      d.append(time)
      row.append(j)
      col.append(j + get)
    else:
      break

g = csr_matrix((d, (row, col)), shape=(num_states, num_states))

start_idx = min(S, num_coins)
dist = dijkstra(g, indices=start_idx).astype(int)
ans = []
for i in range(1, N):
  start = i * (num_coins + 1)
  end = (i + 1) * (num_coins + 1)
  _ans = float('inf')
  for j in range(start, end):
    _ans = min(_ans, dist[j])
  ans.append(_ans)

print(*ans, sep='\n')

Submission status: Accepted

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
from collections import deque
from fractions import gcd
from functools import lru_cache

import heapq


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#############
# Main Code #
#############

N,M,S = inputIL()

L = [[] for i in range(N+1)]

for _ in range(M):
  U,V,A,B = inputIL()
  L[U].append((V,A,B))
  L[V].append((U,A,B))
  
T = [(0,0)]

for _ in range(N):
  C,D = inputIL()
  T.append((C,D))
  
MAX = (N-1)*50

S = min(MAX,S)

dic = {}

for i in range(1,N+1):
  for s in range(MAX+1):
    dic[(i,s)] = []
    for item in L[i]:
      j,a,b = item
      if s >= a:
        dic[(i,s)].append(((j,s-a),b))
    c,d = T[i]
    dic[(i,s)].append(((i,min(s+c,MAX)),d))
    
a = [key for key in dic]

      

d = [[float("inf") for s in range(MAX+1)] for i in range(1,N+2)]
d[1][S] = 0
q = [(0,(1,S))]

while(len(q) != 0):
  ci,temp = heapq.heappop(q)
  i,s = temp
  if d[i][s]<ci:
    continue
  for item in dic[(i,s)]:
    temp,cj = item
    j,t = temp
    if d[j][t] > d[i][s] + cj:
      d[j][t] = d[i][s] + cj
      heapq.heappush(q,(d[j][t], (j,t)))

for item in d[2:]:
  print(min(item))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

N, M, S = map(int, input().split())
S = min(S, 2500)  # 2500枚持っていれば必ずどこにでも行ける

# UVABを読み込む
uvab_list = []
for i in range(M):
    U, V, A, B = map(int, input().split())
    uvab_list.append((U, V, A, B))

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

edge = { }
for U, V, A, B in uvab_list:
    for j in range(2501):  # 各辺に対して残りコストの分だけループ?
        if j - A >= 0:
            if not (U, j) in edge:
                edge[(U, j)] = []
            edge[(U, j)].append((B, (V, j - A)))
            if not (V, j) in edge:
                edge[(V, j)] = []
            edge[(V, j)].append((B, (U, j - A)))

# edge[V,c] <- 点Vでコストcのときに行ける辺のリスト、至る先と至ったあとでのコストを記録している

for i in range(N):
    C, D = cd_list[i]
    for j in range(2501):
        if not (i + 1, j) in edge:
            edge[(i + 1, j)] = []
        jj = min(2500, j + C)
        edge[(i + 1, j)].append((D, (i + 1, jj)))

import heapq
def dijkstra_heap(p):
    vlist=[]
    for i in range(1,N+1):
        for j in range(2501):
            vlist.append((i,j))
    d = {}
    used = {}
    INF = float("inf")
    for v in vlist:
        used[v] = True
        d[v] = INF
    # スタート地点
    d[p] = 0
    used[p] = False

    edgelist = []
    for e in edge[p]:
        heapq.heappush(edgelist,e)

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

        for e in edge[v]:
            if used[e[1]]: # 行き先に行ったことなかったら追加
                heapq.heappush(edgelist,(e[0]+d[v],e[1]))

    return d



# 両替所を自己ループとして解決している
res = dijkstra_heap((1,S))
final_result = [float("inf")]*N

for p in res:
    if final_result[p[0]-1] > res[p]:
        final_result[p[0]-1] = res[p]

for r in final_result[1:]:
    print(r)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect, heapq
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n,m,s0 = map(int,input().split())
s0 = min(2500,s0)
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,d = map(int,input().split())
  G[i].append((i,c,d))

def ceil(x,y):
  return (x-1)//y+1


def dijktra(g,s):
    n=len(g)
    dist = [[inf]*2501 for i in range(n)]
    dist[s][s0] = 0
    hq=[]
    heapq.heappush(hq,(0,s0,s))
    while hq:
        time,money,u = heapq.heappop(hq)
        if dist[u][money] < time: continue
        for v,money1,time1 in g[u]:
          M = min(2500,money+money1)
          if not M >= 0: continue
          if dist[v][M] > time + time1:
            dist[v][M] = (time + time1)
            heapq.heappush(hq,(time + time1, M,v))
    return dist

dist = dijktra(G,0)
# print(dist)
for i in range(1,n):
  print(min(dist[i]))

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
from pprint import pprint
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M, S = MAP()
graph = [[] for _ in range(N)]
for _ in range(M):
	U, V, A, B = MAP()
	graph[U-1].append((V-1, A, B))
	graph[V-1].append((U-1, A, B))

C, D = ZIP(N)

def Extdijkstra(E, start):
    global S
    N_d = len(E)
    M = 2500
    if S >= M: S = M-1
    dist = [[INF]*M for _ in range(N_d)]
    dist[start][S] = 0
    q = [(0, S, start)]

    while q:
        d, num, v = heappop(q)
        if num+C[v] < M and d+D[v] < dist[v][num+C[v]]:  # 自己ループ
            dist[v][num+C[v]] = d+D[v]
            heappush(q, (d+D[v], num+C[v], v))
        for node, c, t in E[v]:
            if num >= c and d + t < dist[node][num-c]:
                dist[node][num-c] = d+t
                heappush(q, (d+t, num-c, node))
    return dist

d = Extdijkstra(graph, 0)
for i in range(1, N):
	print(min(d[i]))

Submission status: Accepted

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

def run():
    # import sys
    # A = list(map(int, sys.stdin.readline().split()))
    # all = sys.stdin.readlines()
    # all = list(map(int, sys.stdin.read().split())
    #N, *A = map(int, open(0))
    #N = int(input())
    N, M, S = list(map(int, sysread().split()))
    to = [[] for _ in range(N+1)]
    max_m = 2500
    for _ in range(M):
        u,m,a,b = list(map(int, sysread().split()))
        to[u].append((m,b,a))
        to[m].append((u,b,a))


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

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

    state = [[1<<61] * (max_m+1) for _ in range(N+1)]

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

if __name__ == "__main__":
    run()

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
read = sys.stdin.read
 
n,m,s = [int(i) for i in readline().split()]
g = [[] for _ in range(n)]
for i in range(m):
    u,v,a,b = [int(i) for i in readline().split()]
    u -= 1
    v -= 1
    g[u].append((v,a,b))
    g[v].append((u,a,b))
 
 
cd = [int(i) for i in read().split()]
c = cd[::2]
d = cd[1::2]
 
 
from heapq import *
INF = 1<<61
M = 2500
if s >= M: s = M-1
dist = [[INF]*M for _ in range(n)] #startからの最短距離
dist[0][s] = 0
q = [(0,s,0)] #(そこまでの距離、銀の枚数、点)
 
while q:
    dv,num,v = heappop(q)
    if dist[v][num] < dv: continue
    if num+c[v] < M and dv+d[v] < dist[v][num+c[v]]:
        dist[v][num+c[v]] = dv + d[v]
        heappush(q, (dv + d[v], num+c[v] ,v))
    for to,a,b in g[v]:
        if num >= a and dv + b < dist[to][num-a]:
            dist[to][num-a] = dv + b
            heappush(q, (dv + b, num-a ,to))
    #print(q)
 
for i in range(1,n):
    print(min(dist[i]))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")

#solve
def solve():
    n, m, s = LI()
    uvab = LIR(m)
    cd = LIR(n)
    dp = [[inf] * 2501 for i in range(n)]
    edg = [[] for i in range(n)]
    for u, v, a, b in uvab:
        edg[u - 1].append((v - 1, a, b))
        edg[v - 1].append((u - 1, a, b))
    for i, (c, d) in enumerate(cd):
        edg[i].append((i, -c, d))
    if s >= 2501:
        s = 2500
    q = [(0, 0, s)]
    dp[0][s] = 0
    time = 0
    while q:
        time, p, score = heappop(q)
        for e, a, b in edg[p]:
            timebuf = time
            if 0 <= score - a <= 2500:
                timebuf += b
                if dp[e][score - a] > timebuf:
                    dp[e][score - a] = timebuf
                    heappush(q, (timebuf, e, score - a))
    
    for i in range(1, n):
        print(min(dp[i]))

    return


#main
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
from heapq import heappop, heappush


def solve(nn, mm, ss, line_list, cd_list):
    if ss > 5000:
        ss = 5000
    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] * ((nn + 1) * 10000)
    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(min(d[i * 10000:(i + 1) * 10000]))
    # 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: Accepted

Solution code:
def main():
    import heapq
    inf = 10**16
    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]*2501 for _ in [0]*n]
    h = [(0, 0, min(s, 2500))]  # 時刻、位置、所持金
    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], 2500)
        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()