Problem:


Score : 500 points

Problem Statement

There are N cities numbered 1 to N, connected by M railroads.

You are now at City 1, with 10^{100} gold coins and S silver coins in your pocket.

The i-th railroad connects City U_i and City V_i bidirectionally, and a one-way trip costs A_i silver coins and takes B_i minutes.
You cannot use gold coins to pay the fare.

There is an exchange counter in each city. At the exchange counter in City i, you can get C_i silver coins for 1 gold coin.
The transaction takes D_i minutes for each gold coin you give.
You can exchange any number of gold coins at each exchange counter.

For each t=2, ..., N, find the minimum time needed to travel from City 1 to City t. You can ignore the time spent waiting for trains.

Constraints

2 \leq N \leq 50

N-1 \leq M \leq 100

0 \leq S \leq 10^9

1 \leq A_i \leq 50

1 \leq B_i,C_i,D_i \leq 10^9

1 \leq U_i < V_i \leq N

There is no pair i, j(i \neq j) such that (U_i,V_i)=(U_j,V_j).

Each city t=2,...,N can be reached from City 1 with some number of railroads.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M S
U_1 V_1 A_1 B_1
:
U_M V_M A_M B_M
C_1 D_1
:
C_N D_N

Output

For each t=2, ..., N in this order, print a line containing the minimum time needed to travel from City 1 to City t.

Sample Input 1

3 2 1
1 2 1 2
1 3 2 4
1 11
1 2
2 5

Sample Output 1

2
14

The railway network in this input is shown in the figure below.

In this figure, each city is labeled as follows:

The first line: the ID number i of the city (i for City i)

The second line: C_i / D_i

Similarly, each railroad is labeled as follows:

The first line: the ID number i of the railroad (i for the i-th railroad in input)

The second line: A_i / B_i

You can travel from City 1 to City 2 in 2 minutes, as follows:

Use the 1-st railroad to move from City 1 to City 2 in 2 minutes.

You can travel from City 1 to City 3 in 14 minutes, as follows:

Use the 1-st railroad to move from City 1 to City 2 in 2 minutes.

At the exchange counter in City 2, exchange 3 gold coins for 3 silver coins in 6 minutes.

Use the 1-st railroad to move from City 2 to City 1 in 2 minutes.

Use the 2-nd railroad to move from City 1 to City 3 in 4 minutes.

Sample Input 2

4 4 1
1 2 1 5
1 3 4 4
2 4 2 2
3 4 1 1
3 1
3 1
5 2
6 4

Sample Output 2

5
5
7

The railway network in this input is shown in the figure below:

You can travel from City 1 to City 4 in 7 minutes, as follows:

At the exchange counter in City 1, exchange 2 gold coins for 6 silver coins in 2 minutes.

Use the 2-nd railroad to move from City 1 to City 3 in 4 minutes.

Use the 4-th railroad to move from City 3 to City 4 in 1 minutes.

Sample Input 3

6 5 1
1 2 1 1
1 3 2 1
2 4 5 1
3 5 11 1
1 6 50 1
1 10000
1 3000
1 700
1 100
1 1
100 1

Sample Output 3

1
9003
14606
16510
16576

The railway network in this input is shown in the figure below:

You can travel from City 1 to City 6 in 16576 minutes, as follows:

Use the 1-st railroad to move from City 1 to City 2 in 1 minute.

At the exchange counter in City 2, exchange 3 gold coins for 3 silver coins in 9000 minutes.

Use the 1-st railroad to move from City 2 to City 1 in 1 minute.

Use the 2-nd railroad to move from City 1 to City 3 in 1 minute.

At the exchange counter in City 3, exchange 8 gold coins for 8 silver coins in 5600 minutes.

Use the 2-nd railroad to move from City 3 to City 1 in 1 minute.

Use the 1-st railroad to move from City 1 to City 2 in 1 minute.

Use the 3-rd railroad to move from City 2 to City 4 in 1 minute.

At the exchange counter in City 4, exchange 19 gold coins for 19 silver coins in 1900 minutes.

Use the 3-rd railroad to move from City 4 to City 2 in 1 minute.

Use the 1-st railroad to move from City 2 to City 1 in 1 minute.

Use the 2-nd railroad to move from City 1 to City 3 in 1 minute.

Use the 4-th railroad to move from City 3 to City 5 in 1 minute.

At the exchange counter in City 5, exchange 63 gold coins for 63 silver coins in 63 minutes.

Use the 4-th railroad to move from City 5 to City 3 in 1 minute.

Use the 2-nd railroad to move from City 3 to City 1 in 1 minute.

Use the 5-th railroad to move from City 1 to City 6 in 1 minute.

Sample Input 4

4 6 1000000000
1 2 50 1
1 3 50 5
1 4 50 7
2 3 50 2
2 4 50 4
3 4 50 3
10 2
4 4
5 5
7 7

Sample Output 4

1
3
5

The railway network in this input is shown in the figure below:

Sample Input 5

2 1 0
1 2 1 1
1 1000000000
1 1

Sample Output 5

1000000001

The railway network in this input is shown in the figure below:

You can travel from City 1 to City 2 in 1000000001 minutes, as follows:

At the exchange counter in City 1, exchange 1 gold coin for 1 silver coin in 1000000000 minutes.

Use the 1-st railroad to move from City 1 to City 2 in 1 minute.



Sample input:
3 2 1
1 2 1 2
1 3 2 4
1 11
1 2
2 5


Sample output:
2
14

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
from scipy.sparse import*
(n,m,s,*D),*t=[map(int,t.split())for t in open(0)]
R,C=[],[]
r=range(2501)
for u,v,a,b in t[:m]:
 for i in r:k=(i+a)*51;R+=k+u,k+v;C+=i*51+v,i*51+u;D+=b,b
for i,(c,d)in enumerate(t[m:],1):
 for j in r:R+=j*51+i,;C+=(j+c)*51+i,;D+=d,
d=csgraph.dijksta(csr_matrix((D,(R,C))),1,min(2500,s)*51+1)
for i in range(2,n+1):print(int(min(d[i::51])))

Submission status: Runtime Error

Solution code:
from scipy.sparse import*
(n,m,s,*D),*t=[map(int,t.split())for t in open(0)]
R,C=[],[]
r=range(2501)
for u,v,a,b in t[:m]:
 for i in r:k=(i+a)*51;R+=k+u,k+v;C+=i*51+v,i*51+u;D+=b,b
for i,(c,d)in enumerate(t[m:],1):
 for j in r:R+=j*51+i,;C+=(j+c)*51+i,;D+=d,
d=csgraph.johnson(csr_matrix((D,(R,C))),1,min(2500,s)*51+1)
for i in range(2,n+1):print(int(min(d[i::51])))

Submission status: Runtime Error

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)
    v=[False]*n
    # calc
    while q:
        dist,cur=heappop(q)
        if v[cur]:
            continue
        v[cur]=True
        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


sx,sy,gx,gy=LI()
n=I()
 
c=[(sx,sy,0),(gx,gy,0)]
for i in range(n):
    c+=[LI()]

n+=2
g=[[]for i in range(n)]
for i in range(n):
    for j in range(i+1,n):
        x,y,r1=c[i]
        s,t,r2=c[j]
        d=math.hypot(x-s,y-t) -r1 -r2
        if d<0:d=0
        g[i].append((j,d))
        g[j].append((i,d))
d,_=dijkstra(g,0)
print(d[1])

Submission status: Runtime Error

Solution code:

Submission status: Runtime Error

Solution code:
N,M,S = map(int,input().split())
edges = [[] for _ in range(2500*50 + 5)]
def indexer(city,coin):
    return 50*coin + city

for _ in range(M):
    u,v,a,b = map(int,input().split())
    u -= 1
    v -= 1
    for scoin in range(a,2501):
        edges[indexer(u,scoin)].append([b,indexer(v,scoin-a)])
        edges[indexer(v,scoin)].append([b,indexer(u,scoin-a)])
## 両替
for i in range(N):
    c,d = map(int,input().split())
    for scoin in range(c,2501):
        edges[indexer(i,scoin-c)].append([d,indexer(i,scoin)])


def dijkstra(s,n,edges):
    import heapq
    dist = [float('inf')] * n
    fixed = [False]*n
    dist[s] = 0
    fixed[s] = True
    priority_que = []
    for e in edges[s]:
        heapq.heappush(priority_que,e)

    while len(priority_que):
        edge = heapq.heappop(priority_que)
        if fixed[edge[1]]:
            continue
        v = edge[1]
        dist[v] = edge[0]
        fixed[v] = True
        for ne in edges[v]:
            heapq.heappush(priority_que,[ne[0]+dist[v], ne[1]])
    return dist

d=dijkstra(indexer(0,min(2500,S)),2500*50 + 5,edges)
for i in range(1,N):
    ans = float('inf')
    for j in range(2501):
        ans = min(ans,d[indexer(i,j)])
    print(ans)

Submission status: Runtime Error

Solution code:
# coding: utf-8
import sys
from heapq import heapify, heappop, heappush

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# 同じ地点で銀貨の枚数によって別の状態として扱う（最大max(A)*(N-1))
N, M, S = lr()
UVAB = [lr() for _ in range(M)]
CD = [lr() for _ in range(N)]  # 0-indexed
Amax = 0
for i in range(M):
    a = UVAB[i][2]
    if a > Amax:
        Amax = a

limit = Amax*(N-1)
graph = [[] for _ in range(N+1)] # 1-indexed
for u, v, a, b in UVAB:
    graph[u].append((v, a, b))
    graph[v].append((u, a, b))

def dijkstra(start):
    # 時間、銀貨の枚数、現在地をqueへ
    INF = 10 ** 15
    dist = [[INF for _ in range(limit+1)] for _ in range(N+1)]
    dist[1][S] = 0
    que = [(0, S, 1)]
    while que:
        time, silver, prev = heappop(que)
        if dist[prev][silver] < time:
            continue
        for next, a, b in graph[prev]:
            t = time + b
            si = silver - a
            if si < 0:
                continue
            if dist[next][si] > t:
                dist[next][si] = t
                heappush(que, (t, si, next))
        c, d = CD[prev-1]
        si = min(limit, silver+c)
        while dist[prev][si] > time + d:
            dist[prev][si] = time + d
            heappush(que, (time+d, si, prev))
            si += c; si = min(limit, si)
            time += d
            
    return dist

dist = dijkstra(1)
for i in range(2, N+1):
    d = dist[i]
    answer = min(d)
    print(answer)

# 52

Submission status: Runtime Error

Solution code:
import queue
def dijkstra(n,EdgeMatrix,start):

    NodeList=queue.PriorityQueue() #探索対象の頂点
    Distance=[float('inf')]*n #頂点0からの最短経路
    used=[False]*n #頂点の使用情報

    Distance[start]=0 #0から0までの距離は0
    used[start]=True #0から探索を始める
    LastNode=start #最新の頂点
    NodeList.put([0,start])

    while not NodeList.empty():
        for i in range(len(EdgeMatrix[LastNode])):
            #探索していない頂点へ距離の短い辺があればキューに追加
            Edge=EdgeMatrix[LastNode][i]
            if used[Edge[0]]==False and Distance[Edge[0]]>Distance[LastNode]+Edge[1]:
                    Distance[Edge[0]]=Distance[LastNode]+Edge[1]
                    NodeList.put([Distance[Edge[0]],Edge[0]])

        #最も近い探索していない頂点
        while not NodeList.empty():
            minNode=NodeList.get()
            if used[minNode[1]]==False:
                break

        LastNode=minNode[1] #最新の頂点を更新
        used[minNode[1]]=True #頂点の使用情報を更新
    return Distance

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

#辺の隣接リスト
EdgeMatrix=[[] for i in range(125000)]

for i in range(m):
    u,v,a,b=map(int,input().split())
    for j in range(a,2500):
        EdgeMatrix[(u-1)*2500+j].append([(v-1)*2500+j-a,b])
        EdgeMatrix[(v-1)*2500+j].append([(u-1)*2500+j-a,b])

for i in range(n):
    c,d=map(int,input().split())
    for j in range(2450):
        EdgeMatrix[i*2500+j].append([min(i*2500+j+c,(i+1)*2500-1),d])

#for i in range(7500,7600):
#    print(EdgeMatrix[i])
    
#頂点0からの最短経路
Distance=dijkstra(125000,EdgeMatrix,s)

for i in range(1,n):
    print(min(Distance[i*2500:(i+1)*2500-1]))

Submission status: Runtime Error

Solution code:
import queue
def dijkstra(n,EdgeMatrix,start):

    NodeList=queue.PriorityQueue() #探索対象の頂点
    Distance=[float('inf')]*n #頂点0からの最短経路
    used=[False]*n #頂点の使用情報

    Distance[start]=0 #0から0までの距離は0
    used[start]=True #0から探索を始める
    LastNode=start #最新の頂点
    count=1 #つないだ頂点の数
    Flag=True

    while not NodeList.empty() or Flag:
        Flag=False
        for i in range(len(EdgeMatrix[LastNode])):
            #探索していない頂点へ距離の短い辺があればキューに追加
            Edge=EdgeMatrix[LastNode][i]
            if used[Edge[0]]==False and Distance[Edge[0]]>Distance[LastNode]+Edge[1]:
                    Distance[Edge[0]]=Distance[LastNode]+Edge[1]
                    NodeList.put([Distance[Edge[0]],Edge[0]])

        #最も近い探索していない頂点
        while True:
            minNode=NodeList.get()
            if used[minNode[1]]==False:
                break

        LastNode=minNode[1] #最新の頂点を更新
        used[minNode[1]]=True #頂点の使用情報を更新
        count+=1 #つないだ頂点の数を更新
    return Distance

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

#辺の隣接リスト
EdgeMatrix=[[] for i in range(125000)]

for i in range(m):
    u,v,a,b=map(int,input().split())
    for j in range(a,2500):
        EdgeMatrix[(u-1)*2500+j].append([(v-1)*2500+j-a,b])
        EdgeMatrix[(v-1)*2500+j].append([(u-1)*2500+j-a,b])

for i in range(n):
    c,d=map(int,input().split())
    for j in range(2450):
        EdgeMatrix[i*2500+j].append([min(i*2500+j+c,(i+1)*2500-1),d])

#for i in range(7500,7600):
#    print(EdgeMatrix[i])
    
#頂点0からの最短経路
Distance=dijkstra(125000,EdgeMatrix,s)

for i in range(1,n):
    print(min(Distance[i*2500:(i+1)*2500-1]))

Submission status: Runtime Error

Solution code:
import queue
def dijkstra(n,EdgeMatrix,start):

    NodeList=queue.PriorityQueue() #探索対象の頂点
    Distance=[float('inf')]*n #頂点0からの最短経路
    used=[False]*n #頂点の使用情報

    Distance[start]=0 #0から0までの距離は0
    used[start]=True #0から探索を始める
    LastNode=start #最新の頂点
    count=1 #つないだ頂点の数

    while count<n:
        for i in range(len(EdgeMatrix[LastNode])):
            #探索していない頂点へ距離の短い辺があればキューに追加
            Edge=EdgeMatrix[LastNode][i]
            if used[Edge[0]]==False and Distance[Edge[0]]>Distance[LastNode]+Edge[1]:
                    Distance[Edge[0]]=Distance[LastNode]+Edge[1]
                    NodeList.put([Distance[Edge[0]],Edge[0]])

        #最も近い探索していない頂点
        while True:
            minNode=NodeList.get()
            if used[minNode[1]]==False:
                break

        LastNode=minNode[1] #最新の頂点を更新
        used[minNode[1]]=True #頂点の使用情報を更新
        count+=1 #つないだ頂点の数を更新
    return Distance

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

#辺の隣接リスト
EdgeMatrix=[[] for i in range(125000)]

for i in range(m):
    u,v,a,b=map(int,input().split())
    for j in range(a,2500):
        EdgeMatrix[(u-1)*2500+j].append([(v-1)*2500+j-a,b])
        EdgeMatrix[(v-1)*2500+j].append([(u-1)*2500+j-a,b])

for i in range(n):
    c,d=map(int,input().split())
    for j in range(2450):
        EdgeMatrix[i*2500+j].append([min(i*2500+j+c,(i+1)*2500-1),d])

#頂点0からの最短経路
Distance=dijkstra(125000,EdgeMatrix,s)

for i in range(1,n):
    print(min(Distance[i*2500:(i+1)*2500-1]))

Submission status: Runtime Error

Solution code:
import heapq

#dg = 10**7#ノード数より多く取る

n,m, S = map(int,input().split()) #n:頂点数　m:辺の数

edge = [[] for i in range(n)]
#edge[i] : iから出る道の[重み,行先]の配列


Cs=[]
Ds=[]
amax=0
for _ in range(m):
    u, v, a, b = map(int,input().split())
    edge[u-1].append([v-1,a,b])
    edge[v-1].append([u-1,a,b])#有向グラフの場合コメント
    amax=max(a,amax)

for _ in range(n):
    c, d = map(int,input().split())
    Cs.append(c)
    Ds.append(d)

dg=(n-1)*amax

def cut(S): 
    return min(S,dg)

S=cut(S)

def dijkstra(start):

    #dijkstra
    # d : minimum distance from s
    d = [[10**20]*(dg+1) for _ in range(n)]
    d[start][cut(S)] = 0
    edgelist = []

    heapq.heappush(edgelist,[Ds[0], 0, cut(S+Cs[0]])

    for e in edge[start]:
        if S-e[1]>=0:
            heapq.heappush(edgelist,[e[2],e[0],S-e[1]])

    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        t,ce,cs = minedge[0],minedge[1],minedge[2]
        #print(t,ce,cs)
        if  d[ce][cs]== 10**20:
            d[ce][cs] = t
            ns=cut(cs+Cs[ce])
            #print(ce,ns)
            if d[ce][ns]==10**20:
                #d[ce][ns]=t+Ds[ce]
                heapq.heappush(edgelist, [t+Ds[ce],ce,ns])

            for e in edge[ce]:
                if cs>=e[1]:
                    #print(e)
                    ne=e[0]
                    ns=cs-e[1]
                    if d[ne][ns]==10**20:
                        #print(ne)
                        heapq.heappush(edgelist, [t+e[2],ne,ns])
    return d

d=dijkstra(start=0)
for x in d[1:]:
    print(min(x))
#print(d)

Submission status: Runtime Error

Solution code:
import heapq

#dg = 10**7#ノード数より多く取る

n,m, S = map(int,input().split()) #n:頂点数　m:辺の数

edge = [[] for i in range(n)]
#edge[i] : iから出る道の[重み,行先]の配列


Cs=[]
Ds=[]
amax=0
for _ in range(m):
    u, v, a, b = map(int,input().split())
    edge[u-1].append([v-1,a,b])
    edge[v-1].append([u-1,a,b])#有向グラフの場合コメント
    amax=max(a,amax)

for _ in range(n):
    c, d = map(int,input().split())
    Cs.append(c)
    Ds.append(d)

dg=(n-1)*amax

def cut(S): 
    if S>dg:
        return dg
    else: return S

S=cut(S)

def dijkstra(start):

    #dijkstra
    # d : minimum distance from s
    d = [[10**20]*(dg+1) for _ in range(n)]
    d[start][cut(S)] = 0
    edgelist = []

    heapq.heappush(edgelist,(Ds[0], 0, cut(S+Cs[0])))

    for e in edge[start]:
        if S-e[1]>=0:
            heapq.heappush(edgelist,[e[2],e[0],S-e[1]])

    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        t,ce,cs = minedge[0],minedge[1],minedge[2]
        #print(t,ce,cs)
        if  d[ce][cs]== 10**20:
            d[ce][cs] = t
            ns=cut(cs+Cs[ce])
            #print(ce,ns)
            if d[ce][ns]==10**20:
                #d[ce][ns]=t+Ds[ce]
                heapq.heappush(edgelist, [t+Ds[ce],ce,ns])

            for e in edge[ce]:
                if cs>=e[1]:
                    #print(e)
                    ne=e[0]
                    ns=cs-e[1]
                    if d[ne][ns]==10**20:
                        #print(ne)
                        heapq.heappush(edgelist, [t+e[2],ne,ns])
    return d

d=dijkstra(start=0)
for x in d[1:]:
    print(min(x))
#print(d)

Submission status: Runtime Error

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

INF = 10**12
n, m, s = map(int, input().split())
edges = defaultdict(lambda: defaultdict(lambda: [INF, INF]))
cd = []
max_a = 0

for i in range(m):
    u, v, a, b = map(int, input().split())
    max_a = max(max_a, a)
    edges[u-1][v-1] = [a, b]
    edges[v-1][u-1] = [a, b]

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

# 解答ACする
# Dijakstraの状態を(頂点、所持している銀貨の枚数, cost)で持つ
# SIZE = max_a * n + 1
SIZE = 2550
if s > SIZE:
    s = SIZE
nodes = [[INF for _ in range(SIZE)] for _ in range(n)]
nodes[0][s-1] = 0

def dijakstra():
    goals = set({0})
    que = [(0, 0, s)]
    heapify(que)
    while len(que) > 0:
        # print(que[:3])
        cost, num, silver = heappop(que)
        if nodes[num][silver] < cost:
            continue
        # print(cost, num, silver)
        if num not in goals:
            goals.add(num)
        if len(goals) == n:
            break
        c, d = cd[num]
        for v in edges[num].keys():
            a, b = edges[num][v]
            times = -1
            to = silver - a
            while to < SIZE:
                times += 1
                plus = times * c
                to = silver + plus - a
                if to < 0:
                    continue
                if to >= SIZE:
                    break
                if nodes[v][to] > cost + b + d * times:
                    nodes[v][to] = cost + b + d * times
                    heappush(que, (cost + b + d * times, v, to))
dijakstra()
for i in range(1, n):
    print(min(nodes[i]))

Submission status: Runtime Error

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(250,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))
kankin = [tuple(map(int,input().split())) for i in range(n)]

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


def dijktra(g,s):
    n=len(g)
    dist = [[inf]*250 for i in range(n)]
    dist[s][s0]
    hq=[]
    heapq.heappush(hq,(0,s0,s))
    while hq:
      time,money,u = heapq.heappop(hq)
      if dist[u][money] < time: continue
      c,d = kankin[u]
      while money <= 250:
        for v,money1,time1 in g[u]:
          if not money >= money1: continue
          if dist[v][money-money1] > time + time1:
            dist[v][money-money1] = (time + time1)
            heapq.heappush(hq,(time + time1, money-money1,v))
        money += c; time += d

    return #!/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(50,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))
kankin = [tuple(map(int,input().split())) for i in range(n)]

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


def dijktra(g,s):
    n=len(g)
    dist = [[inf]*51 for i in range(n)]
    dist[s][s0]
    hq=[]
    heapq.heappush(hq,(0,s0,s))
    while hq:
      time,money,u = heapq.heappop(hq)
      if dist[u][money] < time: continue
      c,d = kankin[u]
      while money <= 50:
        for v,money1,time1 in g[u]:
          if not money >= money1: continue
          if dist[v][money-money1] > time + time1:
            dist[v][money-money1] = (time + time1)
            heapq.heappush(hq,(time + time1, money-money1,v))
        money += c; time += d

    return dist

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




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

Submission status: Runtime Error

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

#O(ElogV)
import heapq
def dijkstra_heap(s):
  #始点sから各頂点への最短距離
  #d = [float("inf")] * n  
  #used = [True] * n #True:未確定
  d,used={},{}
  for v in vlist:
    d[v]=float("inf")
    used[v]=True
  d[s]=0
  used[s]=False
  
  edgelist = []
  for e in edge[s]:
    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

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))
  
vlist=[]
for i in range(1,N+1):
  for j in range(2501):
    vlist.append((i,j))

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

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)))
    
n=len(vlist)
w=len(edge)
res=dijkstra_heap((1,S))
#print(res)

for i in range(2,N+1):
  min_i=float("inf")
  for j in range(2501):
    min_i=min(min_i,res[(i,j)])
    
  print(min_i)

Submission status: Runtime Error

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 = 0
    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))
        max_m = max(max_m, a)

    max_m *= N-1

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

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

    state = [[float('inf')] * (max_m+1) for _ in range(N+1)]

    while queue:
        time, node, coin = heappop(queue)
        if state[node][coin] < time: continue
        c, d = CD[node]
        if coin + c < max_m and time + d < state[node][coin+c]:
            state[node][coin+c] = time + d
            heappush(queue, (time+d, node, coin+c))
        for n_node, n_time, n_coin in to[node]:
            if coin < n_coin:continue
            if state[n_node][coin-n_coin] < n_time + time:continue
            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()