Problem:


Score : 500 points

Problem Statement

There are N towns numbered 1 to N and M roads. The i-th road connects Town A_i and Town B_i bidirectionally and has a length of C_i.

Takahashi will travel between these towns by car, passing through these roads. The fuel tank of his car can contain at most L liters of fuel, and one liter of fuel is consumed for each unit distance traveled. When visiting a town while traveling, he can full the tank (or choose not to do so). Travel that results in the tank becoming empty halfway on the road cannot be done.

Process the following Q queries:

The tank is now full. Find the minimum number of times he needs to full his tank while traveling from Town s_i to Town t_i. If Town t_i is unreachable, print -1.

Constraints

All values in input are integers.

2 \leq N \leq 300

0 \leq M \leq \frac{N(N-1)}{2}

1 \leq L \leq 10^9

1 \leq A_i, B_i \leq N

A_i \neq B_i

\left(A_i, B_i\right) \neq \left(A_j, B_j\right) (if i \neq j)

\left(A_i, B_i\right) \neq \left(B_j, A_j\right) (if i \neq j)

1 \leq C_i \leq 10^9

1 \leq Q \leq N\left(N-1\right)

1 \leq s_i, t_i \leq N

s_i \neq t_i

\left(s_i, t_i\right) \neq \left(s_j, t_j\right) (if i \neq j)

Input

Input is given from Standard Input in the following format:

N M L
A_1 B_1 C_1
:
A_M B_M C_M
Q
s_1 t_1
:
s_Q t_Q

Output

Print Q lines.

The i-th line should contain the minimum number of times the tank needs to be fulled while traveling from Town s_i to Town t_i. If Town t_i is unreachable, the line should contain -1 instead.

Sample Input 1

3 2 5
1 2 3
2 3 3
2
3 2
1 3

Sample Output 1

0
1

To travel from Town 3 to Town 2, we can use the second road to reach Town 2 without fueling the tank on the way.

To travel from Town 1 to Town 3, we can first use the first road to get to Town 2, full the tank, and use the second road to reach Town 3.

Sample Input 2

4 0 1
1
2 1

Sample Output 2

-1

There may be no road at all.

Sample Input 3

5 4 4
1 2 2
2 3 2
3 4 3
4 5 2
20
2 1
3 1
4 1
5 1
1 2
3 2
4 2
5 2
1 3
2 3
4 3
5 3
1 4
2 4
3 4
5 4
1 5
2 5
3 5
4 5

Sample Output 3

0
0
1
2
0
0
1
2
0
0
0
1
1
1
0
0
2
2
1
0



Sample input:
3 2 5
1 2 3
2 3 3
2
3 2
1 3


Sample output:
0
1

Submission status: Runtime Error

Solution code:
N, M, L = map(int, input().split())
ABC = [list(map(int, input().split())) for _ in range(M)]
Q = int(input())
st = [list(map(int, input().split())) for _ in range(Q)]

inf = 10 ** 9 + 7

graph = [[] for _ in range(N)]
tab   = [[inf] * N for _ in range(N)]
for Ai, Bi, Ci in ABC:
    if Ci > L: continue
    #
    graph[Ai - 1].append((Bi, Ci))
    graph[Bi - 1].append((Ai, Ci))
    tab[Ai - 1][Bi - 1] = Ci
    tab[Bi - 1][Ai - 1] = Ci

import heapq

tab_p = [None] * N
tab_d = [None] * N

for start in range(N):
    q = [(0, start + 1)]
    d = [(0 if i == start else inf) for i in range(N)]
    p = [None] * N
    while len(q) > 0:
        dist, src = heapq.heappop(q)
        for dst, cost in graph[src - 1]:
            dist_tmp = dist + cost
            if d[dst - 1] > dist_tmp:
                d[dst - 1] = dist_tmp
                p[dst - 1] = src
                heapq.heappush(q, (dist_tmp, dst))
    #
    tab_p[start] = p
    tab_d[start] = d
    # print("#", start, p)
    
for i, (si, ti) in enumerate(st):
    if tab_d[si - 1][ti - 1] == inf:
        print(-1)
        continue
    else:
        ans = 0
        src, penalty = ti, 0
        # print("##", (si, ti), tab_p[si - 1])
        while True:
            # print("##", src, penalty)
            if penalty > L:
                penalty -= L
                ans += 1
            if src == si: break
            #
            dst = tab_p[si - 1][dst - 1]
            penalty += tab[dst - 1][src - 1]
            src = dst
        #
        print(ans)

Submission status: Runtime Error

Solution code:
from scipy.sparse.csgraph import csgraph_from_dense,floyd_warshall

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

A=[[10**12 for i in range(N+1)]for j in range(N+1)]
B=[[10**12 for i in range(N+1)]for j in range(N+1)]
for i in range(M):
    a,b,c=map(int,input().split())
    if c<=L:
        A[a][b]=c
        A[b][a]=c
        B[a][b]=1
        B[b][a]=1

#print(A)

AG = csgraph_from_dense(A)
A=d = floyd_warshall(AG,directed = False)
#print(A)
for i in range(N+1):
    for j in range(N+1):
        if A[i][j]<=L:
            B[i][j]=1
"""for c in range(1,N+1):
    for a in range(1,N+1):
        for b in range(1,N+1):
            A[a][b]=min(A[a][b],A[a][c]+A[c][b])
            if A[a][b]<=L:
                B[a][b]=1"""
#print(B)
BG=csgraph_from_dense(B)
B=d = floyd_warshall(BG,directed = False)
"""for c in range(1,N+1):
    for a in range(1,N+1):
        for b in range(1,N+1):
            B[a][b]=min(B[a][b],B[a][c]+B[c][b])"""

#print(B)
Q=int(input())
for i in range(Q):
    s,t=map(int,input().split())
    if B[s][t]==10**12:
        print(-1)
    else:
        print(int(B[s][t]-1))

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
import itertools
import heapq


class Node(object):

  def __init__(self, idx):
    self.idx = idx
    self.fixed = False
    self.supply = 300
    self.remain = 0
    self.edges = []

  def __gt__(self, obj):
    return self.supply > obj.supply or self.remain < obj.supply

  def __lt__(self, obj):
    return self.supply < obj.supply or self.remain > obj.supply

  def __hash__(self):
    return self.idx

  def __str__(self):
    return (f'{self.idx}: {self.supply}/{self.remain} - ' +
            ','.join(f'{e.idx}({d})' for e, d in self.edges))


def main():
  n, m, tank = map(int, input().split())
  nodes = [Node(i) for i in range(n + 1)]

  for _ in range(m):
    a, b, c = map(int, input().split())
    nodes[a - 1].edges.append((nodes[b - 1], c))
    nodes[b - 1].edges.append((nodes[a - 1], c))

  queries = [list(map(int, input().split())) for _ in range(int(input()))]
  results = [[None] * len(nodes) for _ in range(len(nodes) - 1)]

  for start in range(len(nodes) - 1):
    for n in nodes:
      n.fixed = False
      n.supply = 300
      n.remain = 0

    nodes[start].supply = 0
    nodes[start].remain = tank

    while True:
      node = min([n for n in nodes if not n.fixed], key=lambda n: (n.supply, -n.remain))
      node.fixed = True

      if node.idx == len(nodes) - 1:
        break

      for e, d in node.edges:
        if e.fixed or d > tank:
          continue

        if d > node.remain:
          remain = tank - d
          supply = node.supply + 1
        else:
          remain = node.remain - d
          supply = node.supply

        if e.supply > supply or e.remain < remain:
          e.supply = supply
          e.remain = remain

    for end in range(len(nodes)):
      results[start][end] = nodes[end].supply

  for start, end in queries:
    print(results[start - 1][end - 1])


if __name__ == '__main__':
  main()

Submission status: Runtime Error

Solution code:
from bisect import bisect_left

n = int(input())
a = sorted(map(int, input().split()))
print(sum(bisect_left(a, a[i] + a[j]) - i - 1
          for i in range(1, n - 1) for j in range(i)))

Submission status: Runtime Error

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


def main():
    mod = 10**10
    N, M, L = map(int, input().split())
    dist = [[float('inf') for _ in range(N+1)] for _ in range(N+1)]
    ans = [[float('inf') for _ in range(N+1)] for _ in range(N+1)]
    for i in range(1, N+1):
        dist[i][i] = 0
        ans[i][i] = 0
    for _ in range(M):
        a, b, c = map(int, input().split())
        if c <= L:
            dist[a][b] = c
            dist[b][a] = c

    for i in range(1, N+1):
        for j in range(1, N+1):
            for k in range(1, N+1):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    for i in range(1, N+1):
        for j in range(N+1):
            if dist[i][j] <= L and i != j:
                ans[i][j] = 1
    for i in range(1, N+1):
        for j in range(1, N+1):
            for k in range(1, N+1):
                ans[i][j] = min(ans[i][j], ans[i][k] + ans[k][j])

    Q = int(input())
    for _ in range(Q):
        s, t = map(int, input().split())
        print(ans[s][t]-1) if ans[s][t] < 10**10 else print(-1)


if __name__ == '__main__':
    main()
import sys
input = sys.stdin.buffer.readline


def main():
    mod = 10**10
    N, M, L = map(int, input().split())
    dist = [[float('inf') for _ in range(N+1)] for _ in range(N+1)]
    ans = [[float('inf') for _ in range(N+1)] for _ in range(N+1)]
    for i in range(1, N+1):
        dist[i][i] = 0
        ans[i][i] = 0
    for _ in range(M):
        a, b, c = map(int, input().split())
        if c <= L:
            dist[a][b] = c
            dist[b][a] = c

    for i in range(1, N+1):
        for j in range(1, N+1):
            for k in range(1, N+1):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    for i in range(1, N+1):
        for j in range(N+1):
            if dist[i][j] <= L and i != j:
                ans[i][j] = 1
    for i in range(1, N+1):
        for j in range(1, N+1):
            for k in range(1, N+1):
                ans[i][j] = min(ans[i][j], ans[i][k] + ans[k][j])

    Q = int(input())
    for _ in range(Q):
        s, t = map(int, input().split())
        print(ans[s][t]-1) if ans[s][t] < 10**10 else print(-1)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from scipy.sparse.csgraph import csgraph_from_dense,floyd_warshall

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

A=[[10**12 for i in range(N+1)]for j in range(N+1)]
B=[[10**12 for i in range(N+1)]for j in range(N+1)]
for i in range(M):
    a,b,c=map(int,input().split())
    if c<=L:
        A[a][b]=c
        A[b][a]=c
        B[a][b]=1
        B[b][a]=1

#print(A)

AG = csgraph_from_dense(A)
A=floyd_warshall(AG)
#print(A)
for i in range(N+1):
    for j in range(N+1):
        if A[i][j]<=L:
            B[i][j]=1
"""for c in range(1,N+1):
    for a in range(1,N+1):
        for b in range(1,N+1):
            A[a][b]=min(A[a][b],A[a][c]+A[c][b])
            if A[a][b]<=L:
                B[a][b]=1"""
#print(B)
BG=csgraph_from_dense(B)
B=floyd_warshall(BG)
"""for c in range(1,N+1):
    for a in range(1,N+1):
        for b in range(1,N+1):
            B[a][b]=min(B[a][b],B[a][c]+B[c][b])"""

#print(B)
Q=int(input())
for i in range(Q):
    s,t=map(int,input().split())
    if B[s][t]==10**12:
        print(-1)
    else:
        print(int(B[s][t]-1))

Submission status: Runtime Error

Solution code:
from bisect import bisect_left

n = int(input())
a = sorted(map(int, input().split()))
print(sum(bisect_left(a, a[i] + a[j], i + 1) - i - 1
          for i in range(1, n - 1) for j in range(i)))

Submission status: Runtime Error

Solution code:
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools

import queue
from collections import deque



def main():
    node_num, edge_num, max_tank = map(int, input().split())
    data = [list(map(int, input().split())) for i in range(edge_num)]
    q_num = int(input())
    query = [list(map(int, input().split())) for i in range(q_num)]

    graph_data = defaultdict(set)
    dist_data = defaultdict(int)

    for i in range(edge_num):
        a, b, c = data[i]
        graph_data[a].add(b)
        graph_data[b].add(a)
        dist_data[(a, b)] = c
        dist_data[(b, a)] = c

    ans_list = [[-1 for i in range(node_num + 1)] for j in range(node_num + 1)]

    for i in range(1, node_num + 1):
        ans_list[i][i] = (0, max_tank)

        count_all = node_num - 1

        check_ele = set()
        check_ele.add(i)
        for j in range(1, i):
            count_all -= 1
            ans_list[i][j] = ans_list[j][i]
            check_ele.add(j)
        aaa = []

        for bbb in check_ele:
            for next_ele in graph_data[bbb]:
                if ans_list[i][next_ele] != -1:
                    continue

                # print(ans_list[i][next_ele])
                count_data, nokori_data = ans_list[i][bbb]
                dist = dist_data[(bbb, next_ele)]
                if dist > max_tank:
                    continue
                if dist <= nokori_data:
                    heapq.heappush(aaa, (count_data, - (nokori_data - dist), next_ele))
                else:
                    heapq.heappush(aaa, (count_data + 1, - (max_tank - dist), next_ele))

        while len(aaa):
            count, nokori, now_ele = heapq.heappop(aaa)

            if ans_list[i][now_ele] != -1:
                continue

            nokori = -1 * nokori
            ans_list[i][now_ele] = (count, nokori)
            count_all -= 1

            if count_all == 0:
                break

            for next_ele in graph_data[now_ele]:
                if ans_list[i][next_ele] != -1:
                    continue
                dist = dist_data[(now_ele, next_ele)]
                if dist > max_tank:
                    continue
                if nokori < dist:
                    heapq.heappush(aaa, (count + 1, - (max_tank - dist), next_ele))
                else:
                    heapq.heappush(aaa, (count, - (nokori - dist), next_ele))

            for lll in range(1, node_num + 1):
                if ans_list[i][lll] == -1:
                    break
            else:
                break


    for i in range(q_num):
        s, t = query[i]
        ans = ans_list[s][t]
        if ans == -1:
            print(-1)
        else:
            print(ans[0])


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import numpy as np
import math
import itertools
import networkx as nx

s = input().split()
n=int(s[0])
m=int(s[1])
l = int(s[2])
g = nx.Graph()
s = input().split()
if len(s)==3:
    for i in range(m):
        g.add_weighted_edges_from([(s[0], s[1], s[2])], weight='weight')
        s = input().split()
    q=int(s[0])
    for i in range(q):
        sum=l
        count=0
        s = input().split()
        keiro=nx.shortest_path(g, source=s[0], target=s[1])
        for k in range(len(keiro)-1):
            if int(g.edges[keiro[k],keiro[k+1]]['weight'])>l:
                print(-1)
                break
            if sum < int(g.edges[keiro[k], keiro[k+1]]['weight']):
                sum=l
                count+=1
            sum -= int(g.edges[keiro[k], keiro[k+1]]['weight'])

        print(count)
else:
    print(-1)

Submission status: Runtime Error

Solution code:
from bisect import bisect_left

n = int(input())
a = sorted(map(int, input().split()))
print(sum(bisect_left(a, a[i] + a[j], i + 1) - i - 1
          for i in range(2, n) for j in range(i)))

Submission status: Runtime Error

Solution code:
import numpy as np
import math
import itertools
import networkx as nx
import matplotlib.pyplot as plt
# 文字列
# s = input()

# 複数
s = input().split()
n=int(s[0])
m=int(s[1])
l = int(s[2])
g = nx.Graph()
s = input().split()
if len(s)==3:
    for i in range(m):
        g.add_weighted_edges_from([(s[0], s[1], s[2])], weight='weight')
        s = input().split()
    q=int(s[0])
    for i in range(q):
        sum=l
        count=0
        s = input().split()
        keiro=nx.shortest_path(g, source=s[0], target=s[1])
        for k in range(len(keiro)-1):
            if int(g.edges[keiro[k],keiro[k+1]]['weight'])>l:
                print(-1)
                break
            if sum < int(g.edges[keiro[k], keiro[k+1]]['weight']):
                sum=l
                count+=1
            sum -= int(g.edges[keiro[k], keiro[k+1]]['weight'])

        print(count)
else:
    print(-1)

Submission status: Runtime Error

Solution code:
import math
import sys

n, m, l = map(int, input().split())
path = [[] for _ in range(n)]
for _ in range(m):
    a, b, c = map(int, input().split())
    path[a - 1].append((b - 1, c))
    path[b - 1].append((a - 1, c))
q = int(input())


def dfs(a, b, root, tank, count):
    if root[a]:
        return -1
    if a == b:
        return count
    root[a] = True
    buf = math.inf
    for t, c in path[a]:
        if tank < c:
            if c < l:
                ret = dfs(t, b, root, l - c, count + 1)
            else:
                ret = -1
        else:
            ret = dfs(t, b, root, tank - c, count)
        if ret != -1:
            buf = min(buf, ret)
    root[a] = False
    if math.isinf(buf):
        return -1
    else:
        return buf


for _ in range(q):
    s,t=map(int,input().split())
    s, t = s - 1, t - 1
    print(dfs(s, t, [False for _ in range(n)], l, 0),flush=True)

Submission status: Runtime Error

Solution code:
import numpy as np
from scipy.sparse.csgraph import floyd_warshall
import sys
input = sys.stdin.readline

def main():
    INF = float("Inf")
    n,m,l = map(int, input().split())
    G = [[INF]*n for i in range(n)]
    for i in range(n):
        G[i][i] = 0
    for i in range(m):
        a,b,c = map(int, input().split())
        a,b = a-1,b-1
        if c <= l:
            G[a][b] = G[b][a] = c
    G = floyd_warshall(G, directed=False)
    G = np.where(G <=l, 1, INF)
    for i in range(n):
        G[i][i] = 0
    GG = floyd_warshall(G, directed=False)

    q = int(input())
    ans = []
    for i in range(q):
        s,t = map(int, input().split())
        a = int(GG[s-1][t-1])
        if a == INF:
            a = 0
        ans.append(a-1)
    print(*ans, sep="\n")

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import math

n, m, l = map(int, input().split())
path = [[] for _ in range(n)]
for _ in range(m):
    a, b, c = map(int, input().split())
    path[a - 1].append((b - 1, c))
    path[b - 1].append((a - 1, c))
q = int(input())
que = [map(int, input().split()) for _ in range(q)]


def dfs(a, b, root, tank, count):
    if root[a]:
        return -1
    if a == b:
        return count
    root[a] = True
    buf = math.inf
    for t, c in path[a]:
        if tank < c:
            if c < l:
                ret = dfs(t, b, root, l - c, count + 1)
            else:
                ret = -1
        else:
            ret = dfs(t, b, root, tank - c, count)
        if ret != -1:
            buf = min(buf, ret)
    root[a] = False
    if math.isinf(buf):
        return -1
    else:
        return buf


for s,t in que:
    s, t = s - 1, t - 1
    print(dfs(s, t, [False for _ in range(n)], l, 0))

Submission status: Runtime Error

Solution code:
from heapq import heappush, heappop
input = sys.stdin.readline
def inpl(): return list(map(int, input().split()))

N, M, L = inpl()
G = [[] for _ in range(N)]
G2 = [[999]*(N) for _ in range(N)]

for _ in range(M):
    a, b, c = inpl()
    if c <= L:
        G[a-1].append([b-1, c])
        G[b-1].append([a-1, c])

for i in range(N):
    supply = [999]*N
    remain = [0]*N
    supply[i] = 1
    remain[i] = L
    Q = [(1, -L, i)]
    while Q:
        s, r, p = heappop(Q)
        r = -r
        if s > supply[p]:
            continue
        if (s == supply[p]) and (r < remain[p]):
            continue
        for q, c in G[p]:
            if r >= c:
                if supply[q] > s:
                    supply[q] = s
                    remain[q] = r - c
                    heappush(Q, (s, c-r, q))
                elif (supply[q] == s) & (remain[q] < r - c):
                    remain[q] = r-c
                    heappush(Q, (s, c-r, q))
            else:
                if supply[q] > s:
                    supply[q] = s + 1
                    remain[q] = L - c
                    heappush(Q, (s+1, c-L, q))
                elif (supply[q] == (s+1)) & (remain[q] < L - c):
                    supply[q] = s+1
                    remain[q] = L-c
                    heappush(Q, (s+1, c-L, q))
    for j in range(N):
        G2[i][j] = supply[j]


for _ in range(int(input())):
    s, t = inpl()
    if G2[s-1][t-1] == 999:
        print(-1)
    else:
        print(G2[s-1][t-1]-1)

Submission status: Runtime Error

Solution code:
import heapq
n,m,l=map(int,input().split())
edge=[[] for i in range(n)]
for i in range(m):
  a,b,c=map(int,input().split())
  edge[a-1].append([c,b-1])
  edge[b-1].append([c,a-1])

def f(s):
  d=[float("inf")]*n
  used=[True]*n
  d[s]=0
  used[s]=False
  edgelist=[]
  ans=0
  cur=l
  for c,e in edge[s]:
    heapq.heappush(edgelist,c*10**3+e)
  while edgelist:
    minedge=heapq.heappop(edgelist)
    v=minedge[0]%(10**3)
    ans,cur=minedge[0]//(10**13),(minedge[0]%(10**13))//(10**3)
    used[v]=False
    d[v]=ans
    
    for e in edge[v]:
      if used[e[1]]:
        if e[0]>l:
          continue
        elif e[0]+cur>l:
          heapq.heappush(edgelist,(ans+1)*10**13+e[0]*10**3+e[1])
        else:
          heapq.heappush(edgelist,(ans)*10**13+(e[0]+cur)*10**3+e[1])
  return d
Ans=[[] for i in range(n)]
for i in range(n):
  Ans[i]=f(i)
q=int(input())
for _ in range(q):
  s,t=map(int,input().split())
  print(-1 if Ans[s-1][t-1]==float("inf") else Ans[s-1][t-1])

Submission status: Runtime Error

Solution code:
from scipy.sparse.csgraph import shortest_path
from scipy.sparse import csr_matrix

def get_path(start, goal, pred):
  return get_path_row(start, goal, pred[start])

def get_path_row(start, goal, pred_row):
  path = []
  i = goal
  while i != start and i >= 0:
    path.append(i)
    i = pred_row[i]
  if i < 0:
    return []
  path.append(i)
  return path[::-1]

N,M,L = map(int,input().split())
if M != 0:
  G = [[0 for _ in range(N)] for _ in range(N)]
  for i in range(M):
    A,B,C = map(int,input().split())
    A -= 1
    B -= 1
    if C <= L:
      G[A][B] = C
      G[B][A] = C
      csr = csr_matrix(G)
    #print(csr)
  d, p = shortest_path(csr, return_predecessors=True)
  #print(d)
  #print(p)

Q = int(input())
for i in range(Q):
  if M == 0:
    print(-1)
    break
  s,t = map(int,input().split())
  s -= 1
  t -= 1
  path = get_path(s,t,p)
  if len(path) == 0:
    print(-1)
  else:
    ans = 0
    tank = L
    for j in range(len(path)-1):
      if tank - G[path[j]][path[j+1]] < 0:
        ans +=1
        tank = L
      tank -= G[path[j]][path[j+1]]
    print(ans)

Submission status: Runtime Error

Solution code:
import math

n, m, l = map(int, input().split())
path = [[] for _ in range(n)]
for _ in range(m):
    a, b, c = map(int, input().split())
    path[a - 1].append((b - 1, c))
    path[b - 1].append((a - 1, c))
q = int(input())


def dfs(a, b, root, tank, count):
    if root[a]:
        return -1
    if a == b:
        return count
    root[a] = True
    buf = math.inf
    for t, c in path[a]:
        if tank < c:
            if c < l:
                ret = dfs(t, b, root, l - c, count + 1)
            else:
                ret = -1
        else:
            ret = dfs(t, b, root, tank - c, count)
        if ret != -1:
            buf = min(buf, ret)
    root[a] = False
    if math.isinf(buf):
        return -1
    else:
        return buf


for i in range(q):
    s, t = map(int, input().split())
    s, t = s - 1, t - 1
    print(dfs(s, t, [False for _ in range(n)], l, 0))

Submission status: Runtime Error

Solution code:
from scipy.sparse.csgraph import shortest_path
from scipy.sparse import csr_matrix

def get_path(start, goal, pred):
  return get_path_row(start, goal, pred[start])

def get_path_row(start, goal, pred_row):
  path = []
  i = goal
  while i != start and i >= 0:
    path.append(i)
    i = pred_row[i]
  if i < 0:
    return []
  path.append(i)
  return path[::-1]

N,M,L = map(int,input().split())
if M != 0:
  G = [[0 for _ in range(N)] for _ in range(N)]
  for i in range(M):
    A,B,C = map(int,input().split())
    A -= 1
    B -= 1
    if C <= L:
      G[A][B] = C
      G[B][A] = C
      csr = csr_matrix(G)
    #print(csr)
  d, p = shortest_path(csr, return_predecessors=True)
  #print(d)
  #print(p)

Q = int(input())
for i in range(Q):
  if M == 0:
    print(-1)
    break
  s,t = map(int,input().split())
  s -= 1
  t -= 1
  path = get_path(s,t,p)
  if len(path) == 0:
    print(-1)
  else:
    ans = 0
    tank = L
    for i in range(len(path)-1):
      if tank - G[path[i]][path[i+1]] < 0:
        ans +=1
        tank = L
      tank -= G[path[i]][path[i+1]]
    print(ans)

Submission status: Runtime Error

Solution code:
n,m,l = map(int,input().split())
A = [list(map(int,input().split())) for i in range(m)]
q = int(input())
S = [list(map(int,input().split())) for i in range(q)]

for i in range(m):
    for j in range(2):
        A[i][j] -= 1
for i in range(q):
    for j in range(2):
        S[i][j] -= 1

B = []
for i in range(m):
    if A[i][2] <= l:
        B.append([A[i][0],A[i][1],A[i][2]])

A = B

# print(S)

M = [[float("inf")] * n for i in range(n)]
for i in range(n):
    M[i][i] = 0
for i in range(m):
    # print(S[i])
    M[A[i][0]][A[i][1]] = A[i][2]
    M[A[i][1]][A[i][0]] = A[i][2]

H = [[0]*n for i in range(n)]
for i in range(n):
    for j in range(n):
        H[i][j] = M[i][j]

N = [[i for i in range(n)] for j in range(n)]

# print(N)

for k in range(n):
    for i in range(n):
        for j in range(n):
            if M[i][j] > M[i][k]+M[k][j]:
                M[i][j] = M[i][k]+M[k][j]
                N[i][j] = N[i][k]

# print(N,M)
def e(i):
    a = S[i][0]
    b = S[i][1]
    c = l
    ans = 0
    end = 0
    while end == 0:
        # print(i,l)
        ne = N[a][b]
        if c < H[a][ne]:
            ans += 1
            c = l
        c -= H[a][ne]
        if c < 0:
            return -1
        if ne == b:
            end = 1
        a = ne
    return ans

for i in range(q):
    print(e(i))

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-


class Node(object):

  def __init__(self, idx):
    self.idx = idx
    self.supply = 300
    self.remain = 0
    self.edges = []

  def __hash__(self):
    return self.idx


def main():
  n, m, tank = map(int, input().split())
  nodes = [Node(i) for i in range(n)]
  results = []

  for _ in range(m):
    a, b, c = map(int, input().split())
    nodes[a - 1].edges.append((nodes[b - 1], c))
    nodes[b - 1].edges.append((nodes[a - 1], c))

  for _ in range(int(input())):
    start, end = map(int, input().split())
    start -= 1
    end -= 1

    for n in nodes:
      n.supply = 300
      n.remain = 0

    result = -1
    nodes[start].supply = 0
    nodes[start].remain = tank
    currents = set([nodes[start]])

    while len(currents) != 0:
      n = min(currents)
      currents.remove(n)

      if n.idx == end:
        result = n.supply
        break

      for e, d in n.edges:
        if d > tank:
          continue
        elif d > n.remain:
          remain = tank - d
          supply = n.supply + 1
        else:
          remain = n.remain - d
          supply = n.supply

        if e.supply > supply or n.remain < remain:
          e.supply = supply
          e.remain = remain
          currents.add(e)

    results.append(result)

  for r in results:
    print(r)


if __name__ == '__main__':
  main()

Submission status: Runtime Error

Solution code:
import sys

def solve():
	input=sys.stdin.readline
	n, m, l = map(int, input().split())
	edge = [[] for _ in range(n)]
	for _ in range(m):
		a, b, c = map(int, input().split())
		if c <= l:
			edge[a-1].append((c, b-1))
			edge[b-1].append((c, a-1))
	inf = 10 ** 20
	dist = [[inf for _ in range(n)]for i in range(n)]
	for i in range(n):
		dist[i][i]=0
		for c, b in edge[i]:
			dist[i][b]=c
			
	for k in range(n):
		for i in range(n):
			for j in range(n):
				dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])
				
	dist2 = [[n+50 for j in range(n)] for i in range(n)]
	for i in range(n):
		dist2[i][i] = 0
		for j in range(i+1, n):
			if dist[i][j] <= l:
				dist2[i][j] = 1
				dist2[j][i] = 1
	for k in range(n):
		for i in range(n):
			for j in range(n):
				dist2[i][j] = min(dist2[i][k] + dist2[k][j])
	q = int(input())		
	for i in range(q):
		s, t = map(int, input().split())
		print(dist2[s-1][t-1] - 1)
	return 0
	
if __name__ == '__main__':
	solve()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-


class Node(object):

  def __init__(self, idx):
    self.idx = idx
    self.supply = 300
    self.remain = 0
    self.edges = []

  def __eq__(self, obj):
    return self.supply == obj.supply and self.remain == obj.remain

  def __gt__(self, obj):
    return self.supply > obj.supply or self.remain < obj.remain

  def __hash__(self):
    return self.idx

  def __str__(self):
    return (f'{self.idx}: {self.supply}/{self.remain} - '
            +','.join(f'{v.idx}({d})' for v, d in self.edges))


def main():
  n, m, tank = map(int, input().split())
  nodes = [Node(i) for i in range(n)]
  results = []

  for _ in range(m):
    a, b, c = map(int, input().split())
    nodes[a - 1].edges.append((nodes[b - 1], c))
    nodes[b - 1].edges.append((nodes[a - 1], c))

  for _ in range(int(input())):
    start, end = map(int, input().split())
    start -= 1
    end -= 1

    for n in nodes:
      n.supply = 300
      n.remain = 0

    result = -1
    nodes[start].supply = 0
    nodes[start].remain = tank
    currents = set([nodes[start]])

    while len(currents) != 0:
      n = min(currents)
      currents.remove(n)

      if n.idx == end:
        result = n.supply
        break

      for e, d in n.edges:
        if d > tank:
          continue
        elif d > n.remain:
          remain = tank - d
          supply = n.supply + 1
        else:
          remain = n.remain - d
          supply = n.supply

        if e.supply > supply or n.remain < remain:
          e.supply = supply
          e.remain = remain
          currents.add(e)

    results.append(result)

  for r in results:
    print(r)


if __name__ == '__main__':
  main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
import heapq


class Node(object):

  def __init__(self, idx):
    self.idx = idx
    self.supply = 300
    self.remain = 0
    self.edges = []

  def __eq__(self, obj):
    return self.supply == obj.supply and self.remain == obj.remain

  def __gt__(self, obj):
    return self.supply > obj.supply or self.remain < obj.remain

  def __hash__(self):
    return self.idx

  def __str__(self):
    return (f'{self.idx}: {self.supply}/{self.remain} - '
            +','.join(f'{v.idx}({d})' for v, d in self.edges))


def main():
  n, m, tank = map(int, input().split())
  nodes = [Node(i) for i in range(n)]
  results = []

  for _ in range(m):
    a, b, c = map(int, input().split())
    nodes[a - 1].edges.append((nodes[b - 1], c))
    nodes[b - 1].edges.append((nodes[a - 1], c))

  for _ in range(int(input())):
    start, end = map(int, input().split())
    start -= 1
    end -= 1

    for n in nodes:
      n.supply = 300
      n.remain = 0

    result = -1
    nodes[start].supply = 0
    nodes[start].remain = tank
    currents = set([nodes[start]])

    while len(currents) != 0:
      n = min(currents)
      currents.remove(n)

      if n.idx == end:
        result = n.supply
        break

      for e, d in n.edges:
        if d > tank:
          continue
        elif d > n.remain:
          remain = tank - d
          supply = n.supply + 1
        else:
          remain = n.remain - d
          supply = n.supply

        if e.supply > supply or n.remain < remain:
          e.supply = supply
          e.remain = remain
          currents.add(e)

    results.append(result)

  for r in results:
    print(r)


if __name__ == '__main__':
  main()