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:
import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
from collections import defaultdict, deque
def resolve():
    N, M, S = lr()
    uvab = [[] for i in range(N)]
    amax = 0
    for i in range(M):
        u, v, a, b = lr()
        uvab[u-1].append([v-1, a, b])
        uvab[v-1].append([u-1, a, b])
        amax = max(amax, a)
    cd = []
    for i in range(N):
        cd.append(lr())
    dp = defaultdict(lambda: float('inf'))
    A = amax*(N-1)
    dp[0, min(S, A)] = 0
    s = deque([[0, min(S, A)]])
    while len(s) > 0:
        tu, i = s.popleft()
        for vab in uvab[tu]:
            v, a, b = vab
            if i >= a and i < A and dp[v, i-a] >= dp[tu, i] + b:
                dp[v, i-a] = dp[tu, i] + b
                s.append([v, i-a])
            elif i == A and dp[v, i] >= dp[tu, i] + b:
                dp[v, i] = dp[tu, i] + b
                s.append([v, i])
        c, d = cd[tu]
        t = i
        while t < A:
            nt = min(t+c, A)
            if dp[tu, nt] > dp[tu, t] + d:
                dp[tu, nt] = dp[tu, t] + d
                s.append([tu, nt])
            t = nt
    for i in range(1, N):
        ans = float('inf')
        for j in range(A+1):
            ans = min(dp[i, j], ans)
        print(ans)
resolve()

Submission status: Time Limit Exceeded

Solution code:
import heapq

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)]
cd=[[0]]+cd

ls=[[] for _ in range(n+1)]
for i in range(m):
  tmp=uvab[i]
  ls[tmp[0]].append([tmp[1], tmp[2], tmp[3]])
  ls[tmp[1]].append([tmp[0], tmp[2], tmp[3]])

ans=[-1]*(n+1)

q=[[0, 1, s]]
heapq.heapify(q)

while ans.count(-1)>1:
  tmp=heapq.heappop(q)
  #tmp[0]:時間 tmp[1]:場所 tmp[2]:銀貨
  if ans[tmp[1]]<0:
    ans[tmp[1]]=tmp[0]
    
  heapq.heappush(q, [tmp[0]+cd[tmp[1]][1], tmp[1], tmp[2]+cd[tmp[1]][0]])
  for l in ls[tmp[1]]:
    #l[0]:行先 l[1]:使用銀貨枚数 l[2]:時間
    if tmp[2]>=l[1]:
      heapq.heappush(q, [tmp[0]+l[2], l[0], tmp[2]-l[1]])
      
print(*ans[2:], sep='\n')

Submission status: Time Limit Exceeded

Solution code:
import heapq

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

for i in range(M):
    uvab[i][0] -= 1
    uvab[i][1] -= 1

railways = [[] for _ in range(N)]
max_a = 0
for u, v, a, b in uvab:
    railways[u].append((v, a, b))
    railways[v].append((u, a, b))
    max_a = max(max_a, a)
del uvab

max_silver = max_a * (N - 1)

d = [-1] * N
d[0] = 0
sum_reached = 1
reached = [False] * N
reached[0] = True

Q = [(0, S, 0)]  # (time, silver, station)
visited = set(Q)

while True:
    t, silver, s = Q[0]

    if not reached[s]:
        d[s] = t
        reached[s] = True
        sum_reached += 1
        if sum_reached == N:
            break

    new_state = (t + cd[s][1], silver + cd[s][0], s)
    if new_state in visited:
        heapq.heappop(Q)
    else:
        heapq.heapreplace(Q, new_state)
        visited.add(new_state)

    for dist, a, b in railways[s]:
        if silver >= a:
            new_state = (t + b, silver - a, dist)
            if new_state not in visited:
                heapq.heappush(Q, new_state)
                visited.add(new_state)

print(*d[1:], sep="\n")

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
# coding: utf-8
import sys

stdin = sys.stdin
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip() # ignore trailing spaces


#ダイクストラ(参照:https://gside.org/blog/2019/12/01/)
class Node(object):#頂点
    def __init__(self,  value: int):
        self.value = value

    def getValue(self) -> int:
        return self.value

    def __str__(self):
        return str(self.value)

    def __lt__(seif, other):
        return None


class WeightedEdge(object):#重み付き枝
    def __init__(self, src: Node, dest: Node, weight: int):
        self.src = src
        self.dest = dest
        self.weight = weight

    def getSource(self) -> Node:
        return self.src

    def getDestination(self) -> Node:
        return self.dest

    def getWeight(self) -> int: 
        return self.weight

    def __str__(self):
        return str(self.src.getValue()) + '->('  + str(self.getWeight()) + ')->' + str(self.dest.getValue())


class Digraph(object):#有向グラフ
    def __init__(self):
        self.nodes = []
        self.edges = {}
        self.size = 0

    def addNode(self, node: Node):
        if node in self.nodes:
            raise ValueError('Duplicate node')
        else:
            self.nodes.append(node)
            self.edges[node] = []
            self.size += 1
    
    def addEdge(self, edge: WeightedEdge):
        src = edge.getSource()
        dest = edge.getDestination()
        weight = edge.getWeight()
        if not (src in self.nodes and dest in self.nodes):
            raise ValueError('Node not a graph')

        self.edges[src].append((weight, dest))
    
    def childrenOf(self, node: Node) -> list:#element : tuple
        return self.edges[node]
    
    def __str__(self):
        result = ''
        for src in self.nodes:
            for weightdest in self.edges[src]:
                dest  = weightdest[1]
                result += str(src.getValue()) + '->' + str(dest.getValue()) + '\n'
        return result[:-1]


class RingBuffer(object):
    def __init__(self, size: int):
        self.ringsize = size
        self.size = 0
        self.ring = [None]*size
        self.head = 0
        self.tail = 0
    def enring(self, a: int):
        if self.tail != self.head or self.ring[self.tail] == None:
            self.ring[self.tail] = a
            self.tail += 1
            self.tail %= self.ringsize
            self.size += 1
        else:
            print('Error : This Ring Buffer is full.')
    def dering(self):
        if self.head != self.tail:
            tmp = self.ring[self.head]
            self.ring[self.head] = None # なくてもよい．
            self.head += 1
            self.head %= self.ringsize
            self.size -= 1
            return tmp
        else:
            print(self.head, self.tail)
            print('Error : This Ring Buffer is empty.')


def getPath(goalNode, prev):
    path = [goalNode]
    dest = goalNode.getValue()
    while prev[dest] != float('inf'):
        path.append(prev[dest])
        dest = prev[dest].getValue()
    return list(reversed(path))


def Dijkstra(graph: Digraph, startNode: Node, goalNode: Node = None) -> list:#Reture a list that has minimum distances from the start point to each point
    dist = [float('inf') for _ in range(graph.size)]
    prev = [float('inf') for _ in range(graph.size)]

    dist[startNode.getValue()] = 0
    srcque = RingBuffer(graph.size)
    costque = RingBuffer(graph.size)
    
    srcque.enring(startNode)
    costque.enring(0)
    while srcque.size != 0:
        srcNode = srcque.dering()
        prev_cost = costque.dering()

        if dist[srcNode.getValue()] < prev_cost:
            continue
        
        for cost, destNode  in graph.childrenOf(srcNode):
            if cost != float('inf') and dist[destNode.getValue()] > dist[srcNode.getValue()] + cost:
                dist[destNode.getValue()] = dist[srcNode.getValue()] + cost
                srcque.enring(destNode)
                costque.enring(dist[destNode.getValue()])
                prev[destNode.getValue()] = srcNode
    if goalNode == None:
        return dist
    else:
        return getPath(goalNode, prev)


def identify(coin, city, sumA):
    return city * (sumA+1) + coin


def main():
    #data input
    n,m,s = na()#citysize, loadsize, Agcoin
    sumA = 0#これだけあれば交換しなくても任意の都市にたどり着ける
    loads = []
    for _ in range(m):
        u,v,a,b =na()
        u,v = u-1,v-1
        sumA += a
        loads += [[u,v,-a,b]]
    for i in range(n):
        c,d = na()
        loads += [[i,i,c,d]]
    #create graph
    d = Digraph()
    nodes = []
    for i in range(identify(sumA, n, sumA)+1):#create node
        node = Node(i)
        nodes.append(node)
        d.addNode(node)
    for load in loads:#addEdge
        u,v,a,b = load
        if u!= v:
            for i in range(-1*a,sumA+1):
                idfrom1 = identify(i,u,sumA)
                idto1 = identify(i+a,v,sumA)
                idfrom2 = identify(i,v,sumA)
                idto2 = identify(i+a,u,sumA)
                d.addEdge(WeightedEdge(nodes[idfrom1],nodes[idto1], b))
                d.addEdge(WeightedEdge(nodes[idfrom2],nodes[idto2], b))
        else:
            for i in range(sumA+1):
                idfrom1 = identify(i,u,sumA)
                idto1 = identify(min(i+a,sumA),v,sumA)
                d.addEdge(WeightedEdge(nodes[idfrom1],nodes[idto1], b))
    #Dijkstra
    startNode = nodes[identify(min(s, sumA),0,sumA)]
    ans = Dijkstra(d, startNode) + [float('inf')]
    
    for i in range(1,n):
        print(min(ans[identify(0,i,sumA):identify(0,i+1,sumA)]))
    return

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def solve():
    import sys
    input = sys.stdin.readline
    N,M,S = map(int,input().split())
    UVAB = [tuple(map(int,input().split())) for i in range(M)]
    CD = [tuple(map(int,input().split())) for i in range(N)]

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

    INF = float('inf')
    times = [INF] * (2501 * N)
    start = min(2500,S)*N
    times[start] = 0
    hq = [start]
    ans = [-1] * N
    ans[0] = 0
    reached = 0
    import heapq
    heapq.heapify(hq)
    while hq:
        x = heapq.heappop(hq)
        t,v = divmod(x,N*2501)
        s,i = divmod(v,N)
        if ans[i] < 0:
            ans[i] = t
            reached += 1
            if reached == N-1: break
        for to,a,b in es[i]:
            if a > s: continue
            nv = (s-a)*N + to
            if times[nv] <= t + b: continue
            times[nv] = t + b
            heapq.heappush(hq, (t+b)*N*2501 + nv)
        ns = s
        nt = times[v]
        while ns <= 2500:
            ns += CD[i][0]
            nt += CD[i][1]
            nv = min(2500,ns)*N + i
            if times[nv] <= nt: continue
            times[nv] = nt
            heapq.heappush(hq, nt*N*2501 + nv)
    print(*ans[1:], sep='\n')
solve()

Submission status: Time Limit Exceeded

Solution code:
def solve():
    import sys
    input = sys.stdin.readline
    N,M,S = map(int,input().split())
    UVAB = [tuple(map(int,input().split())) for i in range(M)]
    CD = [tuple(map(int,input().split())) for i in range(N)]

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

    INF = float('inf')
    times = [INF] * (2501 * N)
    start = min(2500,S)*N
    times[start] = 0
    hq = [start]
    ans = [-1] * N
    ans[0] = 0
    reached = set()
    import heapq
    heapq.heapify(hq)
    while hq:
        x = heapq.heappop(hq)
        t,v = divmod(x,N*2501)
        s,i = divmod(v,N)
        if ans[i] < 0:
            ans[i] = t
            reached.add(i)
            if len(reached) == N-1: break
        for to,a,b in es[i]:
            if a > s: continue
            nv = (s-a)*N + to
            if times[nv] <= t + b: continue
            times[nv] = t + b
            heapq.heappush(hq, (t+b)*N*2501 + nv)
        ns = s
        nt = times[v]
        while ns <= 2500:
            ns += CD[i][0]
            nt += CD[i][1]
            nv = min(2500,ns)*N + i
            if times[nv] <= nt: continue
            times[nv] = nt
            heapq.heappush(hq, nt*N*2501 + nv)
    print(*ans[1:], sep='\n')
solve()

Submission status: Time Limit Exceeded

Solution code:
def solve():
    N,M,S = map(int,input().split())
    UVAB = [tuple(map(int,input().split())) for i in range(M)]
    CD = [tuple(map(int,input().split())) for i in range(N)]

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

    INF = float('inf')
    times = [INF] * (2501 * N)
    start = min(2500,S)*N
    times[start] = 0
    hq = [start]
    ans = [-1] * N
    ans[0] = 0
    reached = set()
    import heapq
    heapq.heapify(hq)
    while hq:
        x = heapq.heappop(hq)
        t,v = divmod(x,N*2501)
        s,i = divmod(v,N)
        if ans[i] < 0:
            ans[i] = t
            reached.add(i)
            if len(reached) == N-1: break
        for to,a,b in es[i]:
            if a > s: continue
            nv = (s-a)*N + to
            if times[nv] <= t + b: continue
            times[nv] = t + b
            heapq.heappush(hq, (t+b)*N*2501 + nv)
        ns = s
        nt = times[v]
        while ns <= 2500:
            ns += CD[i][0]
            nt += CD[i][1]
            nv = min(2500,ns)*N + i
            if times[nv] <= nt: continue
            times[nv] = nt
            heapq.heappush(hq, nt*N*2501 + nv)
    print(*ans[1:], sep='\n')
solve()

Submission status: Time Limit Exceeded

Solution code:
def solve():
    N,M,S = map(int,input().split())
    UVAB = [tuple(map(int,input().split())) for i in range(M)]
    CD = [tuple(map(int,input().split())) for i in range(N)]

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

    INF = float('inf')
    times = [INF] * (2501 * N)
    start = min(2500,S)*N
    times[start] = 0
    hq = [(0,start)]
    ans = [-1] * N
    ans[0] = 0
    reached = set()
    import heapq
    heapq.heapify(hq)
    while hq:
        t,v = heapq.heappop(hq)
        s,i = divmod(v,N)
        if ans[i] < 0:
            ans[i] = t
            reached.add(i)
            if len(reached) == N-1: break
        for to,a,b in es[i]:
            if a > s: continue
            nv = (s-a)*N + to
            if times[nv] <= t + b: continue
            times[nv] = t + b
            heapq.heappush(hq, (t+b, nv))
        ns = s
        nt = times[v]
        while ns <= 2500:
            ns += CD[i][0]
            nt += CD[i][1]
            nv = min(2500,ns)*N + i
            if times[nv] <= nt: continue
            times[nv] = nt
            heapq.heappush(hq, (nt, nv))
    print(*ans[1:], sep='\n')
solve()

Submission status: Time Limit Exceeded

Solution code:
def solve():
    N,M,S = map(int,input().split())
    UVAB = [tuple(map(int,input().split())) for i in range(M)]
    CD = [tuple(map(int,input().split())) for i in range(N)]

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

    INF = float('inf')
    times = [INF] * (2501 * N)
    start = min(2500,S)*N
    times[start] = 0
    hq = [(0,start)]
    ans = [-1] * N
    reached = set()
    import heapq
    heapq.heapify(hq)
    while hq:
        t,v = heapq.heappop(hq)
        s,i = divmod(v,N)
        if ans[i] < 0:
            ans[i] = t
            reached.add(i)
            if len(reached) == N: break
        for to,a,b in es[i]:
            if a > s: continue
            nv = (s-a)*N + to
            if times[nv] <= t + b: continue
            times[nv] = t + b
            heapq.heappush(hq, (t+b, nv))
        ns = s
        nt = times[v]
        while ns <= 2500:
            ns += CD[i][0]
            nt += CD[i][1]
            nv = min(2500,ns)*N + i
            if times[nv] <= nt: continue
            times[nv] = nt
            heapq.heappush(hq, (nt, nv))
    print(*ans[1:], sep='\n')
solve()

Submission status: Time Limit Exceeded

Solution code:
import heapq
N, M, init_silver = map(int, input().split())
MAX_COST = 2500
init_silver = min(init_silver, MAX_COST)

G = [[] for _ in range(N)]
for i in range(M):
    u, v, silver_cost, time_cost = map(int, input().split())
    u, v = u - 1, v - 1
    G[u].append([v, silver_cost, time_cost])
    G[v].append([u, silver_cost, time_cost])

change_rate, change_cost = [], []
for i in range(N):
    rate, cost = map(int, input().split())
    change_rate.append(rate)
    change_cost.append(cost)


# dp[i][silver] := 頂点iにいて銀貨をsilver枚持っているような状況を作るために必要な最小時間
dp = [[float('inf')] * (MAX_COST + 1) for _ in range(N)]
dp[0][init_silver] = 0

# 優先度付きキュー: (time, node, silver)
hq = [(0, 0, init_silver)]
while hq:
    time, node, silver = heapq.heappop(hq)

    self_loop_silver = min(silver + change_rate[node], MAX_COST)
    self_loop_cost = time + change_cost[node]
    if self_loop_cost < dp[node][self_loop_silver]:
        dp[node][self_loop_silver] = self_loop_cost
        heapq.heappush(hq, (time + change_cost[node], node, self_loop_silver))

    for to, silver_cost, time_cost in G[node]:
        remain_silver = min(silver - silver_cost, MAX_COST)
        if remain_silver < 0:
            continue

        dp_next_value = time + time_cost
        if dp[to][remain_silver] < dp_next_value:
            continue

        dp[to][remain_silver] = dp_next_value
        heapq.heappush(hq, (dp_next_value, to, remain_silver))

print(*[min(d) for d in dp[1:]], sep="\n")

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys

stdin = sys.stdin
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip() # ignore trailing spaces

def main():
    n,m,s = na()#citysize, loadsize, Agcoin
    loads = [[] for _ in range(n)]#loads[at] = [(at,to1), (A1,B1)), ((at,to2), (A2,B2)), ..]
    sumA = 0#これだけあれば交換しなくても任意の都市にたどり着ける
    for _ in range(m):
        u,v,a,b =na()
        u,v = u-1,v-1
        sumA += a
        a *= -1
        loads[u] += [[u,v,a,b]]
        loads[v] += [[v,u,a,b]]
    for i in range(n):
        c,d = na()
        loads[i] += [[i,i,c,d]]#自分から自分に、銀貨+c枚(増える)時間D分の路線があると考える
        
    ans = [0] + [float('inf') for _ in range(n-1)]
    que = [load0+[0,s,s >= sumA] for load0 in loads[0]]#幅優先探索,[0,s,flag]は今の時間、銀のコイン数、手持ちのコインがsumAより大きくなったことがあるか
    while que != []:
        at,to,coin,time,nowtime,nowcoin,flag = que.pop(0)
        nowtime += time
        nowcoin += coin
        if nowcoin >= 0:#移動できる
            ans[to] = min(ans[to], nowtime)
            flag = flag or nowcoin >= sumA
            for load in loads[to]:
                u,v,a,b = load
                if not (u==v and flag):
                    que += [load + [nowtime, nowcoin, flag]]
    for i in range(n-1):
        print(ans[i+1])
    return

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import math

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

Us=[0]*M
Vs=[0]*M
As=[0]*M
Bs=[0]*M
for i in range(M):
    Us[i],Vs[i],As[i],Bs[i] = map(int,input().split())

# ---
V={}
Ns = max(As)*N
Nv=N*(Ns+1)
cnt=0
for i in range(1,N+1):
    for ns in range(Ns+1):
        V[(i,ns)]=cnt
        cnt+=1
#T= copy.copy(V)


if S > Ns:
    S = Ns

# --
w = [[math.inf]*Nv for _ in range(Nv) ]
# U <-> V
for _ in range(M):
    u = Us.pop()
    v = Vs.pop()
    a = As.pop()
    b = Bs.pop()
    #
    for i in range(Ns+1): # i = 0,..,Ns
        ns_s = Ns - i
        ns_g = ns_s - a
        if ns_g >= 0:
            # U -> V
            w[ V[(u,ns_s)] ][ V[(v,ns_g)] ] = b
            # V -> U
            w[ V[(v,ns_s)] ][ V[(u,ns_g)] ] = b
            #print(u,v,a,b,ns_s,ns_g,V[(u,ns_s)],V[(v,ns_g)])

# -----

for i in range(N):
    c,d = map(int,input().split())
    v = i+1
    for j in range(Ns): # j = 0,...,Ns-1
        ns_s = j
        ns_g = j + c
        if ns_g > Ns:
            ns_g = Ns
        w[ V[(v,ns_s)] ][ V[(v,ns_g)] ] = d

# -----
D=[-1]*Nv
# -----
T=set(range(Nv))
visited = set([1])
allcity = set(range(1,N+1))

s=V[(1,S)]
T.remove(s) #del T[s]
D[s] = 0
for v in T:
    D[v] = w[ s ][ v ]
#while len(T) > 0:
for _ in range(Nv-1):
    u = min(T,key=lambda x:D[x])
    T.remove(u)

    visited.add(u//(Ns+1)+1)
    if visited == allcity:
        break

    for v in T:
        D[ v ] = min( D[ v ], D[ u ] + w[ u ][ v ] )

for i in range(1,N):
    ans = min([D[i*(Ns+1)+v] for v in range(Ns+1)])
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy
import math

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

Us=[0]*M
Vs=[0]*M
As=[0]*M
Bs=[0]*M
for i in range(M):
    Us[i],Vs[i],As[i],Bs[i] = map(int,input().split())

# ---
V={}
Ns = max(As)*N
Nv=N*(Ns+1)
cnt=0
for i in range(1,N+1):
    for ns in range(Ns+1):
        V[(i,ns)]=cnt
        cnt+=1
#T= copy.copy(V)


if S > Ns:
    S = Ns

# --
w = [[math.inf]*Nv for _ in range(Nv) ]
# U <-> V
for _ in range(M):
    u = Us.pop()
    v = Vs.pop()
    a = As.pop()
    b = Bs.pop()
    #
    for i in range(Ns+1): # i = 0,..,Ns
        ns_s = Ns - i
        ns_g = ns_s - a
        if ns_g >= 0:
            # U -> V
            w[ V[(u,ns_s)] ][ V[(v,ns_g)] ] = b
            # V -> U
            w[ V[(v,ns_s)] ][ V[(u,ns_g)] ] = b
            #print(u,v,a,b,ns_s,ns_g,V[(u,ns_s)],V[(v,ns_g)])

# -----

for i in range(N):
    c,d = map(int,input().split())
    v = i+1
    for j in range(Ns): # j = 0,...,Ns-1
        ns_s = j
        ns_g = j + c
        if ns_g > Ns:
            ns_g = Ns
        w[ V[(v,ns_s)] ][ V[(v,ns_g)] ] = d

# -----
D=[-1]*Nv
# -----
T=set(range(Nv))
visited = set([1])
allcity = set(range(1,N+1))

s=V[(1,S)]
T.remove(s) #del T[s]
D[s] = 0
for v in T:
    D[v] = w[ s ][ v ]
#while len(T) > 0:
for _ in range(Nv-1):
    u = min(T,key=lambda x:D[x])
    T.remove(u)

    visited.add(u//(Ns+1)+1)
    if visited == allcity:
        break

    for v in T:
        D[ v ] = min( D[ v ], D[ u ] + w[ u ][ v ] )

for i in range(2,N+1):
    ans = min([ D[ V[(i,ns)] ] for ns in range(Ns+1) ])
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy
import math

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

Us=[0]*M
Vs=[0]*M
As=[0]*M
Bs=[0]*M
for i in range(M):
    Us[i],Vs[i],As[i],Bs[i] = map(int,input().split())

# ---
V={}
Ns = max(As)*N
Nv=N*(Ns+1)
cnt=0
for i in range(1,N+1):
    for ns in range(Ns+1):
        V[(i,ns)]=cnt
        cnt+=1
#T= copy.copy(V)


if S > Ns:
    S = Ns

# --
w = [[math.inf]*Nv for _ in range(Nv) ]
# U <-> V
for _ in range(M):
    u = Us.pop()
    v = Vs.pop()
    a = As.pop()
    b = Bs.pop()
    #
    for i in range(Ns+1): # i = 0,..,Ns
        ns_s = Ns - i
        ns_g = ns_s - a
        if ns_g >= 0:
            # U -> V
            w[ V[(u,ns_s)] ][ V[(v,ns_g)] ] = b
            # V -> U
            w[ V[(v,ns_s)] ][ V[(u,ns_g)] ] = b
            #print(u,v,a,b,ns_s,ns_g,V[(u,ns_s)],V[(v,ns_g)])

# -----

for i in range(N):
    c,d = map(int,input().split())
    v = i+1
    for j in range(Ns): # j = 0,...,Ns-1
        ns_s = j
        ns_g = j + c
        if ns_g > Ns:
            ns_g = Ns
        w[ V[(v,ns_s)] ][ V[(v,ns_g)] ] = d

# -----
D=[-1]*Nv
# -----
T=set(range(Nv))

s=V[(1,S)]
T.remove(s) #del T[s]
D[s] = 0
for v in T:
    D[v] = w[ s ][ v ]
#while len(T) > 0:
for _ in range(Nv-1):
    u = min(T,key=lambda x:D[x])
    T.remove(u)
    for v in T:
        D[ v ] = min( D[ v ], D[ u ] + w[ u ][ v ] )

for i in range(2,N+1):
    ans = min([ D[ V[(i,ns)] ] for ns in range(Ns+1) ])
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy
import math

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

Us=[0]*M
Vs=[0]*M
As=[0]*M
Bs=[0]*M
for i in range(M):
    Us[i],Vs[i],As[i],Bs[i] = map(int,input().split())

# ---
V={}
Ns = max(As)*N
Nv=N*(Ns+1)
cnt=0
for i in range(1,N+1):
    for ns in range(Ns+1):
        V[(i,ns)]=cnt
        cnt+=1
#T= copy.copy(V)


if S > Ns:
    S = Ns

# --
w = [[math.inf]*Nv for _ in range(Nv) ]
# U <-> V
for _ in range(M):
    u = Us.pop()
    v = Vs.pop()
    a = As.pop()
    b = Bs.pop()
    #
    for i in range(Ns+1): # i = 0,..,Ns
        ns_s = Ns - i
        ns_g = ns_s - a
        if ns_g >= 0:
            # U -> V
            w[ V[(u,ns_s)] ][ V[(v,ns_g)] ] = b
            # V -> U
            w[ V[(v,ns_s)] ][ V[(u,ns_g)] ] = b
            #print(u,v,a,b,ns_s,ns_g,V[(u,ns_s)],V[(v,ns_g)])

# -----

for i in range(N):
    c,d = map(int,input().split())
    v = i+1
    for j in range(Ns): # j = 0,...,Ns-1
        ns_s = j
        ns_g = j + c
        if ns_g > Ns:
            ns_g = Ns
        w[ V[(v,ns_s)] ][ V[(v,ns_g)] ] = d

# -----
D=[-1]*Nv
# -----
T=list(range(Nv))

s=V[(1,S)]
T.remove(s) #del T[s]
D[s] = 0
for v in T:
    D[v] = w[ s ][ v ]
#while len(T) > 0:
for _ in range(Nv-1):
    u = min(T,key=lambda x:D[x])
    T.remove(u)
    for v in T:
        D[ v ] = min( D[ v ], D[ u ] + w[ u ][ v ] )

for i in range(2,N+1):
    ans = min([ D[ V[(i,ns)] ] for ns in range(Ns+1) ])
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from heapq import *
n,m,s=map(int,input().split())
c=[0]*n
d=[0]*n
g=[[]for i in range(n)]

for i in range(m):
    u,v,a,b=map(int,input().split())
    u-=1
    v-=1
    g[u].append((v,a,b))
    g[v].append((u,a,b))
for i in range(n):
    c[i],d[i]=map(int,input().split())

flag=0 #if this == (1<<n)-1 then finish roop
endflag=[[False]*2501 for i in range(n)]
mintimes=[10**15]*n
hp=[(0,min(2500,s),0)]#(time,silver,node)

while flag!=((1<<n)-1):
    time,silver,node = heappop(hp)
    flag=flag|(1<<node)
    endflag[node][silver]=True
    mintimes[node]=min(mintimes[node],time)

    for atnode,costmoney,costtime in g[node]:
        if costmoney<=silver and not endflag[atnode][silver-costmoney]:
            heappush(hp,(time+costtime,silver-costmoney,atnode))

    if silver!=2500 and not endflag[node][min(silver+c[node],2500)]:
        heappush(hp,(time+d[node],min(silver+c[node],2500),node))
        
print(*mintimes[1:],sep="\n")