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:
# -*- coding: utf-8 -*-
"""
Created on Thu Oct 24 23:58:46 2019

@author: Tomomasa Takahashi
"""

class Digraph():
    """
    Directed weighted graph.
    
    edges is a dictionary mapping each node to a edges starting from it
        key: node; value: dictionary of edges starting from that node
            value dictionary: key: end node of edge, value: weight (cost) of the edge
    """
    def __init__(self, adj_list=None):
        """
        Initialize either empty graph or one from a dictionary adjacency list
        """
        self.edges = {}
        self.num_edges = 0
        if isinstance(adj_list, dict):
            for src, values in adj_list.items():
                for dest, weight in values.items():
                    self.add_edge(src, dest, weight)
    
    def add_node(self,node):
        # Adds a vertex to graph (based on key value)       
        self.edges[node] = dict()

    def add_edge(self,src,dest,weight):
        # Adds the (v,w) edge, making sure the two nodes exist
        if not self.has_node(src): 
            self.add_node(src)
        if not self.has_node(dest): 
            self.add_node(dest)
        if not self.has_edge(src, dest):
            self.num_edges += 1
            self.edges[src][dest] = weight
  
    def children_of(self, v):
        # Returns a node's children
        return self.edges[v].items()
    
    def get_nodes(self):
        # Returns a node's children
        return self.edges.keys()
        
    def has_node(self, v):
        # Checks if node exists
        return v in self.edges
        
    def has_edge(self, v, w):
        # Checks if edge exists
        return w in self.edges[v]

    def list_edges(self):
        # Creates list of edges
        ll = []
        for src,values in self.edges.items():
            for dest,weight in values.items():
                ll.append([src,dest,weight])
        return ll
    
    def __str__(self):
        # Returns a string representation of the graph
        result = ''
        for src in self.edges:
            for dest,weight in self.edges[src].items():
                result = result + src + '->'\
                         + dest + ', length ' + str(weight) + '\n'
        return result[:-1] # omit final newline
    
    def connected(self, start):
        visited = set()
        to_visit=[start]
        while len(to_visit)>0:
            current = to_visit.pop(0)
            visited.add(current)
            for node, weight in self.children_of(current):
                if not node in visited:
                    to_visit.append(node)
        return visited

    
    def shortest_path(self, start):
        # Visited nodes X initially empty  
        X = set()
        X.add(start)
        # Previous nodes
        prev_nodes = {start:None}
        # Shortest distances to all nodes from s
        A = dict() 
        for node in self.get_nodes(): 
            A[node] = float('Inf') # initialize to "infinity"           
        A[start] = 0 # distance zero to itself
        # Main loop
        connected_nodes = self.connected(start)
        # Loop while we haven't visited all nodes
        while len(X) < len(connected_nodes):              
            # Store mininimum edge and distance when looping
            min_edge = [] # list [src, dest, weight]
            min_dist = float('inf')
            # Loop through all edges starting in X and not ending in X
            # Find minimum Dijksta score
            for src in X:
                for dest, weight in self.children_of(src): # edges starting from src
                    if dest not in X: # edge not ending in X
                        # Update minimum-Dijkstra-score edge if find one
                        if A[src] + weight < min_dist: 
                            min_edge = [src, dest, weight] 
                            min_dist = A[src] + weight
                            prev_nodes[dest] = src
            # Update A[min_e_dest] = A[min_e_source] + A[min_e_weight]        
            A[min_edge[1]] = A[min_edge[0]] + min_edge[2]
            # Add destination node from min edge to visited nodes
            X.add(min_edge[1])  
        return A, prev_nodes

class Graph(Digraph):
    """ 
    Undirected graph: two one-way edges for every edge
    """
    def add_edge(self, src, dest,weight):
        Digraph.add_edge(self, src, dest, weight)
        Digraph.add_edge(self, dest, src, weight)
        
N,M,L = map(int, input().split())
graph_1 = Graph()
for i in range(N):
    graph_1.add_node(i+1)
for i in range(M):
    src,dest,weight = map(int, input().split())
    graph_1.add_edge(src,dest,weight)
    
graph_2 = Graph()

for src in range(1,N+1):
    short_dict, prev_nodes = graph_1.shortest_path(src)
    for elem in short_dict:
        if elem != src and short_dict[elem]<=L:
            graph_2.add_edge(src, elem, 1)
            
Q=int(input())
for i in range(Q):
    src, dest = map(int, input().split())
    connected_nodes = graph_1.connected(src)
    if dest in connected_nodes:
        short_dict, prev_nodes = graph_2.shortest_path(src)
        print(short_dict[dest]-1)
    else:
        print(-1)

Submission status: Runtime Error

Solution code:
import numpy as np
import sys
input = sys.stdin.readline

def floyd(cost,n):
    for i in range(n):
        for j in range(n):
            for k in range(n):
                new = min(cost[i][j], cost[i][k] + cost[k][j])
                cost[i][j] = new
                cost[j][i] = new

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,n)
    G = np.where(G <=l, 1, INF)
    for i in range(n):
        G[i][i] = 0
    GG = floyd_warshall(G,n)

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

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import numpy as np
import sys
input = sys.stdin.readline

def floyd(cost):
    for i in range(n):
        for j in range(n):
            for k in range(n):
                new = min(cost[i][j], cost[i][k] + cost[k][j])
                cost[i][j] = new
                cost[j][i] = new

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)
    G = np.where(G <=l, 1, INF)
    for i in range(n):
        G[i][i] = 0
    GG = floyd_warshall(G)

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

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from scipy.sparse.csgraph import johnson
import sys
input = sys.stdin.readline

def solve():
  minf = -1*float("inf")
  n,m,l = (int(i) for i in input().split())
  path = [[minf]*n for _ in range(n)]
  for i in range(m):
    a,b,c = (int(i) for i in input().split())
    path[a-1][b-1] = c
  d = johnson(path,directed=False)
  q = int(input())
  
  minipath = [[None]*n for _ in range(n)]
  for i in range(n):
    for j in range(n):
      if d[i][j] <= l:
        minipath[i][j] = 1
      else:
        minipath[i][j] = minf
  d2 = johnson(minipath,directed=False)

  for i in range(q):
    s,t = (int(i) for i in input().split())
    s,t = s-1,t-1
    cost = d2[s][t]
    if cost == minf:
      print(-1)
    else:
      print(int(cost)-1)

solve()

Submission status: Runtime Error

Solution code:
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall

n,m,l=map(int,input().split())
ll=[]
for i in range(m):
    a,b,c=[int(j) for j in input().split()]
    if c<=l:
        ll.append((a,b,c))
q=int(input())
st=[]
for i in range(q):
    st.append([int(j)-1 for j in input().split()])
if ll==[]:
    print(-1)
    exit()
edge=np.array(ll,dtype=np.int64).T
graph=csr_matrix(((edge[2],edge[:2]-1)),(n,n))

#False->無向グラフ True->有効グラフ
ans=floyd_warshall(graph,directed=False)

graph2=np.full((n,n),np.inf)

np.fill_diagonal(graph2,0)

graph2[ans<=l]=1


ans2=floyd_warshall(graph2,directed=False)


for i,j in st:
    if int(ans2[i][j])==float("inf"):
        print(-1)
    else:
        print(int(ans2[i][j])-1)

Submission status: Runtime Error

Solution code:
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall

n,m,l=map(int,input().split())
ll=[]
for i in range(m):
    a,b,c=[int(j) for j in input().split()]
    if c<=l:
        ll.append((a,b,c))
if ll==[]:
    print(-1)
    exit()
edge=np.array(ll,dtype=np.int64).T
graph=csr_matrix(((edge[2],edge[:2]-1)),(n,n))

#False->無向グラフ True->有効グラフ
ans=floyd_warshall(graph,directed=False)
v=[]
s=set(list(range(1,n+1)))
for i in range(n):
    for j in range(n):
        if ans[i][j]<=l:
            if i+1 in s:
                s.remove(i+1)
            if j+1 in s:
                s.remove(j+1)
            v.append((i+1,j+1,1))
for i in s:
    v.append((1,i,float("inf")))
edge=np.array(v,dtype=np.int64).T
graph=csr_matrix(((edge[2],edge[:2]-1)),(n,n))
ans2=floyd_warshall(graph,directed=False)

q=int(input())
st=[]
for i in range(q):
    st.append([int(j)-1 for j in input().split()])

for i,j in st:
    if int(ans2[i][j])==float("inf"):
        print(-1)
    else:
        print(int(ans2[i][j])-1)

Submission status: Runtime Error

Solution code:
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall

n,m,l=map(int,input().split())
ll=[]
for i in range(m):
    a,b,c=[int(j) for j in input().split()]
    if c<=l:
        ll.append((a,b,c))
if ll==[]:
    print(-1)
    exit()
edge=np.array(ll,dtype=np.int64).T
graph=csr_matrix(((edge[2],edge[:2]-1)),(n,n))

#False->無向グラフ True->有効グラフ
ans=floyd_warshall(graph,directed=False)
v=[]
for i in range(n):
    for j in range(n):
        if ans[i][j]<=l:
            v.append((i+1,j+1,1))

edge=np.array(v,dtype=np.int64).T
graph=csr_matrix(((edge[2],edge[:2]-1)),(n,n))
ans2=floyd_warshall(graph,directed=False)

q=int(input())
st=[]
for i in range(q):
    st.append([int(j)-1 for j in input().split()])

for i,j in st:
    if int(ans2[i][j])==float("inf"):
        print(-1)
    else:
        print(int(ans2[i][j])-1)

Submission status: Runtime Error

Solution code:
from scipy.sparse.csgraph import csgraph_from_dense
from scipy.sparse.csgraph import floyd_warshall
N,M,L=map(int,input().split())
ABC=[map(int,input().split()) for _ in range(M)]
Q=int(input())
ST=[list(map(int,input().split())) for _ in range(Q)]

E=[[float('inf')]*N for _ in range(N)]
for a,b,c in ABC:
    E[a-1][b-1]=c
    E[b-1][a-1]=c
G = csgraph_from_dense(E, null_value=10**10)
d = floyd_warshall(G)
E=[[1 if __<= L else 10**10 for __ in _] for _ in d]
G = csgraph_from_dense(E, null_value=10**10)
E = floyd_warshall(G)

for s,t in ST:
    if E[s-1][t-1]==float('inf'):
        print(-1)
    else:
        print(int(E[s-1][t-1]-1))

Submission status: Runtime Error

Solution code:
from scipy.sparse.csgraph import csgraph_from_dense
from scipy.sparse.csgraph import floyd_warshall
import numpy as np
N,M,L=map(int,input().split())
ABC=[map(int,input().split()) for _ in range(M)]
Q=int(input())
ST=[list(map(int,input().split())) for _ in range(Q)]

E=[[10**10]*N for _ in range(N)]
for a,b,c in ABC:
    E[a-1][b-1]=c
    E[b-1][a-1]=c
G = csgraph_from_dense(E, null_value=10**10)
d = floyd_warshall(G)
E=[[1 if __<= L else 10**10 for __ in _] for _ in d]
G = csgraph_from_dense(E, null_value=10**10)
E = floyd_warshall(G)

for s,t in ST:
    if np.isinf(E[s-1][t-1]):
        print(-1)
    else:
        print(int(E[s-1][t-1]-1))

Submission status: Runtime Error

Solution code:
from scipy.sparse.csgraph import csgraph_from_dense
from scipy.sparse.csgraph import floyd_warshall
N,M,L=map(int,input().split())
ABC=[map(int,input().split()) for _ in range(M)]
Q=int(input())
ST=[list(map(int,input().split())) for _ in range(Q)]

E=[[10**10]*N for _ in range(N)]
for a,b,c in ABC:
    E[a-1][b-1]=c
    E[b-1][a-1]=c
G = csgraph_from_dense(E, null_value=10**10)
d = floyd_warshall(G)
E=[[1 if __<= L else 10**10 for __ in _] for _ in d]
G = csgraph_from_dense(E, null_value=10**10)
E = floyd_warshall(G)

for s,t in ST:
    if E[s-1][t-1]==float('inf'):
        print(-1)
    else:
        print(int(E[s-1][t-1]-1))

Submission status: Runtime Error

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

# 町間の道の長さのマトリックスを初期値無限で作成
S = [[float("INF") for i in range(N)] for i in range(N)]

# 町間の道の長さ情報をマトリックスに入力
for i in range(M):
    a, b, c = map(int,input().split())
    S[a-1][b-1] = c
    S[b-1][a-1] = c

# ワーシャルフロイド法で最短距離のマップを生成
Sf = fw(S)

T = [[float("INF")for i in range(N)] for i in range(N)]

# 町間を補給なしで通行可能な場合は1、不可能な場合はINFとしてマトリックスを作成
# （町間距離がタンク容量より大きい場合は通行不可）
for i in range(N):
    for j in range(N):
        if Sf[i][j] <= L:
            T[i][j] = 1

# ワーシャルフロイド法で町間移動可否のマップを生成
# すぐ上のfor文で、補給なしで移動できない町間の移動コストはINFにしたが、
# この処理で複数回の補給を行えば移動できる距離を
Tf = fw(T)

for i in range(int(input())):
    a, b = map(int, input().split())
    if Tf[a-1][b-1] != float("INF"):
        print(int(Tf[a-1][b-1])-1)
    else:
        print(-1)

Submission status: Runtime Error

Solution code:
#O(ElogV)
import heapq
def dijkstra_heap(s,g):
    #始点sから各頂点への最短距離
    d = [float("inf")] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        if e[0]<=l:
            heapq.heappush(edgelist,[[0,l-e[0]],e[1]])
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        if v==g:
            return minedge[0][0]
        nl = minedge[0][1]
        kai=minedge[0][0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                if e[0]<=l and e[0]<=nl:
                    heapq.heappush(edgelist,[[kai,nl-e[0]],e[1]])
                elif e[0]<=l:
                    heapq.heappush(edgelist,[[kai+1,l],e[1]])
                    
    return -1

################################
n,w,l = map(int,input().split()) #n:頂点数　w:辺の数

edge = [[] for i in range(n)]
#edge[i] : iから出る道の[重み,行先]の配列
for i in range(w):
    x,y,z = map(int,input().split())
    edge[x].append([z,y])
    edge[y].append([z,x])
q=int(input())
for i in range(q):
    sa,ga=map(int,input().split())
    print(dijkstra_heap(sa-1,ga-1))

Submission status: Runtime Error

Solution code:
#O(ElogV)
import heapq
def dijkstra_heap(s,g):
    #始点sから各頂点への最短距離
    d = [float("inf")] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        if e[0]<=l:
            heapq.heappush(edgelist,[[0,l-e[0]],e[1]])
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        if v==g:
            return minedge[0][0]
        nl = minedge[0][1]
        kai=minedge[0][0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                if e[0]<=l and e[0]<=nl
                    heapq.heappush(edgelist,[[kai,nl-e[0]],e[1]])
                elif e[0]<=l:
                    heapq.heappush(edgelist,[[kai+1,l],e[1]])
                    
    return -1

################################
n,w,l = map(int,input().split()) #n:頂点数　w:辺の数

edge = [[] for i in range(n)]
#edge[i] : iから出る道の[重み,行先]の配列
for i in range(w):
    x,y,z = map(int,input().split())
    edge[x].append([z,y])
    edge[y].append([z,x])
q=int(input())
for i in range(q):
    sa,ga=map(int,input().split())
    print(dijkstra_heap(sa-1,ga-1))

Submission status: Runtime Error

Solution code:
# coding: utf-8
from scipy.sparse.csgraph import floyd_warshall,csgraph_from_dense

MAX=float('inf')
N,M,L=map(int, raw_input().split())
Roads = [[ 0 if i == j else MAX for j in range(N)] for i in range(N)]

for i in range(M):
    f,t,c = map(int, raw_input().split())
    Roads[f-1][t-1] = c
    Roads[t-1][f-1] = c

RG = csgraph_from_dense(Roads, null_value=MAX)
Rd = floyd_warshall(RG)

Fuels = [[ 1 if Rd[i][j] <=L else MAX for j in range(N)] for i in range(N)]

FG = csgraph_from_dense(Fuels, null_value=MAX)
Fd = floyd_warshall(FG)

Q=int(raw_input())
Queries = []
for i in range(Q):
    s, t = map(int, raw_input().split())
    v = Fd[s-1][t-1]
    if s == t:
        print (str(0))
    if v == float('inf'):
        print (str(-1))
    else:
        print (str(int(v-1)))

Submission status: Runtime Error

Solution code:
# coding: utf-8
from scipy.sparse.csgraph import floyd_warshall,csgraph_from_dense

MAX=float('inf')
N,M,L=map(int, input().split())
Roads = [[ 0 if i == j else MAX for j in range(N)] for i in range(N)]

for i in range(M):
    f,t,c = map(int, input().split())
    Roads[f-1][t-1] = c
    Roads[t-1][f-1] = c

RG = csgraph_from_dense(Roads, null_value=MAX)
Rd = floyd_warshall(RG)

Fuels = [[ 1 if Rd[i][j] <=L else MAX for j in range(N)] for i in range(N)]

FG = csgraph_from_dense(Fuels, null_value=MAX)
Fd = floyd_warshall(FG)

Q=int(input())
Queries = []
for i in range(Q):
    s, t = map(int, input().split())
    v = Fd[s-1][t-1]
    if v == float('inf'):
        print (str(-1))
    else:
        print (str(int(v -1)))

Submission status: Runtime Error

Solution code:
# coding: utf-8
from scipy.sparse.csgraph import floyd_warshall,csgraph_from_dense

MAX=pow(10,9) * 300
N,M,L=map(int, input().split())
Roads = [[ 0 if i == j else MAX for j in range(N)] for i in range(N)]

for i in range(M):
    f,t,c = map(int, input().split())
    Roads[f-1][t-1] = c
    Roads[t-1][f-1] = c

RG = csgraph_from_dense(Roads, null_value=MAX)
Rd = floyd_warshall(RG)

Fuels = [[ 1 if Rd[i][j] <=L else MAX for j in range(N)] for i in range(N)]

FG = csgraph_from_dense(Fuels, null_value=MAX)
Fd = floyd_warshall(FG)

Q=int(input())
Queries = []
for i in range(Q):
    s, t = map(int, input().split())
    v = Fd[s-1][t-1]
    if v == float('inf'):
        print (str(-1))
    else:
        print (str(int(v -1)))

Submission status: Runtime Error

Solution code:
from collections import defaultdict
from heapq import heappop, heappush


class Graph(object):
    """
    隣接リストによる有向グラフ
    """

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    """
    ダイクストラ法（二分ヒープ）による最短経路探索
    計算量: O((E+V)logV)
    """

    def __init__(self, graph, start):
        self.g = graph.graph

        # startノードからの最短距離
        # startノードは0, それ以外は無限大で初期化
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        # 最短経路での1つ前のノード
        self.prev = defaultdict(lambda: None)

        # startノードをキューに入れる
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            # 優先度（距離）が最小であるキューを取り出す
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        """
        startノードからgoalノードまでの最短距離
        """
        return self.dist[goal]

    def shortest_path(self, goal):
        """
        startノードからgoalノードまでの最短経路
        """
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]


g = Graph()
N, M, L = [int(i) for i in input().split()]

for i in range(M):
    u, v, c = [int(i) for i in input().split()]
    g.add_edge(u - 1, v - 1, c)
    g.add_edge(v - 1, u - 1, c)


g2 = Graph()
for i in range(N):
    d = Dijkstra(g, i)
    for j in range(N):
        dist = d.dist[j]
        if dist <= L and i != j:
            g2.add_edge(i, j, 1)


s_0 = -1
ans = []
Q = int(input())
s_t_index = []
for i in range(Q):
    s, t = [int(i) for i in input().split()]
    s_t_index.append([s, t, i])

s_t_index.sort()

for i, sti in s_t_index:
    if sti[0] != s_0:
        s_0 = sti[0]
        d = Dijkstra(g2, s_0-1)
        ans.append([sti[2], d.dist[sti[1]-1]])
    else:
        ans.append([sti[2], d.dist[sti[1]-1]])

ans.sort()
[print([ans[i][1]-1, -1][ans[i][1] == float("inf")]) for i in range(Q)]

Submission status: Runtime Error

Solution code:
import sys

from scipy.sparse.csgraph import floyd_warshall
import numpy as np

input = sys.stdin.readline


def solve():
    infinity = 10 ** 10
    n, m, le = map(int, input().split())
    paths = np.full((n, n), infinity)
    for i in range(n):
        paths[i, i] = 0

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

    paths = floyd_warshall(paths)
    refuels = floyd_warshall(paths <= le)

    q = int(input())
    answer = []
    for _ in range(q):
        s, t = map(int, input().split())
        answer.append(int(refuels[s - 1][t - 1] - 1))

    print("\n".join(map(str, answer)))


if __name__ == "__main__":
    solve()

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
import math

#input = sys.stdin.readline


def solve():
    n, m, le = map(int, input().split())
    paths = np.zeros((n, n))
    for i in range(n):
        for j in range(n):
            if i != j:
                paths[i, j] = math.inf

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

    for i in range(n):
        for j in range(n):
            for k in range(n):
                paths[i, j] = min(paths[i, j], paths[i, k] + paths[k, j])

    refuels = np.array(paths, copy=True)
    for i in range(n):
        for j in range(n):
            refuels[i, j] = 1 if paths[i, j] < le else math.inf
            if i == j:
                refuels[i, j] = 0

    for i in range(n):
        for j in range(n):
            for k in range(n):
                refuels[i, j] = min(refuels[i, j], refuels[i, k] + refuels[k, j])

    q = int(input())
    for _ in range(q):
        s, t = map(int, input().split())
        print(int(refuels[s-1, t-1] - 1 if refuels[s-1, t-1] < math.inf else -1))


if __name__ == "__main__":
    solve()

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
import math

input = sys.stdin.readline


def solve():
    n, m, le = map(int, input().split())
    paths = np.zeros((n, n))
    for i in range(n):
        for j in range(n):
            if i != j:
                paths[i, j] = math.inf

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

    for i in range(n):
        for j in range(n):
            for k in range(n):
                paths[i, j] = min(paths[i, j], paths[i, k] + paths[k, j])

    refuels = np.array(paths, copy=True)
    for i in range(n):
        for j in range(n):
            refuels[i, j] = 1 if paths[i, j] < le else math.inf
            if i == j:
                refuels[i, j] = 0

    for i in range(n):
        for j in range(n):
            for k in range(n):
                refuels[i, j] = min(refuels[i, j], refuels[i, k] + refuels[k, j])

    q = int(input())
    for _ in range(q):
        s, t = map(int, input().split())
        print(int(refuels[s-1, t-1] - 1 if refuels[s-1, t-1] < math.inf else -1))


if __name__ == "__main__":
    solve()

Submission status: Runtime Error

Solution code:
N, M, L = map(int, input().split(" "))

edges = [tuple(map(int, input().split(" "))) for i in range (M)]
edges = [(x-1, y-1, w) for (x, y, w) in edges if w <= L]
edgeDict = {}
for (x, y, w) in edges:
    if x not in edgeDict:
        edgeDict[x] = {}
    edgeDict[x][y] = w

    if y not in edgeDict:
        edgeDict[y] = {}
    edgeDict[y][x] = w

def wf(V, E):
    dist = [[int(1e25)] * N for i in range(N)]
    next_ = [[None] * N for i in range(N)]
    for x, y, w in E:
        dist[x][y] = w
        dist[y][x] = w
        next_[x][y] = y
        next_[y][x] = x

    for v in V:
        dist[v][v] = 0
        next_[v][v] = v

    for k in range(0, len(V)):
        for i in range(0, len(V)):
            for j in range(0, len(V)):
                if dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k]+ dist[k][j]
                    next_[i][j] = next_[i][k]

    return next_, dist

def path(next_, u, v):
    if next_[u][v] == None:
        return None
    path = [u]
    while u != v:
        u = next_[u][v]
        path.append(u)
    return path

next_, dist = wf(range(N), edges)

Q = int(input())
for i in range(Q):
    s, t = map(int, input().split(" "))
    s -= 1
    t -= 1


    p = path(next_, s, t)
    if p == None:
        print(-1)
        continue
    tank = L
    count = 0
    u = next(p)
    for v in p:
        w = edgeDict[u][v]
        if w > tank:
            count += 1
            tank = L - w
        else:
            tank -= w
        u = v
    print(count)

Submission status: Runtime Error

Solution code:
N, M, L = map(int, input().split(" "))

edges = [tuple(map(int, input().split(" "))) for i in range (M)]
edges = [(x-1, y-1, w) for (x, y, w) in edges if w <= L]
edgeDict = {}
for (x, y, w) in edges:
    if x not in edgeDict:
        edgeDict[x] = {}
    edgeDict[x][y] = w

    if y not in edgeDict:
        edgeDict[y] = {}
    edgeDict[y][x] = w

def wf(V, E):
    dist = [[int(1e25)] * N for i in range(N)]
    next_ = [[None] * N for i in range(N)]
    for x, y, w in E:
        dist[x][y] = w
        dist[y][x] = w
        next_[x][y] = y
        next_[y][x] = x

    for v in V:
        dist[v][v] = 0
        next_[v][v] = v

    for k in range(0, len(V)):
        for i in range(0, len(V)):
            for j in range(0, len(V)):
                if dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k]+ dist[k][j]
                    next_[i][j] = next_[i][k]

    return next_, dist

def path(next_, u, v):
    if next_[u][v] == None:
        return None
    yield u
    while u != v:
        u = next_[u][v]
        yield u

next_, dist = wf(range(N), edges)

Q = int(input())
for i in range(Q):
    s, t = map(int, input().split(" "))
    s -= 1
    t -= 1


    p = path(next_, s, t)
    if p == None:
        print(-1)
        continue
    tank = L
    count = 0
    u = next(p)
    for v in p:
        w = edgeDict[u][v]
        if w > tank:
            count += 1
            tank = L - w
        else:
            tank -= w
        u = v
    print(count)

Submission status: Runtime Error

Solution code:
def warshall_floyd(dist):
    #d[i][j]: iからjへの最短距離
    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])
    return dist

def main():
    n, m, l = map(int, input().split()) #N:頂点数　M:辺の数 L:容量
    dist = [[float("inf") for i in range(n)] for j in range(n)]
    
    for i in range(n):
        dist[i][i] = 0

    for i in range(m):
        a, b, c = map(int, input().split())
        dist[a-1][b-1] = c
        dist[b-1][a-1] = c

    warshall_floyd(dist)
    dist2 = [[float("inf") for i in range(n)] for j in range(n)]

    for i in range(n):
        for j in range(n):
            if dist[i][j] <= l:
                dist2[i][j] = 1

    warshall_floyd(dist2)
    q = int(input())
    for i in range(q):
        s, t = map(int, input().split())
        ans = dist2[s-1][t-1]-1
        if dist2[s-1][t-1] == float("inf"):
            ans = -1
        print(ans)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def main():
def warshall_floyd(dist):
    #d[i][j]: iからjへの最短距離
    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])
    return dist

n, m, l = map(int, input().split()) #N:頂点数　M:辺の数 L:容量
dist = [[float("inf") for i in range(n)] for j in range(n)]

for i in range(n):
    dist[i][i] = 0

for i in range(m):
    a, b, c = map(int, input().split())
    dist[a-1][b-1] = c
    dist[b-1][a-1] = c

warshall_floyd(dist)
dist2 = [[float("inf") for i in range(n)] for j in range(n)]

for i in range(n):
    for j in range(n):
        if dist[i][j] <= l:
            dist2[i][j] = 1

warshall_floyd(dist2)
q = int(input())
for i in range(q):
    s, t = map(int, input().split())
    ans = dist2[s-1][t-1]-1
    if dist2[s-1][t-1] == float("inf"):
        ans = -1
    print(ans)
    
if __name__ == '__main__':
    main()