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:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
INF = float("inf")
from collections import defaultdict
from collections import deque
import heapq


class Graph(object):
    def __init__(self, N):
        self.N = N
        self.E = defaultdict(list)

    def add_edge(self, s, t, w=1):
        self.E[s].append((t, w))
        # self.E[t].append((s, w))


def shortestPath(g: Graph, s: int):
    # 返り値 (dist, prev)
    # dist: 始点からの距離が格納されたリスト
    # prev: 始点から最短経路で移動する場合、各頂点に至る前の頂点のリスト
    dist = defaultdict(lambda: INF)
    dist[s] = 0

    prev = defaultdict(lambda: None)
    Q = []
    heapq.heappush(Q, (dist[s], s))

    while len(Q) > 0:
        _, u = heapq.heappop(Q)
        for v, w in g.E[u]:
            if dist[v] > dist[u] + w:
                dist[v] = dist[u] + w
                prev[v] = u
                heapq.heappush(Q, (dist[v], v))
    return dist, prev


def solve(N: int, M: int, S: int,
          U: "List[int]", V: "List[int]",
          A: "List[int]", B: "List[int]",
          C: "List[int]", D: "List[int]"):

    # (頂点数, 所持している銀貨の枚数)ごとにノードを増やす
    # ノード数は 50*(N-1)*N 未満
    NN = 50*N*N
    g = Graph(NN)
    # U[i]-1, V[i]-1間ではなくて、
    # (U[i]-1, a), (V[i]-1, a-A[i])間に重みB[i]の有向リンクがある
    # (V[i]-1, a), (U[i]-1, a-A[i])間に重みB[i]の有向リンクがある
    for i in range(M):
        for j in range(50*N):
            if j - A[i] < 0:
                continue
            g.add_edge((U[i]-1, j), (V[i]-1, j-A[i]), B[i])
            g.add_edge((V[i]-1, j), (U[i]-1, j-A[i]), B[i])
        # print(U[i]-1, V[i]-1)
    # 都市iで補給する時のパス
    for i in range(N):
        for j in range(50*N):
            if j-C[i] >= 0:
                g.add_edge((i, j-C[i]), (i, j), D[i])

    if S >= (N-1)*50:
        S = (N-1)*50
    dist, prev = shortestPath(g, (0, S))
    # print(dist, prev)

    # nに至るパスで最短時間となるものを選ぶ
    for n in range(1, N):
        tot = INF
        for i in range(50*N):
            if (n, i) in dist:
                tot = min(tot, dist[n, i])
                # print((n, i), dist[n, i], prev[n, i])
        print(tot)
        # print(n, "done")
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    S = int(next(tokens))  # type: int
    U = [int()] * (M)  # type: "List[int]"
    V = [int()] * (M)  # type: "List[int]"
    A = [int()] * (M)  # type: "List[int]"
    B = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        U[i] = int(next(tokens))
        V[i] = int(next(tokens))
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    C = [int()] * (N)  # type: "List[int]"
    D = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        C[i] = int(next(tokens))
        D[i] = int(next(tokens))
    solve(N, M, S, U, V, A, B, C, D)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,M,S = map(int,input().split())
edges = [[] for _ in range(2500*50 + 100)]
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
    INF = float('inf')
    d = [INF]*n
    d[s] = 0
    pq = [(0,s)]
    while len(pq):
        c,v = heapq.heappop(pq)
        if d[v] < c:
            continue
        for v2nvcost, nv in edges[v]:
            if c + v2nvcost < d[nv]:
                d[nv] = c + v2nvcost
                heapq.heappush(pq,(d[nv],nv))
    return d


d=dijkstra(indexer(0,min(2500,S)),2500*50 + 100,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: Accepted

Solution code:
N,M,S = map(int,input().split())
edges = [[] for _ in range(2500*50 + 100)]
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 + 100,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: 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


## Segment Tree ##

## Initializer Template ##
# Range Sum:        sg=SegTree(n)
# Range Minimum:    sg=SegTree(n,inf,min,inf)

class SegTree:

    def __init__(self,n,init_ls=None,init_val=0,function=lambda a,b:a+b,ide=0):
        self.n=n
        self.ide_ele=ide_ele=ide
        self.num=num=2**(n-1).bit_length()
        self.seg=seg=[self.ide_ele]*2*self.num
        self.lazy=lazy=[self.ide_ele]*2*self.num
        self.segfun=segfun=function
        #set_val
        if init_ls==None:
            for i in range(n):
                self.seg[i+self.num-1]=init_val
        else:
            for i in range(n):
                self.seg[i+self.num-1]=init_ls[i]
        #build
        for i in range(self.num-2,-1,-1):
            self.seg[i]=self.segfun(self.seg[2*i+1],self.seg[2*i+2])
    
    def update(self,k,x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfun(self.seg[k*2+1],self.seg[k*2+2])
        
    def evaluate(k,l,r): #遅延評価処理
        if lazy[k]!=0:
            node[k]+=lazy[k]
            if(r-l>1):
                lazy[2*k+1]+=lazy[k]//2
                lazy[2*k+2]+=lazy[k]//2

        lazy[k]=0
        
    def query(self,p,q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfun(res,self.seg[p])
            if q&1 == 1:
                res = self.segfun(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfun(res,self.seg[p])
        else:
            res = self.segfun(self.segfun(res,self.seg[p]),self.seg[q])
        return res
    
    def find_min_index(self,p,q,m):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfun(res,self.seg[p])
            if q&1 == 1:
                res = self.segfun(res,self.seg[q])
                q -= 1
            p >>= 1
            q = (q-1)//2
        if p == q:
            res = self.segfun(res,self.seg[p])
        else:
            res = self.segfun(self.segfun(res,self.seg[p]),self.seg[q])
        return res


    def __str__(self):
        # 生配列を表示
        rt=self.seg[self.num-1:self.num-1+self.n]
        return str(rt)

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

ans=0

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):
    ans=inf
    for j in range(k):
        alt=dist_t[i*k+j]
        if alt<ans:
            ans=alt
    print(ans)

Submission status: Accepted

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)
S = min(S, limit)
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: Accepted

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])
    Flag=True #探索対象がなくなるとFalse
    
    while 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 not NodeList.empty():
            minNode=NodeList.get()
            if used[minNode[1]]==False:
                Flag=True
                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(2502):
#    print(EdgeMatrix[i])
    
#頂点0からの最短経路
Distance=dijkstra(125000,EdgeMatrix,min(s,2499))

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

Submission status: Accepted

Solution code:
[print(min(m[i])[0])for h in[__import__('heapq')]for a,d,r,n,x in[(h.heappush,h.heappop,range,lambda:map(int,input().split()),list.append)]for N,M,S in[n()]for g,q in[([[]for _ in r(N)],[(0,S,0)])]for L in[max(A for _ in r(M)for U,V,A,B in[n()]if not(x(g[U-1],(V-1,A,B))or x(g[V-1],(U-1,A,B))))*(N-1)]for m in[[[[2**64]for _ in r(L+1)]for _ in r(N)]]for _ in[[[x(g[i],(i,-C,D))for i in r(N)for C,D in[n()]],[[[_ for s,v,i in[d(q)]for _ in[[a(q,(s+c,j,t))for t,p,c in g[i]for j in[min(L,v-p)]for y in[m[t][j]]if v>=p and s+c<y[0] and not(y.clear()or x(y,s+c))]]if not(x(l,None)if q else l.clear())]]for l in[[None]]for _ in l]]]for i in r(1,N)]

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:
[print(min(m[i])[0])for h in [__import__('heapq')]for a,d,r,n,x in[(h.heappush,h.heappop,range,lambda:map(int,input().split()),list.append)]for N,M,S in[n()]for g,q in[([[]for _ in r(N)],[(0,S,0)])]for L in[max(A for _ in r(M)for U,V,A,B in[n()]if not(x(g[U-1],(V-1,A,B))or x(g[V-1],(U-1,A,B))))*(N-1)]for m in[[[[2**64]for _ in r(L+1)]for _ in r(N)]]for _ in[[[x(g[i],(i,-C,D))for i in r(N)for C,D in[n()]],[[[_ for s,v,i in[d(q)]for _ in[[a(q,(s+c,j,t))for t,p,c in g[i]for j in[min(L,v-p)]for y in[m[t][j]]if v>=p and s+c<y[0] and not(y.clear()or x(y,s+c))]]if not(x(l,None)if q else l.clear())]]for l in[[None]]for _ in l]]]for i in r(1,N)]

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7
INF = 10 ** 13
import sys
sys.setrecursionlimit(100000000)
dy = (-1,0,1,0)
dx = (0,1,0,-1)
from heapq import heapify,heappop,heappush

def dijkstra(G,s = 0): #sを始点とした最短経を求める
    n = len(G)
    dist = [INF] * n
    dist[s] = 0

    q = [(0,s)]
    heapify(q)

    while q:
        d,v = heappop(q)
        if dist[v] < d:
            continue
        for e,cost in G[v]:
            if dist[e] > dist[v] + cost:
                dist[e] = dist[v] + cost
                heappush(q,(dist[e],e))
    
    return dist

def main():
    n,m,s = map(int,input().split())
    MAXV = 2500*n
    G = [[] for _ in range(MAXV)]
    for _ in range(m):
        u,v,a,b = map(int,input().split())
        u -= 1
        v -= 1
        for i in range(2500 - a):
            G[u*2500 + i + a].append((v*2500 + i,b))
            G[v*2500 + i + a].append((u*2500 + i,b))
    
    for i in range(n):
        c,d = map(int,input().split())
        for j in range(2500 - c):
            G[i*2500 + j].append((i*2500 + j + c,d))
  
    dist = dijkstra(G,min(s,2499))
    for i in range(1,n):
        ans = min(dist[2500*i:2500*(i + 1)])
        print(ans) 

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

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

edges = [[] for _ in range(N)]
for _ in range(M):
    fr, to, cost, dist = map(int, input().split())
    mxCost = max(mxCost, cost)
    fr -= 1
    to -= 1
    edges[fr].append((to, dist, cost))
    edges[to].append((fr, dist, cost))

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

que = [(0, S, 0)]
mxCost *= (N - 1)
minDsit = [[10**18] * (mxCost + 1) for _ in range(N)]
minDsit[0][0] = 0

while que:
    dist, s, now = heappop(que)

    for to, d, c in edges[now]:
        cost = min(mxCost, s - c)
        if cost < 0 or minDsit[to][cost] <= dist + d:
            continue
        minDsit[to][cost] = dist + d
        heappush(que, (dist + d, cost, to))

for dist in minDsit[1:]:
    print(min(dist))

Submission status: Accepted

Solution code:
def main():
    import heapq
    
    def dijkstra(graph,s,cd,c):
        dist = [[float("inf")]*2505 for _ in range(n)]
        q = []
        dist[s][c] = 0
        heapq.heappush(q, (0,s,c))
        
        while q:
            d, p,c = heapq.heappop(q)
            
            if dist[p][c] < d:
                continue
            if c+cd[p][0] < 2500:
                if dist[p][c+cd[p][0]] >  d+cd[p][1]:
                    dist[p][c+cd[p][0]] = d+cd[p][1]
                    heapq.heappush(q, (d+cd[p][1],p,c+cd[p][0]))
            else:
                if dist[p][2500] >  d+cd[p][1]:
                    dist[p][2500] = d+cd[p][1]
                    heapq.heappush(q, (d+cd[p][1],p,2500))
            for nn,nc,nt  in graph[p]:
                if c >= nc and dist[nn][c-nc] >   d+nt:
                    dist[nn][c-nc] =    d+nt
                    heapq.heappush(q,(d+nt,nn,c-nc))
            
                    
        for i in dist[1:]:
            print(min(i))
    n,m,s = map(int,input().split())
    E = [[] for i in range(n)]
    la = []
    for i in range(m):
        u,v,a,b = map(int,input().split())
        u -= 1
        v-= 1
        la.append(a)
        E[u].append((v,a,b))
        E[v].append((u,a,b))

    cd = [list(map(int,input().split())) for i in range(n)]

    dijkstra(E,0,cd,min(s,2500))
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    import heapq
    
    def dijkstra(graph,s,cd,c):
        dist = [[float("inf")]*2505 for _ in range(n)]
        q = []
        dist[s][c] = 0
        heapq.heappush(q, (0,s,c))
        
        while q:
            d, p,c = heapq.heappop(q)
            
            if dist[p][c] < d:
                continue
            
            for nn,nc,nt  in graph[p]:
                if c >= nc and dist[nn][c-nc] >   d+nt:
                    dist[nn][c-nc] =    d+nt
                    heapq.heappush(q,(d+nt,nn,c-nc))
            if c+cd[p][0] < 2500:
                if dist[p][c+cd[p][0]] >  d+cd[p][1]:
                    dist[p][c+cd[p][0]] = d+cd[p][1]
                    heapq.heappush(q, (d+cd[p][1],p,c+cd[p][0]))
            else:
                if dist[p][2500] >  d+cd[p][1]:
                    dist[p][2500] = d+cd[p][1]
                    heapq.heappush(q, (d+cd[p][1],p,2500))
                    
        for i in dist[1:]:
            print(min(i))
    n,m,s = map(int,input().split())
    E = [[] for i in range(n)]
    la = []
    for i in range(m):
        u,v,a,b = map(int,input().split())
        u -= 1
        v-= 1
        la.append(a)
        E[u].append((v,a,b))
        E[v].append((u,a,b))

    cd = [list(map(int,input().split())) for i in range(n)]

    dijkstra(E,0,cd,min(s,2500))
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
z=lambda i,c:i+c*50;n,m,s=map(int,input().split());e=[[]for _ in range(4**9)];from heapq import*;t=z(0,min(2500,s));d=[9**20]*(4**9);d[t]=0;h=[[0,t]];q=[9**20]*(n-1)
for _ in range(m):
  u,v,a,b=map(int,input().split())
  for i in range(a,2501):e[z(u-1,i)].append((z(v-1,i-a),b));e[z(v-1,i)].append((z(u-1,i-a),b))
for i in range(n):
  c,r=map(int,input().split())
  for j in range(c,2501):e[z(i,j-c)].append((z(i,j),r))
while h:
  c,v=heappop(h)
  if d[v]<c:continue
  for u,t in e[v]:
    if c+t<d[u]:d[u]=c+t;heappush(h,[c+t,u])
for i in range(n-1):
  for j in range(2501):q[i]=min(q[i],d[z(i+1,j)])
print(*q)

Submission status: Accepted

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)