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

Solution (Python):
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  
def LS2(): return list(sys.stdin.readline().rstrip())  


N,M,L = MI()


class WarshallFloyd():
    def __init__(self,N):  
        self.N = N
        self.d = [[float('inf')]*N for i in range(N)]  
    def add(self,u,v,c,directed = False):
        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])
        return self.d


W = WarshallFloyd(N)
for i in range(M):
    a,b,c = MI()
    W.add(a-1,b-1,c,directed=False)
d = W.WarshallFloyd_search()

d2 = [[float('inf')]*N for _ in range(N)]
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 = I()
for i in range(Q):
    s,t = MI()
    if d2[s-1][t-1] == float('inf'):
        print(-1)
        continue
    print(d2[s-1][t-1]-1)

Solution (Python):
def warshall_floyd(d,n):
    
    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])
    return d


def main():
    INF = 10**18
    n,m,l = map(int, input().split())
    d = [ [INF]*(n+1) for _ in range(n+1) ]
    for _ in range(m):
        a,b,c = map(int, input().split())
        d[a][b] = c
        d[b][a] = c

    d = warshall_floyd(d,n+1)
    new_d = [ [INF]*(n+1) for _ in range(n+1) ]
    for a in range(n+1):
        for b in range(n+1):
            if d[a][b] <= l:
                new_d[a][b] = 1
                new_d[b][a] = 1


    new_d = warshall_floyd(new_d,n+1)
    ansl = []
    q = int(input())
    for _ in range(q):
        s,t = map(int, input().split())
        ans = new_d[s][t]
        if ans >= INF: ans = 0
        ansl.append(ans-1)

    for a in ansl: print(a)



if __name__ == "__main__":
    main()

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    N, M, L = map(int, rl().split())
    INF = 10 ** 18
    dist = [[INF] * N for _ in range(N)]
    for _ in range(M):
        a, b, c = map(int, rl().split())
        a, b = a - 1, b - 1
        dist[a][b] = dist[b][a] = 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])
    
    cost = [[INF] * N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if dist[i][j] <= L:
                cost[i][j] = 1
    
    for k in range(N):
        for i in range(N):
            for j in range(N):
                cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j])
    
    Q = int(rl())
    st = [list(map(lambda n: int(n) - 1, rl().split())) for _ in range(Q)]
    ans = [-1] * Q
    for i, (s, t) in enumerate(st):
        if cost[s][t] != INF:
            ans[i] = cost[s][t] - 1
    print(*ans, sep='\n')


if __name__ == '__main__':
    solve()

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache





MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]



def DD(arg): return defaultdict(arg)


def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr


def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum


def gcd(a, b):
    while b: a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count






  
N,M,L = IL()

class WarshallFloyd():
  def __init__(self, N):
    self.N = N
    self.d = [[float("inf") for i in range(N)] for i in range(N)]

  def add(self, u, v, c, directed=False):
    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
  
W = WarshallFloyd(N)
for _ in range(M):
  u,v,c = IL()
  if c>L: continue
  W.add(u-1,v-1,c)

_,d = W.WarshallFloyd_search() 


W = WarshallFloyd(N)
for u in range(N):
  for v in range(u+1,N):
    if d[u][v] > L: continue
    W.add(u,v,1)

_,d = W.WarshallFloyd_search() 

Q = I()
for _ in range(Q):
  s,t = IL()
  if d[s-1][t-1] == INF:
    print(-1)
  else:
    print(d[s-1][t-1]-1)

Solution (Python):
def numba_compile(numba_config):
    import os, sys
    if sys.argv[-1] == "ONLINE_JUDGE":
        from numba import njit
        from numba.pycc import CC
        cc = CC("my_module")
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature)(func)
            cc.export(func.__name__, signature)(func)
        cc.compile()
        exit()
    elif os.name == "posix":
        exec(f"from my_module import {','.join(func.__name__ for func, _ in numba_config)}")
        for func, _ in numba_config:
            globals()[func.__name__] = vars()[func.__name__]
    else:
        from numba import njit
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature, cache=True)(func)
        print("compiled!", file=sys.stderr)

import numpy as np

def solve(N, M, L, ABC, Q, ST):
    inf = 1<<61
    G = np.full((N+1, N+1), inf)
    G.ravel()[::N+2] = 0
    for i in range(M):
        a, b, c = ABC[i]
        G[a, b] = c
        G[b, a] = c
    for k in range(N+1):
        for i in range(N+1):
            for j in range(N+1):
                if G[i, j] > G[i, k] + G[k, j]:
                    G[i, j] = G[i, k] + G[k, j]
    G = np.where(G<=L, 1, inf)
    G.ravel()[::N+2] = 0
    for k in range(N+1):
        for i in range(N+1):
            for j in range(N+1):
                if G[i, j] > G[i, k] + G[k, j]:
                    G[i, j] = G[i, k] + G[k, j]
    G = np.where(G==inf, 0, G) - 1
    
    Ans = np.zeros(Q, dtype=np.int64)
    for i, (s, t) in enumerate(zip(ST[:,0], ST[:,1])):
        Ans[i] = G[s, t]
    return Ans

numba_compile([
    [solve, "i8[:](i8,i8,i8,i8[:,:],i8,i8[:,:])"]
])

N, M, L = map(int, input().split())
ABC = np.array([list(map(int, input().split())) for _ in range(M)], dtype=np.int64)
Q = int(input())
ST = np.array([list(map(int, input().split())) for _ in range(Q)], dtype=np.int64)

Ans = solve(N, M, L, ABC, Q, ST)
print("\n".join(map(str, Ans.tolist())))

Solution (Python):
def floyd_warshall(G):
    for k in range(N):
        for i in range(N):
            for j in range(N):
                G[i][j]=min(G[i][j],G[i][k]+G[k][j])

import sys
input=sys.stdin.readline
INF=10**30
N,M,L=map(int,input().split())
dp1=[[INF]*N for i in range(N)]
for i in range(N):
    dp1[i][i]=0
for _ in range(M):
    A,B,C=map(int,input().split())
    A,B=A-1,B-1
    dp1[A][B]=C
    dp1[B][A]=C

floyd_warshall(dp1)

dp2=[[INF]*N for i in range(N)]
for i in range(N):
    for j in range(N):
        if i==j:
            dp2[i][j]=0
        else:
            dp2[i][j]=1 if dp1[i][j]<=L else INF
floyd_warshall(dp2)

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

Solution (Python):

import sys


def solve(N: int, M: int, L: int, A: "List[int]", B: "List[int]", C: "List[int]", Q: int, s: "List[int]", t: "List[int]"):
    import numpy as np    
    from scipy.sparse import coo_matrix    
    from scipy.sparse.csgraph import floyd_warshall
   
    mat = floyd_warshall(coo_matrix((C, (A, B)), shape=(N+1, N+1), dtype=np.int32).tocsr(), directed=False)
    mat = floyd_warshall(mat <= L, directed=False)
    for ss, tt in zip(s, t):
        yield -1 if np.isinf(mat[ss][tt]) else int(mat[ss][tt]) - 1



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    M = int(next(tokens))  
    L = int(next(tokens))  
    A = [int()] * (M)  
    B = [int()] * (M)  
    C = [int()] * (M)  
    for i in range(M):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
        C[i] = int(next(tokens))
    Q = int(next(tokens))  
    s = [int()] * (Q)  
    t = [int()] * (Q)  
    for i in range(Q):
        s[i] = int(next(tokens))
        t[i] = int(next(tokens))
    print(*solve(N, M, L, A, B, C, Q, s, t), sep="\n")

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    
    main()

Solution (Python):

import sys


def solve(N: int, M: int, L: int, A: "List[int]", B: "List[int]", C: "List[int]", Q: int, s: "List[int]", t: "List[int]"):
    import numpy as np    
    from scipy.sparse import coo_matrix    
    from scipy.sparse.csgraph import floyd_warshall
    mat = floyd_warshall(coo_matrix((C, (A, B)), shape=(N+1, N+1), dtype=np.int32).tocsr(), directed=False)
    mat = floyd_warshall(mat <= L, directed=False)
    for ss, tt in zip(s, t):
        yield -1 if np.isinf(mat[ss][tt]) else int(mat[ss][tt]) - 1



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    M = int(next(tokens))  
    L = int(next(tokens))  
    A = [int()] * (M)  
    B = [int()] * (M)  
    C = [int()] * (M)  
    for i in range(M):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
        C[i] = int(next(tokens))
    Q = int(next(tokens))  
    s = [int()] * (Q)  
    t = [int()] * (Q)  
    for i in range(Q):
        s[i] = int(next(tokens))
        t[i] = int(next(tokens))
    print(*solve(N, M, L, A, B, C, Q, s, t), sep="\n")

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    
    main()

Solution (Python):

import sys


def solve(N: int, M: int, L: int, A: "List[int]", B: "List[int]", C: "List[int]", Q: int, s: "List[int]", t: "List[int]"):
    import numpy as np    
    from scipy.sparse import coo_matrix    
    from scipy.sparse.csgraph import floyd_warshall
    from itertools import filterfalse
    
    mat = floyd_warshall(coo_matrix((C, (A, B)), shape=(N+1, N+1), dtype=np.int32).tocsr(), directed=False)
    mat = floyd_warshall(mat <= L, directed=False)
    for ss, tt in zip(s, t):
        yield -1 if np.isinf(mat[ss][tt]) else int(mat[ss][tt]) - 1



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    M = int(next(tokens))  
    L = int(next(tokens))  
    A = [int()] * (M)  
    B = [int()] * (M)  
    C = [int()] * (M)  
    for i in range(M):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
        C[i] = int(next(tokens))
    Q = int(next(tokens))  
    s = [int()] * (Q)  
    t = [int()] * (Q)  
    for i in range(Q):
        s[i] = int(next(tokens))
        t[i] = int(next(tokens))
    print(*solve(N, M, L, A, B, C, Q, s, t), sep="\n")

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    
    main()

Solution (Python):


"""
タグ: ワーシャルフロイド
"""

class Graph:
    class Edge:
        def __init__(self, to, cost):
            """
            :param to:  終点ノード
            :param cost: 辺の重み
            """
            self.to, self.cost = to, cost

    def __init__(self, n, directed=False, decrement=True, edges=[]):
        self.n = n
        self.directed = directed
        self.decrement = decrement
        self.edges2 = []                            
        for x, y, cost in edges:
            self.add_edge(x, y, cost)

    def add_edge(self, x, y, cost):
        if self.decrement:
            x -= 1
            y -= 1
        self.edges2.append((x, y, cost))
        if self.directed == False:
            self.edges2.append((y, x, cost))     

    def warshall_folyd(self, INF=1<<30):
        """
        :param INF: INF = 10**18 にすると、負のコストがある場合に少し面倒になる
        :return: 頂点 i, j 間の距離を行列として返す
        """
        dist = [[INF] * self.n for _ in range(self.n)]

        for i, j, cost in self.edges2:
            dist[i][j] = cost
        for i in range(self.n):
            dist[i][i] = 0  

        for k in range(self.n):
            for i in range(self.n):
                for j in range(self.n):
                    if dist[i][j] > dist[i][k] + dist[k][j]:
                        dist[i][j] = dist[i][k] + dist[k][j]
        return dist

def max2(x,y):
    return x if x > y else y

from itertools import combinations

N, M, L = map(int, input().split())
graph = Graph(N, directed=False, decrement=True)
for _ in range(M):
    x, y, cost = map(int, input().split())
    graph.add_edge(x, y, cost)

d = graph.warshall_folyd()

graph2 = Graph(N, directed=False, decrement=False)
for i, j in combinations(range(N), 2):
    if d[i][j] <= L:
        graph2.add_edge(i, j, 1)


d = graph2.warshall_folyd()

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

Solution (Python):
import numpy as np

from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix

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

if M == 0:
    Q = int(input())
    for _ in range(Q):
        print(-1)
    exit()

R = np.array([tuple(map(int, input().split())) for _ in range(M)])
matr = csr_matrix((R[:, 2], (R[:, 0] - 1, R[:, 1] - 1)), shape=(N, N))
way = floyd_warshall(matr, directed=False).astype(int)

way = np.where((way >= 0) & (way <= L), 1, 0)
matr_replenishment = csr_matrix(way)
way_replenishment = floyd_warshall(matr_replenishment, directed=False).astype(int).tolist()

Q = int(input())
for _ in range(Q):
    S, T = map(int, input().split())
    print(res - 1 if (res := way_replenishment[S - 1][T - 1]) >= 0 else -1)

Solution (Python):
import numpy as np
from scipy.sparse.csgraph import floyd_warshall


def solve(N,L,edges,queries):

    graph = np.zeros((N,N),dtype=int)
    for a,b,c in edges:
        graph[a-1,b-1] = c
        graph[b-1,a-1] = c

    dist = floyd_warshall(graph, directed=False)
    dist = (dist<=L)
    dist = floyd_warshall(dist, directed=False)
    res = []
    for a,b in queries:
        d = dist[a-1,b-1]
        res.append(int(d-1) if d != float('inf') else -1)
    return res

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

if __name__ == '__main__':

    t = read().split()

    N,M,L = map(int,t[:3])

    m = map(int,t[3:M*3+3])
    edges = zip(m,m,m)

    Q = int(t[M*3+3])
    m = map(int, t[M*3+4:])
    queries = zip(m,m)

    print(*solve(N,L,edges,queries), sep='\n')

Solution (Python):

N, M, L = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(M)]
Q = int(input())
Y = [list(map(int, input().split())) for _ in range(Q)]

INF = 10 ** 9 + 7
graph = [[INF] * N for _ in range(N)]
count = [[INF] * N for _ in range(N)]
for i in range(N):
    graph[i][i] = 0
    count[i][i] = 0

for a, b, c in X:
    graph[a - 1][b - 1] = c
    graph[b - 1][a - 1] = c

for k in range(N):
    for i in range(N):
        for j in range(N):
            graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])

for i in range(N):
    for j in range(N):
        if i != j and graph[i][j] <= L:
            count[i][j] = 1

for k in range(N):
    for i in range(N):
        for j in range(N):
            count[i][j] = min(count[i][j], count[i][k] + count[k][j])

for s, t in Y:
    if count[s - 1][t - 1] == INF:
        print(-1)
    else:
        print(count[s - 1][t - 1] - 1)

Solution (Python):
class Graph:
    class Edge:
        def __init__(self, to, cost):
            """
            :param to:  終点ノード
            :param cost: 辺の重み
            """
            self.to, self.cost = to, cost

    def __init__(self, n, directed=False, decrement=True, edges=[]):
        self.n = n
        self.directed = directed
        self.decrement = decrement
        self.edges2 = []                            
        for x, y, cost in edges:
            self.add_edge(x, y, cost)

    def add_edge(self, x, y, cost):
        if self.decrement:
            x -= 1
            y -= 1
        self.edges2.append((x, y, cost))
        if self.directed == False:
            self.edges2.append((y, x, cost))     

    def warshall_folyd(self, INF=1<<30):
        """
        :param INF: INF = 10**18 にすると、負のコストがある場合に少し面倒になる
        :return: 頂点 i, j 間の距離を行列として返す
        """
        dist = [[INF] * self.n for _ in range(self.n)]

        for i, j, cost in self.edges2:
            dist[i][j] = cost
        for i in range(self.n):
            dist[i][i] = 0  

        for k in range(self.n):
            for i in range(self.n):
                for j in range(self.n):
                    if dist[i][j] > dist[i][k] + dist[k][j]:
                        dist[i][j] = dist[i][k] + dist[k][j]
        return dist

    def warshall_folyd2(self, INF=1<<30):
        """
        :param INF: INF = 10**18 にすると、負のコストがある場合に少し面倒になる
        :return: 頂点 i, j 間の距離を行列として返す
        """
        dist = [[INF] * self.n for _ in range(self.n)]

        for i, j, cost in self.edges2:
            dist[i][j] = cost
            if dist[i][j] <= L:
                data.append((i, j))
        for i in range(self.n):
            dist[i][i] = 0

        for k in range(self.n):
            for i in range(self.n):
                for j in range(self.n):
                    if dist[i][j] > dist[i][k] + dist[k][j]:
                        dist[i][j] = dist[i][k] + dist[k][j]
                        if dist[i][j] <= L:
                            data.append((i, j))
        return dist

def max2(x,y):
    return x if x > y else y

from itertools import combinations

N, M, L = map(int, input().split())
graph = Graph(N, directed=False, decrement=True)
for _ in range(M):
    x, y, cost = map(int, input().split())
    graph.add_edge(x, y, cost)

data = []
d = graph.warshall_folyd2()

graph2 = Graph(N, directed=False, decrement=False)
for i, j in combinations(range(N), 2):
    if d[i][j] <= L:
        graph2.add_edge(i, j, 1)


d = graph2.warshall_folyd()

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

Solution (Python):
class Graph:
    class Edge:
        def __init__(self, to, cost):
            """
            :param to:  終点ノード
            :param cost: 辺の重み
            """
            self.to, self.cost = to, cost

    def __init__(self, n, directed=False, decrement=True, edges=[]):
        self.n = n
        self.directed = directed
        self.decrement = decrement
        self.edges = [[] for _ in range(self.n)]
        self.edges2 = []                            
        self.parent = [-1]*self.n
        self.info = [-1]*self.n
        for x, y, cost in edges:
            self.add_edge(x, y, cost)

    def add_edge(self, x, y, cost):
        if self.decrement:
            x -= 1
            y -= 1
        self.edges[x].append(self.Edge(y, cost))
        self.edges2.append((x, y, cost))
        if self.directed == False:
            self.edges[y].append(self.Edge(x, cost))
            self.edges2.append((y, x, cost))     

    def warshall_folyd(self, INF=1<<30):
        """
        :param INF: INF = 10**18 にすると、負のコストがある場合に少し面倒になる
        :return: 頂点 i, j 間の距離を行列として返す
        """
        dist = [[INF] * self.n for _ in range(self.n)]

        for i, j, cost in self.edges2:
            dist[i][j] = cost
        for i in range(self.n):
            dist[i][i] = 0  

        for k in range(self.n):
            for i in range(self.n):
                for j in range(self.n):
                    if dist[i][j] > dist[i][k] + dist[k][j]:
                        dist[i][j] = dist[i][k] + dist[k][j]
        return dist

    def warshall_folyd2(self, INF=1<<30):
        """
        :param INF: INF = 10**18 にすると、負のコストがある場合に少し面倒になる
        :return: 頂点 i, j 間の距離を行列として返す
        """
        dist = [[INF] * self.n for _ in range(self.n)]

        for i, j, cost in self.edges2:
            dist[i][j] = cost
            if dist[i][j] <= L:
                data.append((i, j))
        for i in range(self.n):
            dist[i][i] = 0

        for k in range(self.n):
            for i in range(self.n):
                for j in range(self.n):
                    if dist[i][j] > dist[i][k] + dist[k][j]:
                        dist[i][j] = dist[i][k] + dist[k][j]
                        if dist[i][j] <= L:
                            data.append((i, j))
        return dist

def max2(x,y):
    return x if x > y else y

from itertools import combinations

N, M, L = map(int, input().split())
graph = Graph(N, directed=False, decrement=True)
for _ in range(M):
    x, y, cost = map(int, input().split())
    graph.add_edge(x, y, cost)

data = []
d = graph.warshall_folyd2()

graph2 = Graph(N, directed=False, decrement=False)
for i, j in combinations(range(N), 2):
    if d[i][j] <= L:
        graph2.add_edge(i, j, 1)


d = graph2.warshall_folyd()

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

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,m,l = list(map(int, input().split()))
from collections import defaultdict
ns = defaultdict(set)
for i in range(m):
    a,b,c = map(int, input().split())
    a-=1
    b-=1
    if c<=l:
        ns[a].add((c,b))
        ns[b].add((c,a))

def wf(ns):
    """全頂点間距離
    """
    d = [[float("inf")]*n for _ in range(n)]
    for i in range(n):
        for t,j in ns[i]:
            d[i][j] = t
        d[i][i] = 0
    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])
    return d
dist = wf(ns)
ns2 = defaultdict(set)
for i in range(n):
    for j in range(i+1,n):
        if dist[i][j]<=l:
            ns2[i].add((1,j))
            ns2[j].add((1,i))
ddist = wf(ns2)
q = int(input())
ans = [None]*q
for i in range(q):
    s,t = map(int, input().split())
    s-=1
    t-=1
    if dist[s][t]==float("inf"):
        ans[i] = -1
    else:
        ans[i] = ddist[s][t] - 1
write("\n".join(map(str, ans)))

Solution (Python):
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall

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

start = []
goal = []
cost = []
for _ in range(M):
    A, B, C = map(int, input().split())
    A -= 1
    B -= 1
    start.append(A)
    goal.append(B)
    cost.append(C)
    start.append(B)
    goal.append(A)
    cost.append(C)

graph = csr_matrix((cost, (start, goal)), shape = (N, N))
can_reach_with_L = floyd_warshall(graph, directed = False)
can_reach_with_L[can_reach_with_L > L] = 0
ans = floyd_warshall(can_reach_with_L, directed = False, unweighted = True)

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

Solution (Python):
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra

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

start = []
goal = []
cost = []
for _ in range(M):
    A, B, C = map(int, input().split())
    A -= 1
    B -= 1
    start.append(A)
    goal.append(B)
    cost.append(C)
    start.append(B)
    goal.append(A)
    cost.append(C)

graph = csr_matrix((cost, (start, goal)), shape = (N, N))
can_reach_with_L = dijkstra(graph, directed = False, limit = L)
ans = dijkstra(can_reach_with_L, directed = False, unweighted = True)

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

Solution (Python):
import math


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def read_into(*A):
    for a, v in zip(A, read_ints()):
        a.append(v)


def solve():
    N, M, L = read_ints()
    dist = [
        [math.inf for _ in range(N)] for _ in range(N)
    ]
    for i in range(N):
        dist[i][i] = 0
    for _ in range(M):
        a, b, c = read_ints()
        dist[a-1][b-1] = dist[b-1][a-1] = c
    for k in range(N):
        for i in range(N):
            for j in range(N):
                dist[i][j] = dist[j][i] = min(dist[i][j], dist[i][k]+dist[k][j])
    for i in range(N):
        for j in range(N):
            if i == j: continue
            dist[i][j] = 1 if dist[i][j] <= L else math.inf
    for k in range(N):
        for i in range(N):
            for j in range(N):
                dist[i][j] = dist[j][i] = min(dist[i][j], dist[i][k]+dist[k][j])
    Q = read_int()
    for _ in range(Q):
        s, t = read_ints()
        if dist[s-1][t-1] == math.inf:
            print(-1)
        else:
            print(dist[s-1][t-1]-1)


if __name__ == '__main__':
    solve()

Solution (Python):
from scipy.sparse.csgraph import floyd_warshall
from numpy import where
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)]
t=[[float("inf")]*n for _ in range(n)]
for a,b,c in abc:
 if c<=l:t[a-1][b-1]=c
f=floyd_warshall(t,0)
l=floyd_warshall(where(f<=l,1,f),0)
for s, t in st:print(-1if l[s-1,t-1]==float("inf")else int(l[s-1,t-1])-1)

Solution (Python):
N,M,L=map(int, input().split())
def warshall_floyd(d):
    
    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])
    return d

d=[[float("inf")]*N for i in range(N)] 

for i in range(M):
    x,y,z=map(int,input().split())
    d[x-1][y-1]=z
    d[y-1][x-1]=z
for i in range(N):
    d[i][i]=0 
D=warshall_floyd(d)
E=[[float("inf")]*N for i in range(N)] 
for i in range(N):
  for j in range(N):
    if D[i][j]==0:
      E[i][j]=0
    elif D[i][j]<=L:
      E[i][j]=1
F=warshall_floyd(E)
N=int(input())
for i in range(N):
  x,y=map(int,input().split())
  if F[x-1][y-1]==float("inf"):
    print(-1)
  else:
    print(F[x-1][y-1]-1)