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:
import sys,bisect,string,math,time,functools,random
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
def Golf():*a,=map(int,open(0))
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            a,b,c=(inp+[1])[:3]
            org_inp.append(inp)
        else:
            #index=0
            a,b,c=(list(ls[i])+[1])[:3]
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0}):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0}) # sample usage
    mp=[1]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[1]+[mp_def[j] for j in s]+[1]
    mp+=[1]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)];rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
input=lambda: sys.stdin.readline().rstrip()

class Comb:
    def __init__(self,n,mo=10**9+7):
        self.fac=[0]*(n+1)
        self.inv=[1]*(n+1)
        self.fac[0]=1
        self.fact(n)
        for i in range(1,n+1):
            self.fac[i]=i*self.fac[i-1]%mo
            self.inv[n]*=i
            self.inv[n]%=mo
        self.inv[n]=pow(self.inv[n],mo-2,mo)
        for i in range(1,n):
            self.inv[n-i]=self.inv[n-i+1]*(n-i+1)%mo
        return
    
    def fact(self,n):
        return self.fac[n]
        
    def invf(self,n):
        return self.inv[n]

    def comb(self,x,y):
        if y<0 or y>x:
            return 0
        return self.fac[x]*self.inv[x-y]*self.inv[y]%mo

show_flg=False
show_flg=True

class Tree:
    def __init__(self,inp_size=None,init=True):
        if init:
            self.stdin(inp_size)
        return

    def stdin(self,inp_size=None):
        if inp_size==None:
            self.size=int(input())
        else:
            self.size=inp_size
        self.edges,_=GI(self.size,self.size-1)
        return
    
    def listin(self,ls):
        self.size=len(ls)+1
        self.edges,_=GI(self.size,self.size-1,ls)
        return

    def __str__(self):
        return  str(self.edges)

    def dfs(self,x,func=lambda prv,nx,dist:prv+dist,root_v=0):
        q=deque()
        q.append(x)
        v=[-1]*self.size
        v[x]=root_v
        while q:
            c=q.pop()
            for nb,d in self.edges[c]:
                if v[nb]==-1:
                    q.append(nb)
                    v[nb]=func(v[c],nb,d)
        return v

    def EulerTour(self,x,func=lambda prv,nx,dist:prv+dist,root_v=0):
        q=deque()
        q.append((-1,x))
        v=[None]*self.size
        v[x]=root_v
        et=[]
        while q:
            cb,ce=q.pop()
            et.append(ce)
            for nb,d in self.edges[ce]:
                if v[nb]==None:
                    q.append((nb,ce))
                    q.append((ce,nb))
                    v[nb]=func(v[ce],nb,d)
        vid=[[-1,-1]for i in range(self.size)]
        for i,j in enumerate(et):
            if vid[j][0]==-1:
                vid[j][0]=i
            else:
                vid[j][1]=i
        return v,et,vid
    
    def LCA_init(self,depth,et):
        self.st=SegTree(self.size*2-1,func=min,ide=inf)
        for i,j in enumerate(et):
            self.st.update(i,j)
        self.LCA_init_stat==True
        return
    
    def LCA(self,root,x,y):
        if self.LCA_init_stat==False:
            depth,et,vid=self.EulerTour(root)
            self.LCA_init(depth,et)
        return self.st.query(x,y+1)


def dijkstra(edge,st):
    # edge=[[(v_to,dist_to_v),...],[],...]
    # initialize: def: d=dist(st,i), prev=[previous vertex in minimum path], q[]
    n=len(edge)
    d=[(0 if st==i else inf) for i in range(n)]
    prev=[0]*n
    q=[(j,i) for i,j in enumerate(d)]
    heapify(q)
    remain=set(range(n))
    # calc
    while q:
        dist,cur=heappop(q)
        if cur not in remain:
            continue
        remain.remove(cur)
        for dst,dist in edge[cur]:
            alt=d[cur]+dist
            if alt<d[dst]:
                d[dst]=alt
                prev[dst]=cur
                heappush(q,(alt,dst))
    return d,prev


n,m,s=LI()
t_ls=[]
k=1+n*50
s=min(k-1,s)
for i in range(m):
    u,v,a,b=LI()
    u-=1
    v-=1
    for j in range(a,k):
        t_ls+=[(u*k+j,v*k+j-a,b)]
        t_ls+=[(v*k+j,u*k+j-a,b)]

for i in range(n):
    c,d=LI()
    for j in range(k):
        t_ls+=[(i*k+j,i*k+min(j+c,k-1),d)]

gt,_=GI(n*k,len(t_ls),ls=t_ls,Directed=True,index=0)
dist_t,_=dijkstra(gt,0*k+s)

for i in range(1,n):
    print(min(dist_t[i*k:-~i*k]))

Submission status: Accepted

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

edges = [[] for _ in range(n)]
amax = 0
for _ in range(m):
   u, v, a, b = map(int, input().split())
   edges[u-1].append((v-1, a, b))
   edges[v-1].append((u-1, a, b))
   amax = max(a, amax)

lcoins = amax * (n - 1)

cost = []
time = []
for _ in range(n):
   c, d = map(int, input().split())
   cost.append(c)
   time.append(d)

from heapq import *


INF = 1<<61
M = 2500
if s >= M:
   s = M - 1

dist = [[INF] * M for _ in range(n)]
dist[0][s] = 0
q = [(0, s, 0)]

while q:
   dv, num, v = heappop(q)

   if dist[v][num] < dv:
      continue

   # update
   if num + cost[v] < M and dv + time[v] < dist[v][num+cost[v]]:
      dist[v][num+cost[v]] = dv + time[v]
      heappush(q, (dv+time[v], num+cost[v], v))

   for next, a, b in edges[v]:
      if num >= a and dv+b < dist[next][num-a]:
         dist[next][num-a] = dv+b
         heappush(q, (dv+b, num-a, next))


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

Submission status: Accepted

Solution code:
import heapq

def main():
    N, M, S = map(int, input().split())
    AB = [[] for _ in range(N)]
    maxA = 0
    for _ in range(M):
        u, v, a, b = map(int, input().split())
        AB[u - 1].append((a, b, v - 1))
        AB[v - 1].append((a, b, u - 1))
        maxA = max(maxA, a)
    for i in range(N):
        AB[i].sort()

    CD = [tuple(map(int, input().split())) for _ in range(N)]
    maxS = N * maxA
    cur = [(0, 0, S)]  # (time, station, silver)
    T = [-1] * N
    tc = N
    P = [-1] * N
    while tc:
        t, u, s = heapq.heappop(cur)
        if s <= P[u]:
            continue
        P[u] = s
        if T[u] == -1:
            T[u] = t
            tc -= 1
        for a, b, v in AB[u]:
            if s < a:
                break
            if P[v] < s - a:
                heapq.heappush(cur, (t + b, v, s - a))
        if s != maxS:
            c, d = CD[u]
            min_a = AB[u][0][0]
            k = max(1, (min_a - s + c  - 1) // c)
            heapq.heappush(cur, (t + k * d, u, min(s + k * c, maxS)))
    print('\n'.join(map(str, T[1:])))

main()

Submission status: Accepted

Solution code:
import heapq
def main():
    N, M, S = map(int, input().split())
    maxS = 50 * (N-1)
    cost = [[] for _ in range(N)]
    for _ in range(M):
        U, V, A, B = map(int, input().split())
        U = U - 1
        V = V - 1
        cost[U].append((A,B,V))
        cost[V].append((A,B,U))
    for i in range(N):
        cost[i].sort()
    r = []
    for _ in range(N):
        C, D = map(int, input().split())
        r.append((C,D))
    time = [-1] * N
    money = [-1] * N
    used = set()
    cities = N
    q = [(0, S, 0)] # time, silver, city
    count = 0
    while cities:
        count += 1
        t, s, ci = heapq.heappop(q)
        if (s, ci) in used or money[ci] >= s:
            continue
        used.add((s, ci))
        if time[ci] == -1:
            time[ci] = t
            money[ci] = s
            cities -= 1
        for a, b, v in cost[ci]:
            if s < a:
                break
            if (s-a, v) not in used and money[v] < s-a:
                heapq.heappush(q, (t+b, s-a, v))
        if s != maxS:
            c, d = r[ci]
            m = cost[ci][0][0]
            k = max(1, (m-s+c-1)//c)
            if (s+c, ci) not in used:
                heapq.heappush(q, (t+d*k, min(s+c*k, maxS), ci))
    for i in time[1:]:
        print(i)
main()

Submission status: Accepted

Solution code:
import heapq

def main():
    N, M, S = map(int, input().split())
    AB = [[] for _ in range(N)]
    maxA = 0
    for _ in range(M):
        u, v, a, b = map(int, input().split())
        AB[u - 1].append((a, b, v - 1))
        AB[v - 1].append((a, b, u - 1))
        maxA = max(maxA, a)
    for i in range(N):
        AB[i].sort()

    CD = [tuple(map(int, input().split())) for _ in range(N)]
    maxS = N * maxA
    cur = [(0, 0, S)]  # (time, station, silver)
    T = [-1] * N
    tc = N
    P = [-1] * N
    while tc:
        t, u, s = heapq.heappop(cur)
        if s <= P[u]:
            continue
        P[u] = s
        if T[u] == -1:
            T[u] = t
            tc -= 1
        for a, b, v in AB[u]:
            if s < a:
                break
            heapq.heappush(cur, (t + b, v, s - a))
        if s != maxS:
            c, d = CD[u]
            min_a = AB[u][0][0]
            k = max(1, (min_a - s + c  - 1) // c)
            heapq.heappush(cur, (t + k * d, u, min(s + k * c, maxS)))
    print('\n'.join(map(str, T[1:])))

main()

Submission status: Accepted

Solution code:
import heapq
INF = 10**20

N, M, S = map(int, input().split())
adj = [[] for _ in range(N)]
for m in range(M):
    u,v,a,b = map(int, input().split())
    u -= 1
    v -= 1
    adj[u].append((v,a,b))
    adj[v].append((u,a,b))

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

M = 2500
S = min(S, M-1) # 2500枚あれば十分
dist = [[INF]*M for _ in range(N)] # dist[都市][銀貨の枚数]
dist[0][S] = 0
pq = [(0,S,0)] # (時間、銀貨の枚数、都市)

while pq:
    d, sil, node = heapq.heappop(pq)
    if dist[node][sil] < d: # 探索の対象にする必要があるか確認
        continue 
     # 銀貨に交換したとして、上限を超えないか、探索の必要があるか
    if sil+C[node] < M and d+D[node] < dist[node][sil+C[node]]:
        dist[node][sil+C[node]] = d + D[node] # 時間の更新
        heapq.heappush(pq, (d + D[node], sil+C[node] ,node))
    for next, a, b in adj[node]:
        # 銀貨が足りるか、探索の必要があるか
        if sil >= a and d + b < dist[next][sil-a]:
            dist[next][sil-a] = d + b
            heapq.heappush(pq, (d + b, sil-a ,next))

for i in range(1,N):
    print(min(dist[i])) # 残っている銀貨の枚数は問わない

Submission status: Accepted

Solution code:
import heapq
INF = 10**20

N, M, S = map(int, input().split())
adj = [[] for _ in range(N)]
for m in range(M):
    u,v,a,b = map(int, input().split())
    u -= 1
    v -= 1
    adj[u].append((v,a,b))
    adj[v].append((u,a,b))

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

M = 2500
S = min(S, M-1) # 2500枚あれば十分
dist = [[INF]*M for _ in range(N)] # dist[都市][銀貨の枚数]
dist[0][S] = 0
q = [(0,S,0)] # (距離、銀貨の枚数、都市)

while q:
    d, sil, node = heapq.heappop(q)
    if dist[node][sil] < d: # 探索の対象にする必要があるか確認
        continue 
    if sil+C[node] < M and d+D[node] < dist[node][sil+C[node]]:
        dist[node][sil+C[node]] = d + D[node]
        heapq.heappush(q, (d + D[node], sil+C[node] ,node))
    for to,a,b in adj[node]:
        if sil >= a and d + b < dist[to][sil-a]:
            dist[to][sil-a] = d + b
            heapq.heappush(q, (d + b, sil-a ,to))

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

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

from heapq import heappop, heappush

N,M,S = LI()
U,V,A,B = LIR(M,4)
C,D = LIR(N,2)

max_ = (N-1)*max(A)
E = [dict() for _ in range(N*(max_+1))]

def number(i,j):
    return i*(max_+1)+j

def dijkstra(E,s,n):
    d = [10**9*(max_+1)*N]*n
    d[s] = 0
    q = []
    heappush(q,(0,s))
    while q:
        du,u = heappop(q)
        if d[u] < du:
            continue
        for v,weight in E[u].items():
            dnew = du + weight
            if d[v] > dnew:
                d[v] = dnew
                heappush(q,(dnew,v))
    return d

for i in range(N):
    for j in range(max_-C[i]+1):
        E[number(i,j)][number(i,j+C[i])] = D[i]

for i in range(M):
    for j in range(A[i],max_+1):
        E[number(U[i]-1,j)][number(V[i]-1,j-A[i])] = B[i]
        E[number(V[i]-1,j)][number(U[i]-1,j-A[i])] = B[i]

d = dijkstra(E,min(S,max_),N*(max_+1))

for i in range(1,N):
    ans = float('inf')
    for j in range(max_+1):
        if d[number(i,j)] < ans:
            ans = d[number(i,j)]
    print(ans)

Submission status: Accepted

Solution code:
import sys,bisect,string,math,time,functools,random
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
def Golf():*a,=map(int,open(0))
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            a,b,c=(inp+[1])[:3]
            org_inp.append(inp)
        else:
            #index=0
            a,b,c=(list(ls[i])+[1])[:3]
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0}):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0}) # sample usage
    mp=[1]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[1]+[mp_def[j] for j in s]+[1]
    mp+=[1]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)];rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
input=lambda: sys.stdin.readline().rstrip()

class Comb:
    def __init__(self,n,mo=10**9+7):
        self.fac=[0]*(n+1)
        self.inv=[1]*(n+1)
        self.fac[0]=1
        self.fact(n)
        for i in range(1,n+1):
            self.fac[i]=i*self.fac[i-1]%mo
            self.inv[n]*=i
            self.inv[n]%=mo
        self.inv[n]=pow(self.inv[n],mo-2,mo)
        for i in range(1,n):
            self.inv[n-i]=self.inv[n-i+1]*(n-i+1)%mo
        return
    
    def fact(self,n):
        return self.fac[n]
        
    def invf(self,n):
        return self.inv[n]

    def comb(self,x,y):
        if y<0 or y>x:
            return 0
        return self.fac[x]*self.inv[x-y]*self.inv[y]%mo

show_flg=False
show_flg=True

class Tree:
    def __init__(self,inp_size=None,init=True):
        if init:
            self.stdin(inp_size)
        return

    def stdin(self,inp_size=None):
        if inp_size==None:
            self.size=int(input())
        else:
            self.size=inp_size
        self.edges,_=GI(self.size,self.size-1)
        return
    
    def listin(self,ls):
        self.size=len(ls)+1
        self.edges,_=GI(self.size,self.size-1,ls)
        return

    def __str__(self):
        return  str(self.edges)

    def dfs(self,x,func=lambda prv,nx,dist:prv+dist,root_v=0):
        q=deque()
        q.append(x)
        v=[-1]*self.size
        v[x]=root_v
        while q:
            c=q.pop()
            for nb,d in self.edges[c]:
                if v[nb]==-1:
                    q.append(nb)
                    v[nb]=func(v[c],nb,d)
        return v

    def EulerTour(self,x,func=lambda prv,nx,dist:prv+dist,root_v=0):
        q=deque()
        q.append((-1,x))
        v=[None]*self.size
        v[x]=root_v
        et=[]
        while q:
            cb,ce=q.pop()
            et.append(ce)
            for nb,d in self.edges[ce]:
                if v[nb]==None:
                    q.append((nb,ce))
                    q.append((ce,nb))
                    v[nb]=func(v[ce],nb,d)
        vid=[[-1,-1]for i in range(self.size)]
        for i,j in enumerate(et):
            if vid[j][0]==-1:
                vid[j][0]=i
            else:
                vid[j][1]=i
        return v,et,vid
    
    def LCA_init(self,depth,et):
        self.st=SegTree(self.size*2-1,func=min,ide=inf)
        for i,j in enumerate(et):
            self.st.update(i,j)
        self.LCA_init_stat==True
        return
    
    def LCA(self,root,x,y):
        if self.LCA_init_stat==False:
            depth,et,vid=self.EulerTour(root)
            self.LCA_init(depth,et)
        return self.st.query(x,y+1)


def dijkstra(edge,st):
    # edge=[[(v_to,dist_to_v),...],[],...]
    # initialize: def: d=dist(st,i), prev=[previous vertex in minimum path], q[]
    n=len(edge)
    d=[(0 if st==i else inf) for i in range(n)]
    prev=[0]*n
    q=[(j,i) for i,j in enumerate(d)]
    heapify(q)
    
    # calc
    while q:
        dist,cur=heappop(q)
        for dst,dist in edge[cur]:
            alt=d[cur]+dist
            if alt<d[dst]:
                d[dst]=alt
                prev[dst]=cur
                heappush(q,(alt,dst))
    return d,prev


n,m,s=LI()
t_ls=[]
k=1+n*50
s=min(k-1,s)
for i in range(m):
    u,v,a,b=LI()
    u-=1
    v-=1
    for j in range(a,k):
        t_ls+=[(u*k+j,v*k+j-a,b)]
        t_ls+=[(v*k+j,u*k+j-a,b)]

for i in range(n):
    c,d=LI()
    for j in range(k):
        t_ls+=[(i*k+j,i*k+min(j+c,k-1),d)]

gt,_=GI(n*k,len(t_ls),ls=t_ls,Directed=True,index=0)
dist_t,_=dijkstra(gt,0*k+s)

for i in range(1,n):
    print(min(dist_t[i*k:-~i*k]))

Submission status: Accepted

Solution code:
import heapq

n, m, s = [int(x) for x in input().split()]
adj = [[] for u in range(n + 1)]
for e in range(m):
    u, v, a, b = [int(x) for x in input().split()]
    adj[u].append((v, a, b))
    adj[v].append((u, a, b))
exchange = [[int(x) for x in input().split()] if u else [] for u in range(n + 1)]
def bound(s):
    return min(s, n * 50)
pq, done, d = [(0, 1, bound(s))], set(), {(1, bound(s)): 0}
ans = [float('inf') for u in range(n + 1)]
while len(pq) > 0:
    dist, u, s = heapq.heappop(pq)
    ans[u] = min(ans[u], dist)
    if (u, s) not in done:
        for v, a, b in adj[u]:
            if s >= a and d.get((v, bound(s - a)), float('inf')) > d[u, s] + b:
                d[v, bound(s - a)] = d[u, s] + b
                heapq.heappush(pq, (d[v, bound(s - a)], v, bound(s - a)))
        c, t = exchange[u]
        if d.get((u, bound(s + c)), float('inf')) > d[u, s] + t:
            d[u, bound(s + c)] = d[u, s] + t
            heapq.heappush(pq, (d[u, bound(s + c)], u, bound(s + c)))
        done.add((u, s))

print(*(ans[u] for u in range(2, n + 1)), sep='\n')

Submission status: Accepted

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

N,M,S = map(int,input().split())
UVAB = [list(map(int,input().split())) for i in range(M)]
U,V,A,B = zip(*UVAB)

'''
from itertools import combinations 
N = 14
M = N*(N-1)//2
S = 0
UVAB = [[x,y,50,10**9] for x,y in combinations(range(1,N+1),2)] 
U,V,A,B = zip(*UVAB)
'''

mc = max(A)* M
g = defaultdict(list)

for u,v,a,b in UVAB:
    for i in range(a,mc+1):
        g[(u,i)].append(((v,i-a),b))
        g[(v,i)].append(((u,i-a),b))

CD = [[0,0]] + [list(map(int,input().split())) for i in range(N)]
#CD = [[0,0]] + [[10**9,10**9] for i in range(N)]
C,D = zip(*CD)
C = [min(c,mc) for c in C]

for i in range(1,N+1):
    for c in range(mc+1-C[i]):
        g[(i,c)].append(((i,c+C[i]),D[i]))

S = min(S,mc)
dq = [(0,S,1)]

ans = [[10**15 for j in range(mc+1)] for i in range(N+1)]
while dq:
    t, w, v = heappop(dq)
    if ans[v][w] <= t:
        continue
    for i in range(w+1):
        ans[v][i] = min(t, ans[v][i])
    for (nv,nw), nt in g[(v,w)]:
        if ans[nv][nw] > t + nt:
            heappush(dq,(t+nt,nw,nv))

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

Submission status: Accepted

Solution code:
from heapq import heappop,heappush
inf = float("inf")

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

G = [[] for _ in range(n)]
for _ in range(m):
    u,v,cost,time = map(int,input().split())
    u -= 1
    v -= 1
    G[u].append((v,cost,time))
    G[v].append((u,cost,time))

for i in range(n):
    cost,time = map(int,input().split())
    G[i].append((i,-cost,time))

# mint[i][j]
# 銀貨j枚を持って都市iに着くことができる最小時間
mint = [[inf]*2451 for _ in range(n)]

# color[i][j]
# 銀貨j枚を持って都市iに着くことができる最小時間が確定したか
white = 0
black = 1
color = [[white]*2451 for _ in range(n)]

def dijkstra(u,s):
    # 銀貨50枚で49回移動が最大コスト、いらない分は捨てる
    s = min(s,2450)
    mint[u][s] = 0
    color[u][s] = black

    PQ = []
    heappush(PQ,(0,u,s))
    while PQ:
        # minv: PQ内の最小値
        # now: 今いる都市
        # nowcoins: 今持っている銀貨
        minv,now,nowcoins = heappop(PQ)
        color[now][nowcoins] = black
        # 最小時間じゃないなら無視
        if mint[now][nowcoins] < minv: continue
        
        # nxt: 次に行く都市
        # cost: 次の都市に行くのに使う銀貨
        # time: 次の都市に行くのにかかる時間
        # nxtcoins: 次の都市に行った段階で持っている銀貨
        for nxt,cost,time in G[now]:
            nxtcoins = min(nowcoins - cost,2450)
            if nxtcoins < 0: continue
            if color[nxt][nxtcoins]: continue
            if mint[nxt][nxtcoins] > minv + time:
                mint[nxt][nxtcoins] = minv + time
                heappush(PQ,(mint[nxt][nxtcoins],nxt,nxtcoins))

dijkstra(0,s)

# for i in range(n): print(mint[i])
# for i in range(n): print(color[i])
for i in range(1,n): print(min(mint[i]))

Submission status: Accepted

Solution code:
from heapq import heappop,heappush
inf = float("inf")

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

G = [[] for _ in range(n)]
for _ in range(m):
    u,v,cost,time = map(int,input().split())
    u -= 1
    v -= 1
    G[u].append((v,cost,time))
    G[v].append((u,cost,time))

for i in range(n):
    cost,time = map(int,input().split())
    G[i].append((i,-cost,time))

# mint[i][j]
# 銀貨j枚を持って都市iに着くことができる最小時間
mint = [[inf]*2451 for _ in range(n)]

# color[i][j]
# 銀貨j枚を持って都市iに着くことができる最小時間が確定したか
white = 0
black = 1
color = [[white]*2451 for _ in range(n)]

def dijkstra(u,s):
    # 銀貨50枚で49回移動が最大コスト、いらない分は捨てる
    s = min(s,2450)
    mint[u][s] = 0
    color[u][s] = black

    PQ = []
    heappush(PQ,(0,u,s))
    while PQ:
        # minv: PQ内の最小値
        # now: 今いる都市
        # nowcoins: 今持っている銀貨
        minv,now,nowcoins = heappop(PQ)
        color[now][nowcoins] = black
        
        # nxt: 次に行く都市
        # cost: 次の都市に行くのに使う銀貨
        # time: 次の都市に行くのにかかる時間
        # nxtcoins: 次の都市に行った段階で持っている銀貨
        for nxt,cost,time in G[now]:
            nxtcoins = min(nowcoins - cost,2450)
            if nxtcoins < 0: continue
            if color[nxt][nxtcoins]: continue
            if mint[nxt][nxtcoins] > minv + time:
                mint[nxt][nxtcoins] = minv + time
                heappush(PQ,(mint[nxt][nxtcoins],nxt,nxtcoins))

dijkstra(0,s)

# for i in range(n): print(mint[i])
# for i in range(n): print(color[i])
for i in range(1,n): print(min(mint[i]))