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

Solution code:
class WarshallFroyd():
    def __init__(self, N):
        self.N = N
        self.d = [[float('inf')] * N for _ in range(N)]

    def add(self, u, v, c, directed=False):
        """
        Valid only for '0-indexed' graphs!
        add an edge from u to v with cost d
        """
        if directed == False:
            self.d[u][v] = c
            self.d[v][u] = c
        else:
            self.d[u][v] = c

    def WarshallFloyd_search(self, DetectNegativeCycle=False):
        """
        Change self.d to self.d[i][j] = (minimal cost from i to j)
        If self.d[i][j] < 0, this graph has negative loops
        """
        for k in range(self.N):
            for i in range(self.N):
                for j in range(self.N):
                    self.d[i][j] = min(self.d[i][j], self.d[i][k] + self.d[k][j])
        if DetectNegativeCycle == True:
            hasNegativeCycle = False
            for i in range(self.N):
                if self.d[i][i] < 0:
                    hasNegativeCycle = True
                    break
        for i in range(self.N):
            self.d[i][i] = 0
        if DetectNegativeCycle == True:
            return hasNegativeCycle, self.d
        else:
            return None, self.d


"""
classを使いまわすと遅い？？？
以下は直接実装にしてみた。
"""

N, M, L = map(int, input().split())
dp = [[float('inf')] * N for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    dp[a-1][b-1] = c
    dp[b-1][a-1] = c
for k in range(N):
    for i in range(N):
        for j in range(N):
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
#rint('distance={}'.format(dp))


dp2 = [[float('inf')] * N for _ in range(N)]
for a in range(N - 1):
    for b in range(a+1, N):
        if dp[a][b] <= L:
            dp2[a][b] = 1
            dp2[b][a] = 1
for k in range(N):
    for i in range(N):
        for j in range(N):
            dp2[i][j] = min(dp2[i][j], dp2[i][k] + dp2[k][j])
#print('times={}'.format(dp2))


Q = int(input())
for _ in range(Q):
    s, t = map(int, input().split())
    if dp2[s-1][t-1] != float('inf'):
        print(dp2[s-1][t-1] - 1)
    else:
        print(-1)

Submission status: Time Limit Exceeded

Solution code:
class WarshallFroyd():
    def __init__(self, N):
        self.N = N
        self.d = [[float('inf')] * N for _ in range(N)]

    def add(self, u, v, c, directed=False):
        """
        Valid only for '0-indexed' graphs!
        add an edge from u to v with cost d
        """
        if directed == False:
            self.d[u][v] = c
            self.d[v][u] = c
        else:
            self.d[u][v] = c

    def WarshallFloyd_search(self, DetectNegativeCycle=False):
        """
        Change self.d to self.d[i][j] = (minimal cost from i to j)
        If self.d[i][j] < 0, this graph has negative loops
        """
        for k in range(self.N):
            for i in range(self.N):
                for j in range(self.N):
                    self.d[i][j] = min(self.d[i][j], self.d[i][k] + self.d[k][j])
        if DetectNegativeCycle == True:
            hasNegativeCycle = False
            for i in range(self.N):
                if self.d[i][i] < 0:
                    hasNegativeCycle = True
                    break
        for i in range(self.N):
            self.d[i][i] = 0
        if DetectNegativeCycle == True:
            return hasNegativeCycle, self.d
        else:
            return self.d



N, M, L = map(int, input().split())
graph = WarshallFroyd(N)
for _ in range(M):
    a, b, c = map(int, input().split())
    graph.add(a-1, b-1, c)
d = graph.WarshallFloyd_search()
#print('distance={}'.format(d))


graph2 = WarshallFroyd(N)
for a in range(N - 1):
    for b in range(a+1, N):
        if d[a][b] <= L:
            graph2.add(a, b, 1)
times = graph2.WarshallFloyd_search()
#print('times={}'.format(times))


Q = int(input())
for _ in range(Q):
    s, t = map(int, input().split())
    if times[s-1][t-1] != float('inf'):
        print(times[s-1][t-1] - 1)
    else:
        print(-1)

Submission status: Time Limit Exceeded

Solution code:
class WarshallFroyd():
    def __init__(self, N):
        self.N = N
        self.d = [[float('inf')] * N for _ in range(N)]

    def add(self, u, v, c, directed=False):
        """
        Valid only for '0-indexed' graphs!
        add an edge from u to v with cost d
        """
        if directed == False:
            self.d[u][v] = c
            self.d[v][u] = c
        else:
            self.d[u][v] = c

    def WarshallFloyd_search(self):
        """
        Change self.d to self.d[i][j] = (minimal cost from i to j)
        If self.d[i][j] < 0, this graph has negative loops
        """
        for k in range(self.N):
            for i in range(self.N):
                for j in range(self.N):
                    self.d[i][j] = min(self.d[i][j], self.d[i][k] + self.d[k][j])
        hasNegativeCycle = False
        for i in range(self.N):
            if self.d[i][i] < 0:
                hasNegativeCycle = True
                break
        for i in range(self.N):
            self.d[i][i] = 0
        return hasNegativeCycle, self.d



N, M, L = map(int, input().split())
graph = WarshallFroyd(N)
for _ in range(M):
    a, b, c = map(int, input().split())
    graph.add(a-1, b-1, c)
_, d = graph.WarshallFloyd_search()
#print('distance={}'.format(d))


graph2 = WarshallFroyd(N)
for a in range(N - 1):
    for b in range(a+1, N):
        if d[a][b] <= L:
            graph2.add(a, b, 1)
_, times = graph2.WarshallFloyd_search()
#print('times={}'.format(times))


Q = int(input())
for _ in range(Q):
    s, t = map(int, input().split())
    if times[s-1][t-1] != float('inf'):
        print(times[s-1][t-1] - 1)
    else:
        print(-1)

Submission status: Time Limit Exceeded

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

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

# from scipy.sparse.csgraph import floyd_warshall

for i in range(m):  # ノード番号が1始まりで与えられている場合
    for j in range(2):
        A[i][j] -= 1

for i in range(q):  # ノード番号が1始まりで与えられている場合
    for j in range(2):
        S[i][j] -= 1

M = [[float("inf")] * n for i in range(n)]

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

for i in range(m):
    M[A[i][0]][A[i][1]] = A[i][2]
    M[A[i][1]][A[i][0]] = A[i][2]

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

# M = floyd_warshall(M)

for i in range(n):
    for j in range(n):
        M[i][j] = 1 if M[i][j] <= l else float("inf")

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

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

# M = floyd_warshall(M)

for i in range(q):
    ans = M[S[i][0]][S[i][1]]-1
    if ans == float("inf"):
        ans = -1
    print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n,m,l = LI()
    aa = [LI() for _ in range(m)]
    q = I()
    qa = [LI_() for _ in range(q)]

    e = collections.defaultdict(list)
    for a,b,c in aa:
        if c > l:
            continue
        a -= 1
        b -= 1
        e[a].append((b,c))
        e[b].append((a,c))

    def search(s):
        d = collections.defaultdict(lambda: (inf, inf))
        d[s] = (0,-l)
        q = []
        heapq.heappush(q, ((0,0), s))
        v = collections.defaultdict(bool)
        while len(q):
            k, u = heapq.heappop(q)
            if v[u]:
                continue
            v[u] = True
            kk = k[0]
            kl = k[1]

            for uv, ud in e[u]:
                if v[uv]:
                    continue
                if kl + ud > l:
                    vd = (kk+1, ud)
                else:
                    vd = (kk, kl+ud)
                if d[uv] > vd:
                    d[uv] = vd
                    heapq.heappush(q, (vd, uv))

        return d

    dd = {}
    for i in range(n):
        d = search(i)
        for k in range(n):
            v = d[k]
            if v[0] == inf:
                d[k] = -1
            else:
                d[k] = v[0]
        dd[i] = d

    rr = []
    for s,t in qa:
        rr.append(dd[s][t])

    return JA(rr, "\n")


print(main())

Submission status: Time Limit Exceeded

Solution code:
n,m,l=map(int,input().split())
abc=[list(map(int,input().split())) for _ in [0]*m]
q=int(input())
st=[list(map(int,input().split())) for _ in [0]*q]
inf=10**12
dist=[[inf]*n for _ in [0]*n]
for i in range(n):
    dist[i][i]=0
for a,b,c in abc:
    dist[a-1][b-1]=c
    dist[b-1][a-1]=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])
inf=10**3
dist2=[[inf]*n for _ in [0]*n]
for i in range(n):
    for j in range(n):
        if dist[i][j]<=l:
            dist2[i][j]=1
for k in range(n):
    for i in range(n):
        for j in range(n):
            dist2[i][j]=min(dist2[i][j],dist2[i][k]+dist2[k][j])
for i in range(n):
    for j in range(n):
        if dist2[i][j]==inf:
            dist2[i][j]=-1
        else:
            dist2[i][j]-=1
for s,t in st:
    print(dist2[s-1][t-1])

Submission status: Time Limit Exceeded

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):
        """
        Initialize either empty graph or one from a dictionary adjacency list
        """
        self.edges = []
        self.id2name={}
        self.name2id={}
        self.num_edges = 0
        self.num_nodes = 0
    
    def add_node(self,node):
        # Adds a vertex to graph (based on key value)
        ind = self.num_nodes
        self.id2name[ind] = node
        self.name2id[node] = ind
        self.edges.append(dict())
        self.num_nodes += 1

    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[self.name2id[src]][self.name2id[dest]] = weight
  
    def children_of(self, v):
        # Returns a node's children
        return self.edges[self.name2id[v]].items()
    
    def children_of_id(self, v_id):
        # Returns a node's children
        return self.edges[v_id].items()
    
    def get_nodes(self):
        # Returns a node's children
        return self.name2id.keys()
        
    def has_node(self, v):
        # Checks if node exists
        return v in self.name2id
        
    def has_edge(self, v, w):
        # Checks if edge exists
        return self.name2id[w] in self.edges[self.name2id[v]]
    
    def has_edge_id(self, v_id, w_id):
        # Checks if edge exists
        return w_id in self.edges[v_id]

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

    def warshall_floyd(self):
        dist=[]
        #initialize
        for src_id in range(self.num_nodes):
            dist_src=[]
            for dest_id in range(self.num_nodes):
                if self.has_edge_id(src_id, dest_id):
                    dist_src.append(self.edges[src_id][dest_id])
                elif src_id != dest_id:
                    dist_src.append(float('inf'))
                else:
                    dist_src.append(0)
            dist.append(dist_src)
        #construct
        for via_id in range(self.num_nodes):
            for src_id in range(self.num_nodes):
                for dest_id in range(self.num_nodes):
                    dist[src_id][dest_id] = min(dist[src_id][dest_id], dist[src_id][via_id]+dist[via_id][dest_id])
        return dist
    
    def dijkstra(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 i in range(N):
    graph_2.add_node(i+1)


dist = graph_1.warshall_floyd()
for src_id in range(N):
    for dest_id in range(N):
        if dest_id != src_id and dist[src_id][dest_id]<=L:
            graph_2.add_edge(src_id+1, dest_id+1, 1)
            
dist2 = graph_2.warshall_floyd()
            
Q=int(input())
for i in range(Q):
    src, dest = map(int, input().split())
    ans = dist2[src-1][dest-1]
    if ans == float('inf'):
        print(-1)
    else:
        print(ans-1)

Submission status: Time Limit Exceeded

Solution code:
inf = float('inf')

#計算量O(V^3) V:頂点数
# dist[i][j]: iからjへのコスト,  n:頂点数
def warshall_floyd(ad):
    n = len(ad)
    dist = [line[:] for line in ad]
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if i == j:
                    dist[i][j] = 0
                elif dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    return dist

N, M, L = map(int,input().split())
ad = [[inf] * N for _ in range(N)]
for _ in range(M):
    A, B, C = map(int,input().split())
    if C > L:
        continue
    A -= 1
    B -= 1
    ad[A][B] = C
    ad[B][A] = C
Q = int(input())
query = [[int(e)-1 for e in input().split()] for _ in range(Q)]

ad = warshall_floyd(ad)
for s in range(N):
    for t in range(N):
        if ad[s][t] <= L:
            ad[s][t] = 1
        else:
            ad[s][t] = inf

ad = warshall_floyd(ad)
for s, t in query:
    ans = ad[s][t] - 1
    if ans == inf:
        ans = -1
    print(ans)

Submission status: Time Limit Exceeded

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 warshall_floyd(self):
        nodes = self.get_nodes()
        dist={}
        #initialize
        for src in nodes:
            dist_src={}
            for dest in nodes:
                if self.has_edge(src, dest):
                    dist_src[dest] = self.edges[src][dest]
                elif src != dest:
                    dist_src[dest] = float('inf')
                else:
                    dist_src[dest] = 0
            dist[src]=dist_src
        #construct
        for via in nodes:
            for src in nodes:
                for dest in nodes:
                    dist[src][dest] = min(dist[src][dest], dist[src][via]+dist[via][dest])
        return dist
    
    def dijkstra(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 i in range(N):
    graph_2.add_node(i+1)


dist = graph_1.warshall_floyd()

for src in range(1,N+1):
    for dest in range(1,N+1):
        if dest != src and dist[src][dest]<=L:
            graph_2.add_edge(src, dest, 1)
            
dist2 = graph_2.warshall_floyd()
            
Q=int(input())
for i in range(Q):
    src, dest = map(int, input().split())
    ans = dist2[src][dest]
    if ans == float('inf'):
        print(-1)
    else:
        print(ans-1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, M, L = map(int, input().split())
D = np.full((N, N), np.inf)
for i in range(N):
    D[i][i] = 0
    
for _ in range(M):
    A, B, C = map(int, input().split())
    D[A - 1][B - 1] = D[B - 1][A - 1] = C
    
for k in range(N):
    for i in range(N):
        for j in range(N):
            D[i][j] = min(D[i][j], D[i][k] + D[k][j])

D2 = np.full((N, N), np.inf)
for i in range(N):
    for j in range(N):
        if D[i][j] <= L:
            D2[i][j] = 1
    
for k in range(N):
    for i in range(N):
        for j in range(N):
            D2[i][j] = min(D2[i][j], D2[i][k] + D2[k][j])
            
Q = int(input())
for i in range(Q):
    s, t = map(int, input().split())
    if D2[s - 1][t - 1] == np.inf:
        print(-1)
    else:
        print(D2[s - 1][t - 1] - 1)

Submission status: Time Limit Exceeded

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

def floyd_warshall(cost,n):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                new = min(cost[i][j], cost[i][k] + cost[k][j])
                cost[i][j] = new
                cost[j][i] = new
    return np.array(cost)

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

Solution code:
import sys
imput=sys.stdin.readline

class WarshallFloyd():
    def __init__(self, N):
        self.N = N
        self.d = [[float("inf") for i in range(N)]
                  for i in range(N)]  # d[u][v] : 辺uvのコスト(存在しないときはinf)

    def add(self, u, v, c, directed=False):
        """
        0-indexedであることに注意
        u = from, v = to, c = cost
        directed = Trueなら、有向グラフである
        """
        if directed is False:
            self.d[u][v] = c
            self.d[v][u] = c
        else:
            self.d[u][v] = c

    def WarshallFloyd_search(self):
        for k in range(self.N):
            for i in range(self.N):
                for j in range(self.N):
                    self.d[i][j] = min(
                        self.d[i][j], self.d[i][k] + self.d[k][j])
        hasNegativeCycle = False
        for i in range(self.N):
            if self.d[i][i] < 0:
                hasNegativeCycle = True
                break
        for i in range(self.N):
            self.d[i][i] = 0
        return hasNegativeCycle, self.d


n,m,l=map(int,input().split())
ABC=[list(map(int, input().split())) for i in range(m)]
q=int(input())
st=[list(map(int, input().split())) for i in range(q)]

graph=WarshallFloyd(n)
graph2=WarshallFloyd(n)
for a,b,c in ABC:
    graph.add(a-1,b-1,c)
hasNegativeCycle, d = graph.WarshallFloyd_search()
ans=graph.WarshallFloyd_search()
#print(ans)

for i in range(n):
    for j in range(i+1,n):
        if ans[1][i][j]<=l:
            graph2.add(i,j,1)
        else:
            graph2.add(i,j,float('inf'))
ans1=graph2.WarshallFloyd_search()
#print(ans1)
for i,j in st:
    i,j=min(i,j),max(i,j)
    if ans1[1][i-1][j-1]-1!=float('inf'):
        print(ans1[1][i-1][j-1]-1)
    else:
        print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
imput=sys.stdin.readline

class WarshallFloyd():
    def __init__(self, N):
        self.N = N
        self.d = [[float("inf") for i in range(N)]
                  for i in range(N)]  # d[u][v] : 辺uvのコスト(存在しないときはinf)

    def add(self, u, v, c, directed=False):
        """
        0-indexedであることに注意
        u = from, v = to, c = cost
        directed = Trueなら、有向グラフである
        """
        if directed is False:
            self.d[u][v] = c
            self.d[v][u] = c
        else:
            self.d[u][v] = c

    def WarshallFloyd_search(self):
        # これを d[i][j]: iからjへの最短距離 にする
        # 本来無向グラフでのみ全域木を考えるが、二重辺なら有向でも行けそう
        # d[i][i] < 0 なら、グラフは負のサイクルを持つ
        for k in range(self.N):
            for i in range(self.N):
                for j in range(self.N):
                    self.d[i][j] = min(
                        self.d[i][j], self.d[i][k] + self.d[k][j])
        hasNegativeCycle = False
        for i in range(self.N):
            if self.d[i][i] < 0:
                hasNegativeCycle = True
                break
        for i in range(self.N):
            self.d[i][i] = 0
        return hasNegativeCycle, self.d


n,m,l=map(int,input().split())
ABC=[list(map(int, input().split())) for i in range(m)]
q=int(input())
st=[list(map(int, input().split())) for i in range(q)]

graph=WarshallFloyd(n)
graph2=WarshallFloyd(n)
for a,b,c in ABC:
    graph.add(a-1,b-1,c)
hasNegativeCycle, d = graph.WarshallFloyd_search()
#ans = sorted([[i, max(d[i])] for i in range(n)], key=lambda x: x[0])
ans=graph.WarshallFloyd_search()
#print(ans)

for i in range(n):
    for j in range(n):
        if ans[1][i][j]<=l:
            graph2.add(i,j,1)
        else:
            graph2.add(i,j,float('inf'))
ans1=graph2.WarshallFloyd_search()
#print(ans1)
for i,j in st:
    if ans1[1][i-1][j-1]-1!=float('inf'):
        print(ans1[1][i-1][j-1]-1)
    else:
        print(-1)