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:
def main():
    import heapq
    
    def dijkstra(graph,start,cd,MAX,s):
        dist = [[float("inf")]*MAX for _ in range(n)]
        q = []
        
        c,d = cd[start]
        for i in range(MAX):
            if c*i+s < MAX:
                dist[start][c*i+s] = d*i
                heapq.heappush(q, (d*i,start,s+c*i))
            else:
                break
        while q:
            cost, cur_node,coin = heapq.heappop(q)
            
            if dist[cur_node][coin] < cost:
                continue
            
            for nex_node,nex_cost,nex_time  in graph[cur_node]:
                if coin >= nex_cost and dist[nex_node][coin-nex_cost] > cost+nex_time:
                    now_coin = coin - nex_cost
                    now_cost = cost+nex_time
                    c,d = cd[nex_node]
                    for i in range(MAX):
                        if c*i+now_coin < MAX:
                            if dist[nex_node][c*i+now_coin] > d*i+now_cost:
                                dist[nex_node][c*i+now_coin] = d*i+now_cost
                                heapq.heappush(q, (d*i+now_cost,nex_node,now_coin+c*i))
                        else:
                            break
                    
        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,2501,min(s,2500))
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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
        que.append((dist + d, cost, to))

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

Submission status: Time Limit Exceeded

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

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

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

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

# 解答ACする
# Dijakstraの状態を(頂点、所持している銀貨の枚数, cost)で持つ
def dijakstra(goal):
    # SIZE = max_a * n + 1
    SIZE = 2501
    global s
    if s > SIZE:
        s = SIZE
    nodes = [[INF for _ in range(SIZE)] for _ in range(n)]
    nodes[0][1] = 0
    que = [(0, 0, s)]
    heapify(que)
    while len(que) > 0:
        # print(que[:3])
        cost, num, silver = heappop(que)
        # print(cost, num, silver)
        if num == goal:
            return cost
        c, d = cd[num]
        for v in edges[num].keys():
            a, b = edges[num][v]

            times = -1
            to = silver - a
            while to < SIZE:
                times += 1
                plus = times * c
                to = silver + plus - a
                if to < 0:
                    continue
                if to >= SIZE:
                    break
                if nodes[v][to] > cost + b + d * times:
                    nodes[v][to] = cost + b + d * times
                    heappush(que, (cost + b + d * times, v, to))

for i in range(1, n):
    print(dijakstra(i))

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq

input = sys.stdin.readline

COST_MAX = 2501
TIME_MAX = 10 ** 15

N, M, S = map(int, input().split())
fare_adj = [[COST_MAX] * N for _ in range(N)]
time_adj = [[TIME_MAX] * N for _ in range(N)]
fare_max = 0
for i in range(M):
    u, v, a, b = map(int, input().split())
    u -= 1
    v -= 1
    fare_adj[u][v] = fare_adj[v][u] = a
    time_adj[u][v] = time_adj[v][u] = b
    fare_max = max(fare_max, a)

exchanges = []
for i in range(N):
    # g-s rate, waiting duration
    c, d = map(int, input().split())
    exchanges.append((c, d))


WALLET_MAX = fare_max * (N - 1)
mintime = [[TIME_MAX] * (WALLET_MAX + 1) for _ in range(N)]


def search():
    q = [(0, 0, min(S, WALLET_MAX))]
    while q:
        t, loc, silvers = heapq.heappop(q)
        if t > mintime[loc][silvers]:
            continue
        mintime[loc][silvers] = t
        while True:
            for nloc in range(N):
                if nloc == loc:
                    continue
                ntime = t + time_adj[loc][nloc]
                nsilvers = min(silvers - fare_adj[loc][nloc], WALLET_MAX)
                if nsilvers >= 0 and ntime < mintime[nloc][nsilvers]:
                    mintime[nloc][nsilvers] = ntime
                    heapq.heappush(q, (ntime, nloc, nsilvers))
            rate, wait = exchanges[loc]
            t += wait
            if silvers > WALLET_MAX:
                break
            silvers += rate


search()
for t in range(1, N):
    print(min(mintime[t]))

Submission status: Time Limit Exceeded

Solution code:
import heapq

COST_MAX = 2501
TIME_MAX = 10 ** 15

N, M, S = map(int, input().split())
fare_adj = [[COST_MAX] * N for _ in range(N)]
time_adj = [[TIME_MAX] * N for _ in range(N)]
fare_max = 0
for i in range(M):
    u, v, a, b = map(int, input().split())
    u -= 1
    v -= 1
    fare_adj[u][v] = fare_adj[v][u] = a
    time_adj[u][v] = time_adj[v][u] = b
    fare_max = max(fare_max, a)

exchanges = []
for i in range(N):
    # g-s rate, waiting duration
    c, d = map(int, input().split())
    exchanges.append((c, d))


WALLET_MAX = fare_max * (N - 1)
mintime = [[TIME_MAX] * (WALLET_MAX + 1) for _ in range(N)]


def search():
    q = [(0, 0, min(S, WALLET_MAX))]
    while q:
        t, loc, silvers = heapq.heappop(q)
        if t > mintime[loc][silvers]:
            continue
        mintime[loc][silvers] = t
        while True:
            for nloc in range(N):
                if nloc == loc:
                    continue
                ntime = t + time_adj[loc][nloc]
                nsilvers = min(silvers - fare_adj[loc][nloc], WALLET_MAX)
                if nsilvers >= 0 and ntime < mintime[nloc][nsilvers]:
                    mintime[nloc][nsilvers] = ntime
                    heapq.heappush(q, (ntime, nloc, nsilvers))
            rate, wait = exchanges[loc]
            t += wait
            if silvers > WALLET_MAX:
                break
            silvers += rate


search()
for t in range(1, N):
    print(min(mintime[t]))

Submission status: Time Limit Exceeded

Solution code:
import heapq

WALLET_MAX = 2501
TIME_MAX = 10 ** 15

N, M, S = map(int, input().split())
fare_adj = [[WALLET_MAX] * N for _ in range(N)]
time_adj = [[TIME_MAX] * N for _ in range(N)]
fare_max = 0
for i in range(M):
    u, v, a, b = map(int, input().split())
    u -= 1
    v -= 1
    fare_adj[u][v] = fare_adj[v][u] = a
    time_adj[u][v] = time_adj[v][u] = b
    fare_max = max(fare_max, a)

exchanges = []
for i in range(N):
    # g-s rate, waiting duration
    c, d = map(int, input().split())
    exchanges.append((c, d))


WALLET_MAX = fare_max * (N - 1)
mintime = [[TIME_MAX] * (WALLET_MAX + 1) for _ in range(N)]


def search():
    q = [(0, 0, min(S, WALLET_MAX))]
    while q:
        t, loc, silvers = heapq.heappop(q)
        if t >= mintime[loc][silvers]:
            continue
        mintime[loc][silvers] = t
        while True:
            for nloc in range(N):
                if nloc == loc:
                    continue
                ntime = t + time_adj[loc][nloc]
                nsilvers = min(silvers - fare_adj[loc][nloc], WALLET_MAX)
                if nsilvers >= 0 and ntime < mintime[nloc][nsilvers]:
                    heapq.heappush(q, (ntime, nloc, nsilvers))
            rate, wait = exchanges[loc]
            t += wait
            if silvers > WALLET_MAX:
                break
            silvers += rate


search()
for t in range(1, N):
    print(min(mintime[t]))

Submission status: Time Limit Exceeded

Solution code:
import heapq

WALLET_MAX = 2501
TIME_MAX = 10 ** 15

N, M, S = map(int, input().split())
fare_adj = [[WALLET_MAX] * N for _ in range(N)]
time_adj = [[TIME_MAX] * N for _ in range(N)]
fare_max = 0
for i in range(M):
    u, v, a, b = map(int, input().split())
    u -= 1
    v -= 1
    fare_adj[u][v] = fare_adj[v][u] = a
    time_adj[u][v] = time_adj[v][u] = b
    fare_max = max(fare_max, a)

exchanges = []
for i in range(N):
    # g-s rate, waiting duration
    c, d = map(int, input().split())
    exchanges.append((c, d))


WALLET_MAX = fare_max * (N - 1)
mintime = [[TIME_MAX] * (WALLET_MAX + 1) for _ in range(N)]


def search():
    q = [(0, 0, min(S, WALLET_MAX))]
    while q:
        t, loc, silvers = heapq.heappop(q)
        if t >= mintime[loc][silvers]:
            continue
        mintime[loc][silvers] = t
        while silvers <= WALLET_MAX:
            for nloc in range(N):
                if nloc == loc:
                    continue
                ntime = t + time_adj[loc][nloc]
                nsilvers = min(silvers - fare_adj[loc][nloc], WALLET_MAX)
                if nsilvers >= 0 and ntime < mintime[nloc][nsilvers]:
                    heapq.heappush(q, (ntime, nloc, nsilvers))
            rate, wait = exchanges[loc]
            assert rate > 0 and wait > 0
            t += wait
            silvers += rate


search()
for t in range(1, N):
    print(min(mintime[t]))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 # 998244353
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n, m, s = map(int,input().split())
    E = []
    S = 1
    for _ in range(m):
        u, v, a, b = map(int,input().split())
        u -= 1; v -= 1
        E.append((u, v, -a, b)) # a : cost of silver
        S += a
    for v in range(n):
        c, d = map(int,input().split()) # c : earning silver
        E.append((v, v, c, d))

    dp = [[INF] * S for _ in range(n)]
    dp[0][min(s, S - 1)] = 0

    # 基本的には Bellman - Ford で確定
    for _ in range(2 * n - 2):
        for u, v, ds, dt in E:
            for s in range(S):
                ns = s + ds
                if not (0 <= ns < S):
                    continue
                dp[v][ns] = min(dp[v][ns], dp[u][s] + dt)
                dp[u][ns] = min(dp[u][ns], dp[v][s] + dt)

    for i in range(1, n):
        print(min(dp[i][j] for j in range(S)))
resolve()

Submission status: Time Limit Exceeded

Solution code:
import heapq

COST_MAX = 2501
TIME_MAX = 10 ** 15

N, M, S = map(int, input().split())
fare_adj = [[COST_MAX] * N for _ in range(N)]
time_adj = [[TIME_MAX] * N for _ in range(N)]
fare_max = 0
fare_sum = 0
for i in range(M):
    u, v, a, b = map(int, input().split())
    u -= 1
    v -= 1
    fare_adj[u][v] = fare_adj[v][u] = a
    time_adj[u][v] = time_adj[v][u] = b
    fare_sum += a
    fare_max = max(fare_max, a)

exchanges = []
for i in range(N):
    # g-s rate, waiting duration
    c, d = map(int, input().split())
    exchanges.append((c, d))


mintime = [[TIME_MAX] * (fare_sum + 1) for _ in range(N)]


def search():
    q = [(0, 0, S)]
    while q:
        t, loc, silvers = heapq.heappop(q)
        silvers = min(silvers, fare_sum)
        if t >= mintime[loc][silvers]:
            continue
        mintime[loc][silvers] = t
        while silvers <= fare_sum:
            for nloc in range(N):
                if nloc == loc:
                    continue
                ntime = t + time_adj[loc][nloc]
                nsilvers = min(silvers - fare_adj[loc][nloc], fare_sum)
                if nsilvers >= 0 and ntime < mintime[nloc][nsilvers]:
                    heapq.heappush(q, (ntime, nloc, nsilvers))
            rate, wait = exchanges[loc]
            t += wait
            silvers += rate


search()
for t in range(1, N):
    print(min(mintime[t]))

Submission status: Time Limit Exceeded

Solution code:
import heapq

COST_MAX = 2501
TIME_MAX = 10 ** 15

N, M, S = map(int, input().split())
fare_adj = [[COST_MAX] * N for _ in range(N)]
time_adj = [[TIME_MAX] * N for _ in range(N)]
fare_max = 0
fare_sum = 0
for i in range(M):
    u, v, a, b = map(int, input().split())
    u -= 1
    v -= 1
    fare_adj[u][v] = fare_adj[v][u] = a
    time_adj[u][v] = time_adj[v][u] = b
    fare_sum += a
    fare_max = max(fare_max, a)

exchanges = []
for i in range(N):
    # g-s rate, waiting duration
    c, d = map(int, input().split())
    exchanges.append((c, d))


mintime = [[TIME_MAX] * (fare_sum + 1) for _ in range(N)]


def search():
    q = [(0, 0, S)]
    while q:
        t, loc, silvers = heapq.heappop(q)
        silvers = min(silvers, fare_sum)
        if t >= mintime[loc][silvers]:
            continue
        mintime[loc][silvers] = t
        while True:
            for nloc in range(N):
                if nloc == loc:
                    continue
                ntime = t + time_adj[loc][nloc]
                nsilvers = min(silvers - fare_adj[loc][nloc], fare_sum)
                if nsilvers >= 0 and ntime < mintime[nloc][nsilvers]:
                    heapq.heappush(q, (ntime, nloc, nsilvers))
            rate, wait = exchanges[loc]
            t += wait
            if silvers > fare_sum:
                break
            silvers += rate


search()
for t in range(1, N):
    print(min(mintime[t]))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 # 998244353
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n, m, s = map(int,input().split())
    E = []
    for _ in range(m):
        u, v, a, b = map(int,input().split())
        u -= 1; v -= 1
        E.append((u, v, -a, b)) # a : cost of silver
    for v in range(n):
        c, d = map(int,input().split()) # c : earning silver
        E.append((v, v, c, d))

    S = 5050 # silver を 5000 以上稼ぐ必要はない
    dp = [[INF] * S for _ in range(n)]
    dp[0][min(s, S - 1)] = 0

    # 基本的には Bellman - Ford で確定
    for _ in range(2 * n + 2):
        for u, v, ds, dt in E:
            for s in range(S):
                ns = s + ds
                if not (0 <= ns < S):
                    continue
                dp[v][ns] = min(dp[v][ns], dp[u][s] + dt)
                dp[u][ns] = min(dp[u][ns], dp[v][s] + dt)

    for i in range(1, n):
        print(min(dp[i][j] for j in range(S)))
resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

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

def print_l(l):
    print(' '.join(map(str, l)))

class Interval():
    def __init__(self, li):
        self.li = li
        self.n = len(li)
        self.sum_li = [li[0]]
        for i in range(1, self.n):
            self.sum_li.append(self.sum_li[i-1] + li[i])

    def sum(self, a, b=None):
        if b is None:
            return self.sum(0, a)

        res = self.sum_li[min(self.n-1, b-1)]
        if a > 0:
            res -= self.sum_li[a-1]
        return res

n,m,s=l_in()

uvab=[]
edges = [[] for _ in range(n)]
for _ in range(m):
    u,v,a,b = l_in()
    edges[u-1].append((v-1,a,b))
    edges[v-1].append((u-1,a,b))

cd = [l_in() for _ in range(n)]

# dp[i][g] city i で g まいの銀貨をもつための最小時間
m = 51*n
#m = 4
dp = [[-1]*m for _ in range(n)]


from heapq import heappush,heappop
h = []

for g in range(min(s+1,m+3)):
    heappush(h, (0,-g,0))

while len(h) > 0:
    t,g,i = h[0]
    g = -g
#    print("t,g,i", t,g,i)
    #

    heappop(h)
    if dp[i][min(g,m-1)] != -1:
        continue

    
    dp[i][min(g,m-1)] = t
    
    for v,a,b in edges[i]:
        if g-a >= 0:
            heappush(h,(t+b,-(g-a),v))
#            print("push", t+b,-g+a,v)

    c,d = cd[i]
    heappush(h,(t+d,-(g+c),i))
    
#    if dp[i][min(g+c,m-1)] == -1:

for d in dp:
    pass
#    print(d)


for i in range(1, n):
    res = -1
    for v,a,b in edges[i]:
        min_t = -1
        for g in range(a,m):
            t = dp[v][g]
            if t == -1:
                continue
            if min_t == -1 or min_t > t:
                min_t = t
#                print("min_t", v,g,min_t)

        if res == -1 or res > min_t+b:
            res = min_t+b

#    print(dp[i])
    for t in dp[i]:
        if t == -1:
            continue
        if res == -1  or t < res:
            continue
            res = t
            
    print(res)

Submission status: Time Limit Exceeded

Solution code:
import heapq
def dijkstra_heap():
    used = [-1] * (2501*n)
    edgelist=[]
    d=[0]*n
    d[0]=1
    f=1
    for i in range(0,2501):
        if 0<=ss+i*cd[0][0]<=2500:
            heapq.heappush(edgelist,[cd[0][1]*i,cd[0][0]*i+ss])
        else:
            break
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        if used[minedge[1]]!=-1:
            continue
        v = minedge[1]
        kai=minedge[0]
        mai=v%2501
        used[v] = kai
        if d[v//2501]==0:
            d[v//2501]=1
            f+=1
            if f==n:
                return used
        for e in edge[v//2501]:
            if mai-e[1]>=0:
                for i in range(2501):
                    sss=mai-e[1]+cd[e[2]][0]*i
                    if 0<=sss<=2500:
                        if used[e[2]*2501+sss]==-1:
                            heapq.heappush(edgelist,[e[0]+kai+cd[e[2]][1]*i,e[2]*2501+sss])  
                    else:
                        break
    return used

################################
n,m,ss = map(int,input().split())
ss=min(2500,ss)
edge = [[] for i in range(n)]

for i in range(m):
    x,y,a,b = map(int,input().split())
    edge[x-1].append([b,a,y-1])
    edge[y-1].append([b,a,x-1])
cd=[]
for i in range(n):
    cd.append(list(map(int,input().split())))
pp=dijkstra_heap()
for i in range(1,n):
    ans=10**20
    for j in range(2501):
        if pp[i*2501+j]!=-1:
            ans=min(ans,pp[i*2501+j])
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True  and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

#from collections import defaultdict
import heapq
n,m,s = inm()
aas = []
dst = [{} for i in range(n+1)]
for i in range(m):
    uu,vv,aa,bb = inm()
    dst[uu][vv] = (aa,bb)
    dst[vv][uu] = (aa,bb)
    aas.append(aa)
maxa = max(aas)
s = min(s,(maxa+1)*n-1)
c = [-1]
d = [-1]
for i in range(n):
    cc,dd = inm()
    c.append(cc)
    d.append(dd)

#dst2 = defaultdict(dict)
dst2 = {}
for u in range(1,n+1):
    for p in range((maxa+1)*n-c[u]):
        dst2[(u,p)] = {(u,p+c[u]) : d[u]}
    for v in dst[u]:
        m = dst[u][v][0]
        t = dst[u][v][1]
        for p in range(m,(maxa+1)*n):
            if (u,p) not in dst2:
                dst2[(u,p)] = {}
            dst2[(u,p)][(v,p-m)] = t

if DBG:
    print("dst2)")
    for z in dst2:
        printn(str(z)+':')
        ddprint(dst2[z])
cost = {}
for z in dst2:
    cost[z] = BIG
q = [(0,1,s)]
while len(q)>0:
    dd,u,p = heapq.heappop(q)
    if cost[(u,p)]<=dd:
        continue
    cost[(u,p)] = dd
    for v,r in dst2[(u,p)]:
        heapq.heappush(q,(dd+dst2[(u,p)][(v,r)], v,r))

if DBG:
    print("cost)")
    for z in cost:
        printn(str(z)+':')
        ddprint(cost[z])
ans = [BIG]*(n+1)
for u,p in cost:
    ans[u] = min(ans[u], cost[(u,p)])
for i in range(2,n+1):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop

infi = 10 ** 20
n, m, s = map(int, input().split())
time_graph = [[] for _ in range(n + 1)]
money_graph = [[0] * (n + 1) for _ in range(n + 1)]
for _ in range(m):
    u, v, a, b = map(int, input().split())
    time_graph[v].append((b, u))
    time_graph[u].append((b, v))
    money_graph[u][v] = a
    money_graph[v][u] = a


rate = [(0, 0) for _ in range(n + 1)]
for i in range(1, n + 1):
    c, d = map(int, input().split())
    rate[i] = (c, d)

start = 1

time = [infi] * (n + 1)
time[start] = 0
que = [(0, s, start)]
cnt = 0
visited = set()
used_pair = set()
cnt = 0
while que:
    t_edge, m_edge, edge = heappop(que)
    if (t_edge, m_edge, edge) in used_pair:
        continue
    used_pair.add((t_edge, m_edge, edge))
    if time[edge] > t_edge:
        time[edge] = t_edge
    if not (edge in visited):
        cnt += 1
        visited.add(edge)
    if cnt == n:
        break
    delta_money, delta_time = rate[edge]
    heappush(que, (t_edge + delta_time, m_edge + delta_money, edge))
    for t_newedge, newedge in time_graph[edge]:
        newtime = t_edge + t_newedge
        newmoney = m_edge - money_graph[edge][newedge]
        if newmoney < 0:
            continue
        heappush(que, (newtime, newmoney, newedge))

print(*time[2:], sep="\n")

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop

infi = 10 ** 20
n, m, s = map(int, input().split())
time_graph = [[] for _ in range(n + 1)]
money_graph = [[0] * (n + 1) for _ in range(n + 1)]
for _ in range(m):
    u, v, a, b = map(int, input().split())
    time_graph[v].append((b, u))
    time_graph[u].append((b, v))
    money_graph[u][v] = a
    money_graph[v][u] = a


rate = [(0, 0) for _ in range(n + 1)]
for i in range(1, n + 1):
    c, d = map(int, input().split())
    rate[i] = (c, d)

start = 1

time = [infi] * (n + 1)
time[start] = 0
que = [(0, s, start)]
cnt = 0
visited = set()
cnt = 0
while que:
    t_edge, m_edge, edge = heappop(que)
    if time[edge] > t_edge:
        time[edge] = t_edge
    if not (edge in visited):
        cnt += 1
        visited.add(edge)
    if cnt == n:
        break
    delta_money, delta_time = rate[edge]
    heappush(que, (t_edge + delta_time, m_edge + delta_money, edge))
    for t_newedge, newedge in time_graph[edge]:
        newtime = t_edge + t_newedge
        newmoney = m_edge - money_graph[edge][newedge]
        if newmoney < 0:
            continue
        heappush(que, (newtime, newmoney, newedge))

print(*time[2:], sep="\n")

Submission status: Time Limit Exceeded

Solution code:
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True  and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

from collections import defaultdict
import heapq
n,m,s = inm()
aas = []
dst = [{} for i in range(n+1)]
for i in range(m):
    uu,vv,aa,bb = inm()
    dst[uu][vv] = (aa,bb)
    dst[vv][uu] = (aa,bb)
    aas.append(aa)
maxa = max(aas)
s = min(s,(maxa+1)*n-1)
c = [-1]
d = [-1]
for i in range(n):
    cc,dd = inm()
    c.append(cc)
    d.append(dd)

dst2 = defaultdict(dict)
for u in range(1,n+1):
    for v in dst[u]:
        m = dst[u][v][0]
        t = dst[u][v][1]
        for p in range((maxa+1)*n-c[u]):
            dst2[(u,p)][(u,p+c[u])] = d[u]
        for p in range((maxa+1)*n):
            if p>=m:
                dst2[(u,p)][(v,p-m)] = t

if DBG:
    print("dst2)")
    for z in dst2:
        printn(str(z)+':')
        ddprint(dst2[z])
cost = {}
for z in dst2:
    cost[z] = BIG
q = [(0,1,s)]
while len(q)>0:
    dd,u,p = heapq.heappop(q)
    if cost[(u,p)]<=dd:
        continue
    cost[(u,p)] = dd
    for v,r in dst2[(u,p)]:
        heapq.heappush(q,(dd+dst2[(u,p)][(v,r)], v,r))

if DBG:
    print("cost)")
    for z in cost:
        printn(str(z)+':')
        ddprint(cost[z])
ans = [BIG]*(n+1)
for u,p in cost:
    ans[u] = min(ans[u], cost[(u,p)])
for i in range(2,n+1):
    print(ans[i])

Submission status: Time Limit Exceeded

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

#O(ElogV)
import heapq
def dijkstra_heap(s):
  #始点sから各頂点への最短距離
  d,used={},{}
  for v in vlist:
    d[v]=float("inf")
    used[v]=True
  d[s]=0
  used[s]=False
  
  edgelist = []
  for e in edge[s]:
    heapq.heappush(edgelist,e)
    
  while len(edgelist):
    minedge = heapq.heappop(edgelist)
    #まだ使われてない頂点の中から最小の距離のものを探す
    if not used[minedge[1]]:
      continue
    v = minedge[1]
    d[v] = minedge[0]
    used[v] = False
    for e in edge[v]:      
      if used[e[1]]:
        heapq.heappush(edgelist,(e[0]+d[v],e[1]))
        
  return d

uvab_list=[]
for i in range(M):
  U,V,A,B=map(int,input().split())
  uvab_list.append((U,V,A,B))
  
cd_list=[]
for i in range(N):
  C,D=map(int,input().split())
  cd_list.append((C,D))
  
vlist=[]
for i in range(1,N+1):
  for j in range(2501):
    vlist.append((i,j))

edge={}
for U,V,A,B in uvab_list:
  for j in range(2501):
    if j-A>=0:
      if not (U,j) in edge:
        edge[(U,j)]=[]    
      edge[(U,j)].append((B,(V,j-A)))
      if not (V,j) in edge:
        edge[(V,j)]=[]
      edge[(V,j)].append((B,(U,j-A)))

for i in range(N):
  C,D=cd_list[i]
  for j in range(2501):
    if not (i+1,j) in edge:
      edge[(i+1,j)]=[]    
    jj=min(2500,j+C)    
    edge[(i+1,j)].append((D,(i+1,jj)))
    
n=len(vlist)
w=len(edge)
res=dijkstra_heap((1,S))
#print(res)

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