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: Time Limit Exceeded

Solution code:
from heapq import heappop, heappush


def main():
    N, M, S = map(int, input().split())
    adj = [{} for _ in range(N)]
    amax = 0
    for _ in range(M):
        u, v, a, b = map(int, input().split())
        adj[u-1][v-1] = (a, b)
        adj[v-1][u-1] = (a, b)
        amax = max(amax, a)
    C = [0] * N
    D = [0] * N
    for i in range(N):
        C[i], D[i] = map(int, input().split())
    MAX = amax * N
    dp = [[float("inf")] * (MAX+1) for _ in range(N)]
    q = [(0, min(S, MAX), 0)]
    ans = [None] * N
    remain = N
    while len(q) and remain:
        time, coin, cur = heappop(q)
        if dp[cur][coin] <= time:
            continue
        if ans[cur] is None:
            ans[cur] = time
            remain -= 1
        dp[cur][coin] = time
        if coin < MAX:
            heappush(q, (time + D[cur], min(coin + C[cur], MAX), cur))
        for nxt in adj[cur]:
            dcost, dtime = adj[cur][nxt]
            if dcost <= coin:
                heappush(q, (time + dtime, coin - dcost, nxt))
    for i in range(1, N):
        print(ans[i])


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappop, heappush


def main():
    N, M, S = map(int, input().split())
    adj = [{} for _ in range(N)]
    amax = 0
    for _ in range(M):
        u, v, a, b = map(int, input().split())
        adj[u-1][v-1] = (a, b)
        adj[v-1][u-1] = (a, b)
        amax = max(amax, a)
    C = [0] * N
    D = [0] * N
    for i in range(N):
        C[i], D[i] = map(int, input().split())
    MAX = amax * N
    dp = [[float("inf")] * (MAX+1) for _ in range(N)]
    q = [(0, min(S, MAX), 0)]
    ans = [None] * N
    while len(q) and None in ans:
        time, coin, cur = heappop(q)
        if dp[cur][coin] <= time:
            continue
        if ans[cur] is None:
            ans[cur] = time
        dp[cur][coin] = time
        if coin < MAX:
            heappush(q, (time + D[cur], min(coin + C[cur], MAX), cur))
        for nxt in adj[cur]:
            dcost, dtime = adj[cur][nxt]
            if dcost <= coin:
                heappush(q, (time + dtime, coin - dcost, nxt))
    for i in range(1, N):
        print(ans[i])


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, M, S = mapint()
query = [[(-1, -1)]*N for _ in range(N)]
for _ in range(M):
    u, v, a, b = mapint()
    query[u-1][v-1] = (a, b)
    query[v-1][u-1] = (a, b)
exchange = [list(mapint()) for _ in range(N)]

inf = 10**18
dp = [[inf]*(N*50) for _ in range(N)]
dp[0][0] = 0

import heapq
queue = [(0, 0, S)]
checked = [0]*N
cnt = 0

while queue:
    t, now, coin = heapq.heappop(queue)
    if cnt==N:
        break
    if not checked[now]:
        checked[now] = 1
        cnt += 1
    rate, time = exchange[now]
    if coin<N*50:
        i = 0
        while coin+rate*i<N*50:
            if t+i*time<dp[now][coin+rate*i]:
                dp[now][coin+rate*i] = t+i*time
                for nx in range(N):
                    a, b = query[now][nx]
                    if a!=-1 and coin+rate*i>=a and dp[nx][coin+rate*i-a]>t+i*time+b:
                        heapq.heappush(queue, (t+i*time+b, nx, coin+rate*i-a))
            i += 1
    else:
        coin = N*50-1
        if t<dp[now][coin]:
            dp[now][coin] = t
            for nx in range(N):
                a, b = query[now][nx]
                if a!=-1 and coin>=a and dp[nx][coin-a]>t+b:
                    heapq.heappush(queue, (t+b, nx, coin-a))  

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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]
        for v in g[u]:
            a, b = g[u][v]
            for i in range(-(-(MA-s+a)//c)+1):
                m = s - a + i*c
                if m < 0:
                    continue
                m = min(m, MA)
                alt = i*dd + b + d[u][s]
                if 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: Time Limit Exceeded

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 = 50*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)))
    # print(q)
    while q:
        c, (u, s) = heapq.heappop(q)
        if d[u][s] < c:
            continue
        c, dd = V[u]
        for v in g[u]:
            a, b = g[u][v]
            for i in range(1000000):
                m = s - a + i*c
                if m < 0:
                    continue
                m = min(m, MA)
                alt = i*dd + b + d[u][s]

                if d[v][m] > alt:
                    d[v][m] = alt
                    heapq.heappush(q, (d[v][m], (v, m)))
                if m == MA:
                    break

    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: Time Limit Exceeded

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 = {}
    MA = 0
    for u, v, a, b in UVAB:
        g[u][v] = (a, b)
        g[v][u] = (a, b)
        MA = max(MA, a)
    MA *= (N-1)

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

    d = defaultdict(lambda: INF)
    def f(u, m, s):
        q = []
        c, d = V[u]
        for i in range(1, 100000):
            nc = s+i*c
            if nc > MA:
                q.append((m+i*d, (u, MA)))
                break
            else:
                q.append((m+i*d, (u, nc)))
        return q

    s = (1, min(S, MA))
    d = defaultdict(lambda: INF)
    d[s] = 0
    q = []
    heapq.heappush(q, (d[s], s))

    while q:
        c, u = heapq.heappop(q)
        if d[u] < c:
            continue
        uu, cc = u
        c, dd = V[uu]
        for vv in g[uu]:
            a, b = g[uu][vv]
            for i in range(1000000):
                m = cc + i*c - a
                if m < 0:
                    continue
                m = min(m, MA)
                v = (vv, m)
                alt = i*dd + b + d[u]

                if d[v] > alt:
                    d[v] = alt
                    heapq.heappush(q, (d[v], v))
                if m == MA:
                    break

    ans = [INF] * (N+1)
    for k, v in d.items():
        u = k[0]
        ans[u] = min(ans[u], v)

    for i in range(2, N+1):
        print(ans[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: Time Limit Exceeded

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 = {}
    MA = 0
    for u, v, a, b in UVAB:
        g[u][v] = (a, b)
        g[v][u] = (a, b)
        MA += a

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

    d = defaultdict(lambda: INF)
    def f(u, m, s):
        q = []
        c, d = V[u]
        for i in range(1, 100000):
            nc = s+i*c
            if nc > MA:
                q.append((m+i*d, (u, MA)))
                break
            else:
                q.append((m+i*d, (u, nc)))
        return q

    s = (1, min(S, MA))
    d = defaultdict(lambda: INF)
    d[s] = 0
    q = []
    heapq.heappush(q, (d[s], s))

    while q:
        c, u = heapq.heappop(q)
        if d[u] < c:
            continue
        uu, cc = u
        c, dd = V[uu]
        for vv in g[uu]:
            a, b = g[uu][vv]
            for i in range(1000000):
                m = cc + i*c - a
                if m < 0:
                    continue
                m = min(m, MA)
                v = (vv, m)
                alt = i*dd + b + d[u]

                if d[v] > alt:
                    d[v] = alt
                    heapq.heappush(q, (d[v], v))
                if m == MA:
                    break

    ans = [INF] * (N+1)
    for k, v in d.items():
        u = k[0]
        ans[u] = min(ans[u], v)

    for i in range(2, N+1):
        print(ans[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: Time Limit Exceeded

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 = {}
    MA = 0
    for u, v, a, b in UVAB:
        g[u][v] = (a, b)
        g[v][u] = (a, b)
        MA += a

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

    d = defaultdict(lambda: INF)
    def f(u, m, s):
        q = []
        c, d = V[u]
        for i in range(1, 100000):
            nc = s+i*c
            if nc > MA:
                q.append((m+i*d, (u, MA)))
                break
            else:
                q.append((m+i*d, (u, nc)))
        return q

    s = (1, min(S, MA))
    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)
        if d[u] < c:
            continue
        uu, cc = u
        c, dd = V[uu]
        for vv in g[uu]:
            a, b = g[uu][vv]
            for i in range(1000000):
                m = cc + i*c - a
                if m < 0:
                    continue
                m = min(m, MA)
                v = (vv, m)
                alt = i*dd + b + d[u]

                if d[v] > alt:
                    d[v] = alt
                    prev[v] = u
                    heapq.heappush(q, (d[v], v))
                if m == MA:
                    break

    ans = [INF] * (N+1)
    for k, v in d.items():
        u = k[0]
        ans[u] = min(ans[u], v)

    for i in range(2, N+1):
        print(ans[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: Time Limit Exceeded

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 slv(N, M, S, UVAB, CD):
    g = defaultdict(dict)
    V = {}
    MA = 0
    for u, v, a, b in UVAB:
        g[u][v] = (a, b)
        g[v][u] = (a, b)
        MA += a

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

    d = defaultdict(lambda: INF)
    def f(u, m, s):
        q = []
        c, d = V[u]
        for i in range(1, 100000):
            nc = s+i*c
            if nc > MA:
                q.append((m+i*d, (u, MA)))
                break
            else:
                q.append((m+i*d, (u, nc)))
        return q

    s = (1, min(S, MA))
    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)
        uu, cc = u
        c, dd = V[uu]
        for vv in g[uu]:
            a, b = g[uu][vv]
            for i in range(1000000):
                m = cc + i*c - a
                if m < 0:
                    continue
                m = min(m, MA)
                v = (vv, m)
                alt = i*dd + b + d[u]
                if d[v] > alt:
                    d[v] = alt
                    prev[v] = u
                    heapq.heappush(q, (d[v], v))
                if m == MA:
                    break

    ans = [INF] * (N+1)
    for k, v in d.items():
        u = k[0]
        ans[u] = min(ans[u], v)

    for i in range(2, N+1):
        print(ans[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: Time Limit Exceeded

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

    n_nokori = nokori
    n_cost = 0
    while n_nokori < 2500:
        n_nokori += u
        n_cost += v
        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: Time Limit Exceeded

Solution code:
N,M,S = map(int,input().split())
UVAB = [list(map(int,input().split())) for _ in [0]*M]
CD = [list(map(int,input().split())) for _ in [0]*N]

E = [[] for _ in [0]*N]
for u,v,a,b in UVAB:
    u -= 1
    v -= 1
    E[u].append((v,a,b))
    E[v].append((u,a,b))

import heapq
def Dijkstra(N,E,start,S):
    d = [[-1]*(M*50+1) for _ in [0]*N]
    q = [(0,S,start)]
    while q:
        ci,s,i = heapq.heappop(q)
        if d[i][min(M*50,s)]!= -1:continue
        d[i][min(M*50,s)] = ci
        C,D = CD[i]
        heapq.heappush(q,(ci+D,s+C,i))
        for j,a,b in E[i]:
            if s<a : continue
            heapq.heappush(q,(ci+b,s-a,j))
    return d

d = Dijkstra(N,E,0,S)
for i in range(1,N):
    ans = min(e for e in d[i] if e>0)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq

n,m,s=map(int,input().split())
path=[[] for _ in range(n+1)]
coin=[(0,0)]
time=[float("inf") for _ in range(n+1)]
time[0]=0
queue=[]
A=0
for i in range(m):
    u,v,a,b=map(int,input().split())
    A=max(a,A)
    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))

heapq.heappush(queue,(0,s,1,1))
while len(queue)!=0:
    t,c,v,d=heapq.heappop(queue)
    if time[v]>t:
        time[v]=t
    for nv,na,nb in path[v]:
        if na>c:
            continue
        else:
            heapq.heappush(queue,(t+nb,c-na,nv,d+1))
    if c > (n-d)*A:
        continue
    else:
        heapq.heappush(queue,(t+coin[v][1],c+coin[v][0],v,d))
    
print(*time[2:],sep="\n")

Submission status: Time Limit Exceeded

Solution code:
import heapq

n,m,s=map(int,input().split())
path=[[] for _ in range(n+1)]
coin=[(0,0)]
time=[float("inf") for _ in range(n+1)]
time[0]=0
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))

heapq.heappush(queue,(0,s,1))
while len(queue)!=0:
    t,c,v=heapq.heappop(queue)
    if time[v]>t:
        time[v]=t
    for nv,na,nb in path[v]:
        if na>c:
            continue
        else:
            heapq.heappush(queue,(t+nb,c-na,nv))
    if c > n*50:
        continue
    else:
        heapq.heappush(queue,(t+coin[v][1],c+coin[v][0],v))
    
print(*time[2:],sep="\n")

Submission status: Time Limit Exceeded

Solution code:
import heapq

n,m,s=map(int,input().split())
path=[[] for _ in range(n+1)]
coin=[(0,0)]
time=[float("inf") for _ in range(n+1)]
time[0]=0
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))

heapq.heappush(queue,(0,s,1))
while len(queue)!=0:
    t,c,v=heapq.heappop(queue)
    if max(time)<t:
        continue

    if time[v]>t:
        time[v]=t

    for nv,na,nb in path[v]:
        if na>c:
            continue
        else:
            heapq.heappush(queue,(t+nb,c-na,nv))
    heapq.heappush(queue,(t+coin[v][1],c+coin[v][0],v))
    
print(*time[2:],sep="\n")

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop
N, M, S = map(int, input().split())
edge = [[] for _ in range(N)]
for i 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))

CD = [tuple(map(int, input().split())) for _ in range(N)]
S = min(2500, S)
# キューの中身(時間,銀貨の数,現在地)
q = [(0, S, 0)]
d = [[-1] * 2510 for _ in range(N)]
#d[0][S] = 0
while len(q) > 0:
    t, s, v = heappop(q)
    if d[v][s] > -1: continue
    d[v][s] = t
    for nv, ns, nt in edge[v]:
        if s < ns: continue
        heappush(q, (t+nt, s-ns, nv))
    c, dtime = CD[v]
    if s+c <= 2500:
        heappush(q, (t+dtime, s+c, v))

INF = 10 ** 30
for j in range(1, N):
    print(min([i if i > -1 else INF for i in d[j]]))

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop
N, M, S = map(int, input().split())
edge = [[] for _ in range(N)]
for i 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))

CD = [tuple(map(int, input().split())) for _ in range(N)]
S = min(5000, S)
# キューの中身(時間,銀貨の数,現在地)
q = [(0, S, 0)]
d = [[-1] * 5010 for _ in range(N)]
#d[0][S] = 0
while len(q) > 0:
    t, s, v = heappop(q)
    if d[v][s] > -1: continue
    d[v][s] = t
    for nv, ns, nt in edge[v]:
        if s < ns: continue
        heappush(q, (t+nt, s-ns, nv))
    c, dtime = CD[v]
    if s+c <= 5000:
        heappush(q, (t+dtime, s+c, v))

INF = 10 ** 30
for j in range(1, N):
    print(min([i if i > -1 else INF for i in d[j]]))

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop
import sys
n, m, s = map(int, input().split())
edges = list()
for _ in range(m):
  new_u, new_v, new_a, new_b = map(int, input().split())
  edges.append((new_u-1, new_v-1, new_a, new_b))
coins_range = (n-1)*max(edges,key=lambda item:item[2])[2]+1
c, d = list(), list()
for _ in range(n):
  new_c, new_d = map(int, input().split())
  c.append(new_c)
  d.append(new_d)
adjacency = {(i, j): [] for i in range(n) for j in range(coins_range)}
for (node, coins) in adjacency.keys():
  new_coins = coins+c[node]
  if new_coins<=coins_range-1:
    adjacency[(node, coins)].append(((node, coins+c[node]), (d[node])))
for edge in edges:
  node1, node2, cost, weight = edge
  for coins in range(cost, coins_range):
    adjacency[(node1, coins)].append(((node2, coins-cost), weight))
    adjacency[(node2, coins)].append(((node1, coins-cost), weight))
def dijkstra():
  while state_heap:
    distance, state = heappop(state_heap)
    visited[state] = True
    for (new_state, weight) in adjacency[state]:
      if not visited[new_state]:
        distances[new_state] = min(distances[new_state], distance+weight)
        heappush(state_heap, (distances[new_state], new_state))
distances = {(i, j): float("inf") for i in range(n) for j in range(coins_range)}
initial_state = (0, min(s, coins_range-1))
distances[initial_state] = 0
state_heap = []
heappush(state_heap, (distances[initial_state], initial_state))
visited = {(i, j): False for i in range(n) for j in range(coins_range)}
visited[initial_state] = True
dijkstra()
final_distances = [float("inf")]*n
for ((node, _), distance) in distances.items():
  final_distances[node] = min(final_distances[node], distance)
[print(distance) for distance in final_distances[1:]]

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
def main():
  n,m,s=map(int,input().split())
  uvab=[list(map(int,input().split())) for _ in range(m)]
  cd=[list(map(int,input().split())) for _ in range(n)]
  g=[[]for _ in range(n)]
  for u,v,a,b in uvab:
    g[u-1].append((v-1,a,b))
    g[v-1].append((u-1,a,b))
  import heapq
  inf=pow(10,21)
  max_s=100*51
  dp=[[inf]*(max_s+1)for _ in range(n)]
  kakutei=[[0]*(max_s+1)for _ in range(n)]
  dp[0][min(s,max_s)]=0
  todo=[[0,0,min(s,max_s)]] # [dp[v][i],v,i]
  heapq.heapify(todo)
  flgs=[0]*n
  flg=0
  ans=[inf]*n
  while flg<n:
    _,v,i=heapq.heappop(todo)
    if kakutei[v][i]==1:
      continue
    kakutei[v][i]=1
    if flgs[v]==0:
      flg+=1
      flgs[v]=1
    c,d=cd[v]
    ans[v]=min(ans[v],_)
    # 両替
    j=min(max_s,i+c)
    if kakutei[v][j]==0:
      dp[v][j]=min(dp[v][j],dp[v][i]+d)
      heapq.heappush(todo,[dp[v][j],v,j])
    # 鉄道
    l=g[v]
    for u,a,b in l:
      if i-a>=0 and kakutei[u][i-a]==0:
        dp[u][i-a]=min(dp[u][i-a],dp[v][i]+b)
        heapq.heappush(todo,[dp[u][i-a],u,i-a])
  print(*ans[1:],sep='\n')
if __name__=='__main__':
  main()