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 collections

n,m,s=map(int,input().split())
g=[[] for _ in range(n+1)]
dic={}
for _ in range(m):
  u,v,a,b=map(int,input().split())
  g[u].append(v)
  g[v].append(u)
  dic[(u,v)]=(a,b)
  dic[(v,u)]=(a,b)
arr=[[0,0]]+[list(map(int,input().split())) for _ in range(n)]
cost=[[10**18]*2501 for _ in range(n+1)]
for i in range(min(2500,s)+1):
  cost[1][i]=0
q=collections.deque()
q.append(1)
while len(q)!=0:
  v=q.popleft()
  c,d=arr[v]
  for i in range(c,2501):
    cost[v][i]=min(cost[v][i],cost[v][i-c]+d)
  for u in g[v]:
    a,b=dic[(v,u)]
    flag=False
    for i in range(a,2501):
      if cost[u][i-a]>cost[v][i]+b:
        cost[u][i-a]=cost[v][i]+b
        flag=True
    if flag==True:
      q.append(u)

for i in range(2,n+1):
  print(min(cost[i]))

Submission status: Accepted

Solution code:
import sys
import heapq
def dijkstra(s,es):
    INF=sys.maxsize
    cs=[INF]*len(es)
    cs[s],hq=0,[]
    heapq.heapify(hq)
    heapq.heappush(hq,(cs[s],s))
    while hq:
        d,v=heapq.heappop(hq)
        if cs[v]<d:continue
        for t,b in es[v]:
            if cs[t]>cs[v]+b:
                cs[t]=cs[v]+b
                heapq.heappush(hq,(cs[t],t))
    return cs
def nwc(n,c):
    MAX_COINS=2500
    return (MAX_COINS+1)*n+c
def main():
    MAX_COINS=2500
    N,M,S=tuple(map(int,sys.stdin.readline().split()))
    S=S if S<MAX_COINS else MAX_COINS
    es=[[] for _ in range(N*(MAX_COINS+1))]
    for _ in range(M):
        u,v,a,b=tuple(map(int,sys.stdin.readline().split()))
        u,v=u-1,v-1
        for c in range(a,MAX_COINS+1):
            es[nwc(u,c)].append((nwc(v,c-a),b))
            es[nwc(v,c)].append((nwc(u,c-a),b))
    for n in range(N):
        c,d=tuple(map(int,sys.stdin.readline().split()))
        c=c if c<MAX_COINS else MAX_COINS
        for i in range(0,MAX_COINS-c+1):es[nwc(n,i)].append((nwc(n,i+c),d))
    cs=dijkstra(nwc(0,S),es)
    for n in range(1,N):print(min(cs[n*(MAX_COINS+1):(n+1)*(MAX_COINS+1)]))
if __name__=='__main__':main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import heapq
import sys
from collections import defaultdict

input = sys.stdin.buffer.readline
INF = 2**62-1


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


def read_str_n():
    return list(map(str, input().split()))


def Dijkstra(g, s):
    d = defaultdict(lambda: INF)
    d[s] = 0
    q = []
    heapq.heappush(q, (d[s], s))

    prev = {}
    done = set()
    while q:
        c, u = heapq.heappop(q)
        if u in done:
            continue
        done.add(u)
        for v in g[u]:
            alt = g[u][v] + d[u]
            if d[v] > alt:
                d[v] = alt
                prev[v] = u
                heapq.heappush(q, (d[v], v))
    return d

def slv(N, M, S, UVAB, CD):
    g = defaultdict(dict)
    V = {}
    for u, v, a, b in UVAB:
        g[u][v] = (a, b)
        g[v][u] = (a, b)

    for i, (c, d) in enumerate(CD, 1):
        V[i] = (c, d)

    MA = (N-1)*max(a for u, v, a, b in UVAB)
    S = min(S, MA)
    d = [[INF] * (MA+1) for _ in range(N+1)]
    d[1][S] = 0
    q = []

    def p(q, u, m, alt):
        if m >= 0 and d[u][m] > alt:
            d[u][m] = alt
            heapq.heappush(q, (d[u][m], (u, m)))

    heapq.heappush(q, (d[1][S], (1, S)))
    while q:
        c, (u, s) = heapq.heappop(q)
        if d[u][s] < c:
            continue
        c, dd = V[u]
        p(q, u, min(MA, s+c), d[u][s] + dd)

        for v in g[u]:
            a, b = g[u][v]
            p(q, v, s-a, b + d[u][s])

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


def main():
    N, M, S = read_int_n()
    UVAB = [read_int_n() for _ in range(M)]
    CD = [read_int_n() for _ in range(N)]
    (slv(N, M, S, UVAB, CD))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import heapq
import sys
from collections import defaultdict

input = sys.stdin.buffer.readline
INF = 2**62-1


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


def read_str_n():
    return list(map(str, input().split()))


def Dijkstra(g, s):
    d = defaultdict(lambda: INF)
    d[s] = 0
    q = []
    heapq.heappush(q, (d[s], s))

    prev = {}
    done = set()
    while q:
        c, u = heapq.heappop(q)
        if u in done:
            continue
        done.add(u)
        for v in g[u]:
            alt = g[u][v] + d[u]
            if d[v] > alt:
                d[v] = alt
                prev[v] = u
                heapq.heappush(q, (d[v], v))
    return d

def slv(N, M, S, UVAB, CD):
    g = defaultdict(dict)
    V = {}
    for u, v, a, b in UVAB:
        g[u][v] = (a, b)
        g[v][u] = (a, b)

    for i, (c, d) in enumerate(CD, 1):
        V[i] = (c, d)

    MA = (N-1)*max(a for u, v, a, b in UVAB)
    S = min(S, MA)
    d = [[INF] * (MA+1) for _ in range(N+1)]
    d[1][S] = 0
    q = []

    def p(q, u, m, alt):
        if m >= 0 and d[u][m] > alt:
            d[u][m] = alt
            heapq.heappush(q, (d[u][m], (u, m)))

    heapq.heappush(q, (d[1][S], (1, S)))
    while q:
        c, (u, s) = heapq.heappop(q)
        if d[u][s] < c:
            continue
        c, dd = V[u]
        if s != MA:
            p(q, u, min(MA, s+c), d[u][s] + dd)

        for v in g[u]:
            a, b = g[u][v]
            p(q, v, s-a, b + d[u][s])

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


def main():
    N, M, S = read_int_n()
    UVAB = [read_int_n() for _ in range(M)]
    CD = [read_int_n() for _ in range(N)]
    (slv(N, M, S, UVAB, CD))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import heapq
import sys
from collections import defaultdict

input = sys.stdin.buffer.readline
INF = 2**62-1


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


def read_str_n():
    return list(map(str, input().split()))


def Dijkstra(g, s):
    d = defaultdict(lambda: INF)
    d[s] = 0
    q = []
    heapq.heappush(q, (d[s], s))

    prev = {}
    done = set()
    while q:
        c, u = heapq.heappop(q)
        if u in done:
            continue
        done.add(u)
        for v in g[u]:
            alt = g[u][v] + d[u]
            if d[v] > alt:
                d[v] = alt
                prev[v] = u
                heapq.heappush(q, (d[v], v))
    return d

def slv(N, M, S, UVAB, CD):
    g = defaultdict(dict)
    V = {}
    for u, v, a, b in UVAB:
        g[u][v] = (a, b)
        g[v][u] = (a, b)

    for i, (c, d) in enumerate(CD, 1):
        V[i] = (c, d)

    MA = (N-1)*max(a for u, v, a, b in UVAB)
    S = min(S, MA)
    d = [[INF] * (MA+1) for _ in range(N+1)]
    d[1][S] = 0
    q = []

    def p(q, u, m, alt):
        if m >= 0 and d[u][m] > alt:
            d[u][m] = alt
            heapq.heappush(q, (d[u][m], (u, m)))

    heapq.heappush(q, (d[1][S], (1, S)))
    while q:
        c, (u, s) = heapq.heappop(q)
        if d[u][s] < c:
            continue
        c, dd = V[u]
        if s != MA:
            m = min(MA, s+c)
            alt = d[u][s] + dd
            p(q, u, m, alt)

        for v in g[u]:
            a, b = g[u][v]
            alt = b + d[u][s]
            m = s - a
            p(q, v, m, alt)

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


def main():
    N, M, S = read_int_n()
    UVAB = [read_int_n() for _ in range(M)]
    CD = [read_int_n() for _ in range(N)]
    (slv(N, M, S, UVAB, CD))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import heapq
import sys
from collections import defaultdict

input = sys.stdin.buffer.readline
INF = 2**62-1


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


def read_str_n():
    return list(map(str, input().split()))


def Dijkstra(g, s):
    d = defaultdict(lambda: INF)
    d[s] = 0
    q = []
    heapq.heappush(q, (d[s], s))

    prev = {}
    done = set()
    while q:
        c, u = heapq.heappop(q)
        if u in done:
            continue
        done.add(u)
        for v in g[u]:
            alt = g[u][v] + d[u]
            if d[v] > alt:
                d[v] = alt
                prev[v] = u
                heapq.heappush(q, (d[v], v))
    return d

def slv(N, M, S, UVAB, CD):
    g = defaultdict(dict)
    V = {}
    for u, v, a, b in UVAB:
        g[u][v] = (a, b)
        g[v][u] = (a, b)

    for i, (c, d) in enumerate(CD, 1):
        V[i] = (c, d)

    MA = (N-1)*max(a for u, v, a, b in UVAB)
    S = min(S, MA)
    d = [[INF] * (MA+1) for _ in range(N+1)]
    d[1][S] = 0
    q = []
    heapq.heappush(q, (d[1][S], (1, S)))
    while q:
        c, (u, s) = heapq.heappop(q)
        if d[u][s] < c:
            continue
        c, dd = V[u]
        if s != MA:
            m = min(MA, s+c)
            alt = d[u][s] + dd
            if d[u][m] > alt:
                d[u][m] = alt
                heapq.heappush(q, (d[u][m], (u, m)))
        for v in g[u]:
            a, b = g[u][v]
            alt = b + d[u][s]
            m = s - a
            if m >= 0 and d[v][m] > alt:
                d[v][m] = alt
                heapq.heappush(q, (d[v][m], (v, m)))

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


def main():
    N, M, S = read_int_n()
    UVAB = [read_int_n() for _ in range(M)]
    CD = [read_int_n() for _ in range(N)]
    (slv(N, M, S, UVAB, CD))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

from heapq import heappush, heappop
def resolve():
    INF = float('inf')
    maxMoney = 2502

    def Dijkstra(g):
        ans = {}
        # ある頂点にいて、ある銀貨の枚数を持っているときのこれまでにかかった最短時間
        dp = [[INF] * (maxMoney + 1) for _ in range(N)]
        # (time, node, silver)
        hq = []
        heappush(hq, (0, 0, min(S, maxMoney)))
        while hq:
            t, v, s = heappop(hq)
            if t > dp[v][s]:
                continue
            if v not in ans:
                ans[v] = t
                if len(ans) == N:
                    break

            # buy
            if s < maxMoney:
                c, d = CD[v]
                new_s = min(s + c, maxMoney)
                new_t = t + d
                if new_t < dp[v][new_s]:
                    dp[v][new_s] = new_t
                    heappush(hq, (new_t, v, new_s))

            # move
            for nv, cost, time in G[v]:
                # 払えない
                if s < cost:
                    continue
                # 払って移動した場合、最短時間なら更新
                new_s = s - cost
                new_t = t + time
                if new_t < dp[nv][new_s]:
                    dp[nv][new_s] = new_t
                    heappush(hq, (new_t, nv, new_s))
        return ans

    N, M, S = map(int, input().split())
    G = [[] for _ in range(N)]
    for _ in range(M):
        u, v, coin, tm = map(int, input().split())
        u, v = u - 1, v - 1
        G[u].append((v, coin, tm))
        G[v].append((u, coin, tm))
    CD = [list(map(int, input().split())) for _ in range(N)]

    ans = Dijkstra(G)
    for i in range(1, N):
        print(ans[i])


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline

def main():

    n, m, s = map(int, input().split())
    g = [[] for i in range(n*2501)]
    for i in range(m):
        u, v, a, b = map(int, input().split())
        u, v = u-1, v-1
        for j in range(2501):
            k = j-a
            if 0 <= k <= 2500:
                g[u+n*j].append((b, v+n*k))
                g[v+n*j].append((b, u+n*k))

    for i in range(n):
        c, d = map(int, input().split())
        for j in range(2501):
            k = j+c
            if 0 <= k <= 2500:
                g[i+n*j].append((d, i+n*k))

    import heapq
    INF = 10**18
    def dijkstra_heap(s, edge, n):
        d = [INF] * n
        used = [True] * n #True: not used
        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

    s_ = 0+min(s, 2500)*n
    d = dijkstra_heap(s_, g, n*2501)
    #print(d)
    for i in range(1, n):
        min_ = INF
        for j in range(2501):
            k = i+n*j
            min_ = min(min_, d[k])
        print(min_)

if __name__ == '__main__':
    main()

Submission status: Accepted

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


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

d = defaultdict(list)
e = defaultdict(int)

for _ in range(M):
    U, V, A, B = map(int, input().split())
    d[U].append((A, B, V))
    d[V].append((A, B, U))

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

dist = defaultdict(lambda :10**30)
ans = defaultdict(lambda :10**30)

source = (1, S)
dist[source] = 0
q = [(0, source)]

while q:
    cost, (s, nokori) = heappop(q)
    ns = (s, nokori)

    u, v = e[s]
    if dist[ns] < cost:
        continue

    if nokori > 2500:
        nokori = 2500
    else:
        n_nokori = nokori + u
        n_cost = v
        if n_nokori > 2500:
            n_nokori = 2500
        nt = (s, n_nokori)
        
        if dist[nt] > dist[ns]+n_cost:
            dist[nt] = dist[ns]+n_cost
            heappush(q, (dist[nt], nt))
    
    for a, b, t in d[s]:
        n_nokori = nokori - a
        n_cost = b
        
        nt = (t, n_nokori)

        if n_nokori < 0:
            continue
        if dist[nt] > dist[ns]+n_cost:
            dist[nt] = dist[ns]+n_cost
            heappush(q, (dist[nt], nt))

for (s, _), v in dist.items():
    ans[s] = min(ans[s], v)

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

Submission status: Accepted

Solution code:
def main():
    import os
    import sys
    from io import BytesIO, IOBase
    
    BUFSIZE = 8192
    
    
    class FastIO(IOBase):
        newlines = 0
    
        def __init__(self, file):
            self._fd = file.fileno()
            self.buffer = BytesIO()
            self.writable = "x" in file.mode or "r" not in file.mode
            self.write = self.buffer.write if self.writable else None
    
        def read(self):
            while True:
                b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
                if not b:
                    break
                ptr = self.buffer.tell()
                self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
            self.newlines = 0
            return self.buffer.read()
    
        def readline(self):
            while self.newlines == 0:
                b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
                self.newlines = b.count(b"\n") + (not b)
                ptr = self.buffer.tell()
                self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
            self.newlines -= 1
            return self.buffer.readline()
    
        def flush(self):
            if self.writable:
                os.write(self._fd, self.buffer.getvalue())
                self.buffer.truncate(0), self.buffer.seek(0)
    
    
    class IOWrapper(IOBase):
        def __init__(self, file):
            self.buffer = FastIO(file)
            self.flush = self.buffer.flush
            self.writable = self.buffer.writable
            self.write = lambda s: self.buffer.write(s.encode("ascii"))
            self.read = lambda: self.buffer.read().decode("ascii")
            self.readline = lambda: self.buffer.readline().decode("ascii")
    
    
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
    input = lambda: sys.stdin.readline().rstrip("\r\n")
    mod = 10**9 + 7


    n, m, s = map(int, input().split())
    s = min(s, 2500)
    from collections import defaultdict
    # O(ElogV)
    import heapq
    def dijkstra(s, x):
        # 始点sから各頂点への最短距離
        d = defaultdict(lambda: float("inf"))
        d[(s, x)] = 0
        # 各頂点が訪問済みかどうか
        used = defaultdict(lambda: False)
        used[(s, x)] = True
        # 仮の距離を記録するヒープ
        que = []
        for e in edge[(s, x)]:
            heapq.heappush(que, e)
        while que:
            minedge = heapq.heappop(que)
            if used[minedge[1]]:
                continue
            v = minedge[1]
            d[v] = minedge[0]
            used[v] = True
            for e in edge[v]:
                if not used[e[1]]:
                    heapq.heappush(que, (e[0] + d[v], e[1]))
        return d

    max_money = 2500
    edge = defaultdict(list)
    for _ in range(m):
        u, v, a, b = map(int, input().split())
        u -= 1
        v -= 1
        for i in range(a, max_money + 1):
            edge[(u, i)].append((b, (v, i - a)))
            edge[(v, i)].append((b, (u, i - a)))
    for j in range(n):
        c, d = map(int, input().split())
        for i in range(max_money):
            if i + c <= max_money:
                edge[(j, i)].append((d, (j, i + c)))

    ans = [10**18]*n

    d = dijkstra(0, s)
    for i in d:
        x, y = i
        cost = d[i]
        ans[x] = min(ans[x], cost)
    for i in ans[1:]:
        print(i)
main()

Submission status: Accepted

Solution code:
def main(): 
    import sys
    input = lambda: sys.stdin.readline().rstrip()

    n, m, s = map(int, input().split())
    s = min(s, 2500)
    from collections import defaultdict
    # O(ElogV)
    import heapq
    def dijkstra(s, x):
        # 始点sから各頂点への最短距離
        d = defaultdict(lambda: float("inf"))
        d[(s, x)] = 0
        # 各頂点が訪問済みかどうか
        used = defaultdict(lambda: False)
        used[(s, x)] = True
        # 仮の距離を記録するヒープ
        que = []
        for e in edge[(s, x)]:
            heapq.heappush(que, e)
        while que:
            minedge = heapq.heappop(que)
            if used[minedge[1]]:
                continue
            v = minedge[1]
            d[v] = minedge[0]
            used[v] = True
            for e in edge[v]:
                if not used[e[1]]:
                    heapq.heappush(que, (e[0] + d[v], e[1]))
        return d

    max_money = 2500
    edge = defaultdict(list)
    for _ in range(m):
        u, v, a, b = map(int, input().split())
        u -= 1
        v -= 1
        for i in range(a, max_money + 1):
            edge[(u, i)].append((b, (v, i - a)))
            edge[(v, i)].append((b, (u, i - a)))
    for j in range(n):
        c, d = map(int, input().split())
        for i in range(max_money):
            if i + c <= max_money:
                edge[(j, i)].append((d, (j, i + c)))

    ans = [10**18]*n

    d = dijkstra(0, s)
    for i in d:
        x, y = i
        cost = d[i]
        ans[x] = min(ans[x], cost)
    for i in ans[1:]:
        print(i)
main()

Submission status: Accepted

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

n, m, s = map(int, input().split())
s = min(s, 2500)
from collections import defaultdict
# O(ElogV)
import heapq
def dijkstra(s, x):
    # 始点sから各頂点への最短距離
    d = defaultdict(lambda: float("inf"))
    d[(s, x)] = 0
    # 各頂点が訪問済みかどうか
    used = defaultdict(lambda: False)
    used[(s, x)] = True
    # 仮の距離を記録するヒープ
    que = []
    for e in edge[(s, x)]:
        heapq.heappush(que, e)
    while que:
        minedge = heapq.heappop(que)
        if used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = True
        for e in edge[v]:
            if not used[e[1]]:
                heapq.heappush(que, (e[0] + d[v], e[1]))
    return d

max_money = 2500
edge = defaultdict(list)
for _ in range(m):
    u, v, a, b = map(int, input().split())
    u -= 1
    v -= 1
    for i in range(a, max_money + 1):
        edge[(u, i)].append((b, (v, i - a)))
        edge[(v, i)].append((b, (u, i - a)))
for j in range(n):
    c, d = map(int, input().split())
    for i in range(max_money):
        if i + c <= max_money:
            edge[(j, i)].append((d, (j, i + c)))

ans = [10**18]*n

d = dijkstra(0, s)
for i in d:
    x, y = i
    cost = d[i]
    ans[x] = min(ans[x], cost)
for i in ans[1:]:
    print(i)

Submission status: Accepted

Solution code:
# ダイクストラ
def main():
    import sys
    sys.setrecursionlimit(10**9)
    input = sys.stdin.readline
    from heapq import heappush, heappop

    N, M, S = map(int, input().split())
    S = min(S, 2500)
    graph = [[] for _ in range(N)]

    for u, v, a, b in (map(int, input().split()) for _ in range(M)):
        graph[u-1].append((v-1, a, b))
        graph[v-1].append((u-1, a, b))

    for i, (c, d) in enumerate(map(int, input().split()) for _ in range(N)):
        graph[i].append((i, -c, d))

    hq = [(0, 0, S)]
    INF = 10**18
    # dp[v][silver]
    # 都市vにsilverを使って到達したときの時間の最小値
    dp = [[INF]*2501 for _ in range(N)]
    dp[0][S] = 0

    while hq:
        time, v, silver = heappop(hq)
        if dp[v][silver] < time:
            continue

        for dest, a, b in graph[v]:
            next_s = silver-a if silver-a < 2500 else 2500
            if next_s < 0 or dp[dest][next_s] <= time+b:
                continue
            for i in range(next_s, -1, -1):
                if dp[dest][i] > time+b:
                    dp[dest][i] = time+b
                else:
                    break
            heappush(hq, (time+b, dest, next_s))

    print(*(min(dp[i]) for i in range(1, N)), sep='\n')

main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
import heapq

def main():
    N,M,S = map(int,input().split())
    edge = [[] for _ in range(N)]
    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))
    
    change = [tuple(map(int,input().split())) for _ in range(N)]
    MAX_COST = 50*50
    S = min(S, MAX_COST)
    
    q = [(0,(0,S))]
    ans = [-1]*N
    visited = set()
    heapq.heapify(q)
    
    while q:
        time, data = heapq.heappop(q)
        now, money = data
        if ans[now] == -1:
            ans[now] = time
            if -1 not in ans:
                break
        if data in visited:
            continue
        visited.add(data)
        for fol, a, b in edge[now]:
            if money >= a:
                fol_data = (fol, money-a)
                if fol_data in visited:
                    continue
                heapq.heappush(q, (time+b, fol_data))
        c, d = change[now]
        if money+c > MAX_COST:
            continue
        heapq.heappush(q, (time+d, (now, money+c)))
    
    print(*ans[1:], sep="\n")

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import heapq

n,m,s=map(int,input().split())
limit=2500
s=min(s,limit)
path=[[] for _ in range(n+1)]
coin=[(0,0)]
time=[[float("inf") for _ in range(limit+1)] for _ in range(n+1)]
queue=[]

for i in range(m):
    u,v,a,b=map(int,input().split())
    path[u].append((v,a,b))
    path[v].append((u,a,b))

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

time[1][s]=0
heapq.heappush(queue,(0,1,s))

while len(queue)!=0:
    t,v,c=heapq.heappop(queue)
    for nv,na,nb in path[v]:
        if na>c:
            continue
        elif time[nv][c-na]<=t+nb:
            continue
        else:
            time[nv][c-na]=t+nb
            heapq.heappush(queue,(t+nb,nv,c-na))

    nc=min(c+coin[v][0],limit)
    nt=t+coin[v][1]
    if time[v][nc]<=nt:
        continue
    else:
        time[v][nc]=nt
        heapq.heappush(queue,(nt,v,nc))
    
for i in range(2,n+1):
    print(min(time[i]))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
import heapq
INF = 10**18

MAX_SILVER = 3000 

class Dijkstra:
    def __init__(self, adj):
        self.adj = adj
        self.dist = [INF] * len(adj)
        self.q = []

    def calc(self, start):
        self.dist[start] = 0
        heapq.heappush(self.q, (0, start))
        while len(self.q) != 0:
            prov_cost, src = heapq.heappop(self.q)
            if self.dist[src] < prov_cost:
                continue
            for dest, cost in self.adj[src]:
                if self.dist[dest] > self.dist[src] + cost:
                    self.dist[dest] = self.dist[src] + cost
                    heapq.heappush(self.q, (self.dist[dest], dest))
        return self.dist

n, m, s = map(int, input().split())
edge = [[] for _ in range(n * MAX_SILVER)]
for _ in range(m):
    u, v, a, b = map(int, input().split())
    u -= 1; v -= 1
    for i in range(a, MAX_SILVER):
        edge[u*MAX_SILVER + i].append((v*MAX_SILVER + i-a, b))
        edge[v*MAX_SILVER + i].append((u*MAX_SILVER + i-a, b))

for v in range(n):
    c, d = map(int, input().split())
    for i in range(MAX_SILVER - 100):
        edge[v*MAX_SILVER + i].append((v*MAX_SILVER + i + c, d))

DIJK = Dijkstra(edge)
if s > 2500:
    s = 2500
dist = DIJK.calc(s)

for v in range(1, n): 
    ret = INF
    for val in range(MAX_SILVER):
        if dist[v*MAX_SILVER + val] < ret:
            ret = dist[v*MAX_SILVER + val]
    print(ret)

Submission status: Accepted

Solution code:
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n,m,s = map(int,ipt().split())
    mac = 2500
    way = [[] for i in range(n+1)] #place,money,time
    for _ in range(m):
        u,v,a,b = map(int,ipt().split())
        way[u].append((v,a,b))
        way[v].append((u,a,b))
    for i in range(1,n+1):
        c,d = map(int,ipt().split())
        way[i].append((i,-c,d))
    ct = [[10**18]*2501 for i in range(n+1)]
    ct[1][min(s,mac)] = 0 #place,money//mintime
    hq = [(0,1,min(s,mac))] #time,place,money
    while hq:
        ti,pl,mo = hpq.heappop(hq)
        for dp,dm,dt in way[pl]:
            if mo >= dm and ct[dp][min(mo-dm,mac)] > ti+dt:
                 ct[dp][min(mo-dm,mac)] = ti+dt
                 hpq.heappush(hq,(ti+dt,dp,min(mo-dm,mac)))
    ans = [min(i) for i in ct[2::]]
    for i in ans:
        print(i)
    return

if __name__ == '__main__':
    main()