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**9)
input = sys.stdin.readline


def WF(mat, N):
    for k in range(N):
        for i in range(N):
            for j in range(N):
                mat[i][j] = min(mat[i][j], mat[i][k]+mat[k][j])
    return mat


N, M, L = map(int, input().split())
roads = [[float('inf')]*N for _ in [0]*N]
kyuyu = [[float('inf')]*N for _ in [0]*N]
for _ in range(M):
    a, b, c = map(int, input().split())
    roads[a-1][b-1] = c
    roads[b-1][a-1] = c

roads = WF(roads, N)
for i in range(N):
    for j in range(i+1, N):
        if roads[i][j] <= L:
            kyuyu[i][j] = 1
            kyuyu[j][i] = 1
kyuyu = WF(kyuyu, N)
Q = int(input())
for _ in range(Q):
    s, t = map(lambda x: int(x)-1, input().split())
    dist = kyuyu[s][t]
    if dist == float('inf'):
        print(-1)
    else:
        print(dist-1)

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


def create_graph(N, edge_pairs, is_bi_dir=False):
    in_vs, out_vs, weights = [], [], []
    for s, t, w in edge_pairs:
        in_vs.append(s)
        out_vs.append(t)
        weights.append(w)
        if is_bi_dir:
            in_vs.append(t)
            out_vs.append(s)
            weights.append(w)
    return csr_matrix((weights, (in_vs, out_vs)), shape=(N, N), dtype=np.int64)


N, M, L = map(int, input().split())
edge_pairs = []
for _ in range(M):
    s, t, w = map(int, input().split())
    edge_pairs.append((s-1, t-1, w))
graph = create_graph(N, edge_pairs, True)
dist = floyd_warshall(graph, directed=False)
edge_pairs = []
for i in range(N):
    for j in range(i+1, N):
        if dist[i][j] <= L:
            edge_pairs.append((i, j, 1))
graph = create_graph(N, edge_pairs, True)
dist = floyd_warshall(graph, directed=False)

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

Solution (Python):
n,m,L=map(int,input().split())
l=[list(map(int,input().split())) for i in range(m)]
q=int(input())
ql=[list(map(int,input().split())) for i in range(q)]
distance=[[10**18]*n for i in range(n)]
for i in range(m):
  if l[i][2]<=L:
    distance[l[i][0]-1][l[i][1]-1]=l[i][2]
    distance[l[i][1]-1][l[i][0]-1]=l[i][2]
for i in range(n):
  for j in range(n):
    for k in range(n):
      distance[j][k]=min(distance[j][k],distance[j][i]+distance[i][k])

distance2=[[10**18]*n for i in range(n)]
for i in range(n):
  for j in range(n):
    if distance[i][j]<=L:
      distance2[i][j]=1
      distance2[j][i]=1
for i in range(n):
  for j in range(n):
    for k in range(n):
      distance2[j][k]=min(distance2[j][k],distance2[j][i]+distance2[i][k])

for i in range(q):
  if distance2[ql[i][0]-1][ql[i][1]-1]>=10**18:
    print(-1)
  else:
    print(distance2[ql[i][0]-1][ql[i][1]-1]-1)

Solution (Python):

import sys
import heapq
import functools
INF = float("inf")




class Graph(object):
    def __init__(self, N):
        self.N = N
        self.E = [[] for _ in range(N)]

    def add_edge(self, s, t, w=1):
        self.E[s].append((t, w))
        self.E[t].append((s, w))


def Warshall_Floyd(g: Graph):
    N = g.N
    dist = [[INF]*N for _ in range(N)]
    for from_, toweights in enumerate(g.E):
        for to_, w in toweights:
            dist[from_][to_] = w

    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 solve(N: int,
          M: int,
          L: int,
          A: "List[int]",
          B: "List[int]",
          C: "List[int]",
          Q: int,
          s: "List[int]",
          t: "List[int]"):
    g = Graph(N)
    for i in range(M):
        g.add_edge(A[i]-1, B[i]-1, C[i])
    dist = Warshall_Floyd(g)

    g = Graph(N)
    for i in range(N):
        for j in range(i+1, N):
            if dist[i][j] <= L:
                g.add_edge(i, j, 1)
    dist = Warshall_Floyd(g)

    for i in range(Q):
        ans = dist[s[i]-1][t[i]-1]-1
        if ans == INF:
            print(-1)
        else:
            print(ans)

    return


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))
    solve(N, M, L, A, B, C, Q, s, t)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.buffer.readline
from collections import deque
N, M, L = map(int, input().split())
D = [[1<<40] * N for _ in range(N)]
for i in range(N):
    D[i][i] = 0
for _ in range(M):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    D[a][b] = c
    D[b][a] = 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])
Y = [[] for _ in range(N)]
for i in range(N):
    for j in range(N):
        if i == j: continue
        if D[i][j] <= L:
            Y[i].append(j)
def BFS(n, E, i0=0):
    Q = deque([i0])
    D = [-1] * n
    D[i0] = 0
    while Q:
        x = Q.popleft()
        for c in E[x]:
            if D[c] == -1:
                D[c] = D[x] + 1
                Q.append(c)
    return D
D2 = []
for i in range(N):
    D2.append(BFS(N, Y, i))

ans = []
for _ in range(int(input())):
    s, t = map(int, input().split())
    a = D2[s-1][t-1]-1
    ans.append(str(a if a >= 0 else -1))
print("\n".join(ans))

Solution (Python):
import sys
input = sys.stdin.buffer.readline
N, M, L = map(int, input().split())
d = [[float("inf")] * (N + 1) for _ in range(N + 1)]
for _ in range(M):
  u, v, c = map(int, input().split())
  d[u][v] = c
  d[v][u] = c
Q = int(input())
for k in range(1, N + 1):
  for i in range(1, N + 1):
    for j in range(1, N + 1):
      if d[i][j] > d[i][k] + d[k][j]:
        d[i][j] = d[i][k] + d[k][j]

nd = [[float("inf")] * (N + 1) for _ in range(N + 1)]

for i in range(1, N + 1):
  for j in range(1, N + 1):
    if d[i][j] <= L:
      nd[i][j] = 1
for k in range(1, N + 1):
  for i in range(1, N + 1):
    for j in range(1, N + 1):
      if nd[i][j] > nd[i][k] + nd[k][j]:
        nd[i][j] = nd[i][k] + nd[k][j]

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

Solution (Python):
import sys
input = sys.stdin.readline

n,m,l = map(int,input().split())
dp = [[-1]*n for _ in range(n)]
for i in range(n):
    dp[i][i] = 0

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):
            if dp[i][k] != -1 and dp[k][j] != -1:
                if dp[i][j] == -1:
                    dp[i][j] = dp[i][k] + dp[k][j]
                else:
                    dp[i][j] = min(dp[i][j],dp[i][k]+dp[k][j])

dp2 = [[-1]*n for _ in range(n)]

for i in range(n):
    for j in range(n):
        if 0 <= dp[i][j] <= l:
            dp2[i][j] = 1

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

for k in range(n):
    for i in range(n):
        for j in range(n):
            if dp2[i][k] != -1 and dp2[k][j] != -1:
                if dp2[i][j] == -1:
                    dp2[i][j] = dp2[i][k] + dp2[k][j]
                else:
                    dp2[i][j] = min(dp2[i][j],dp2[i][k]+dp2[k][j])

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

Solution (Python):
import sys
input=sys.stdin.readline
from scipy.sparse.csgraph import floyd_warshall
n,m,l=map(int,input().split())
table=[[0]*n for i in range(n)]
for i in range(m):
    a,b,c=map(int,input().split())
    table[a-1][b-1]=c
    table[b-1][a-1]=c
d=floyd_warshall(csgraph=table, directed=False, return_predecessors=False)

table2=[[0]*n for i in range(n)]
for i in range(n):
  for j in range(i+1,n):
    if d[i][j]<=l:
      table2[i][j]=1
      table2[j][i]=1
d2=floyd_warshall(csgraph=table2, directed=False, return_predecessors=False)
q=int(input())
for _ in range(q):
  s,t=map(int,input().split())
  if d2[s-1][t-1]==float("inf"):
    print(-1)
  else:
    print(int(d2[s-1][t-1])-1)

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

import queue
from collections import deque



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

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

    distance = [[10 ** 12 for i in range(node_num + 1)] for j in range(node_num + 1)]
    for i in range(1, node_num + 1):
        distance[i][i] = 0

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


    for k in range(1, node_num + 1):
        for i in range(1, node_num + 1):
            for j in range(1, node_num + 1):
                distance[i][j] = min(distance[i][k] + distance[k][j], distance[i][j])


    distance2 = [[10 ** 5 for i in range(node_num + 1)] for j in range(node_num + 1)]
    for i in range(1, node_num + 1):
        distance2[i][i] = 0

    for i in range(1, node_num + 1):
        for j in range(1, node_num + 1):
            if distance[i][j] <= max_tank:
                distance2[i][j] = 1


    for k in range(1, node_num + 1):
        for i in range(1, node_num + 1):
            for j in range(1, node_num + 1):
                distance2[i][j] = min(distance2[i][k] + distance2[k][j], distance2[i][j])

    for i in range(q_num):
        s, t = query[i]
        ans = distance2[s][t]
        if ans == 10 ** 5:
            print(-1)
        else:
            print(ans - 1)



if __name__ == '__main__':
    main()

Solution (Python):


import sys
input = sys.stdin.readline


n,m,l =map(int, input().split( ))
Edge = [[] for _ in range(n)]

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

dp = [[10**10 for _ in range(n)] for __ in range(n)]

for i in range(n):
    for ed in Edge[i]:
        dp[i][ed[0]] = ed[1]

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

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

"""
以下が要点
"""
dp2 = [[10**8 for _ in range(n)] for __ in range(n)]
for j in range(n):
    for i in range(j):
        if dp[i][j] <=l:
            dp2[i][j] = 1
            dp2[j][i] = 1
for i in range(n):
    dp2[i][i] = 1
    
for k in range(n):
    for j in range(n):
        for i in range(n):
            dp2[i][j] = min(dp2[i][j],dp2[i][k] + dp2[k][j])
"""
以上
"""
q = int(input())
ans = []
for i in range(q):
    s,t = map(int, input().split( ))
    if dp2[s-1][t-1] >10**6:
        print(-1)
    else:
        print(dp2[s-1][t-1]-1)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
import bisect
from heapq import heappush, heappop
from scipy.sparse.csgraph import floyd_warshall

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M, L = MAP()
ABC = [LIST() for _ in range(M)]
Q = INT()
st = [LIST() for _ in range(Q)]

graph1 = [[INF]*(N+1) for _ in range(N+1)]
graph2 = [[INF]*(N+1) for _ in range(N+1)]
for i in range(M):
	A, B, C = ABC[i]
	if C <= L:
		graph1[A][B] = C
		graph1[B][A] = C


graph1 = floyd_warshall(graph1, directed=False)

for i in range(N+1):
    for j in range(N+1):
        if graph1[i][j]<=L:
            graph2[i][j]=1

graph2 = floyd_warshall(graph2, directed=False)

for s, t in st:
	if graph2[s][t] == INF:
		print(-1)
	else:
		print(int(graph2[s][t])-1)

Solution (Python):
INF = float('inf')
N,M,L = map(int,input().split())
cost = [[INF]*N for _ in range(N)]
for i in range(M):
    a,b,c = map(int,input().split())
    cost[a-1][b-1] = c
    cost[b-1][a-1] = c

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

for i in range(N):
    for j in range(N):
        if cost[i][j] > L:
            cost[i][j] = INF
        else:
            cost[i][j] = 1

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

for i in range(N):
    for j in range(N):
        if cost[i][j] == INF:
            cost[i][j] = -1
        else:
            cost[i][j] -= 1

Q = int(input())

for i in range(Q):
    s,t = map(int,input().split())
    print(cost[s-1][t-1])

Solution (Python):

from scipy.sparse.csgraph import floyd_warshall
n,m,l=map(int,input().split())
table=[[0]*n for i in range(n)]
for i in range(m):
    a,b,c=map(int,input().split())
    table[a-1][b-1]=c
    table[b-1][a-1]=c
d=floyd_warshall(csgraph=table, directed=False, return_predecessors=False)

table2=[[0]*n for i in range(n)]
for i in range(n):
  for j in range(i+1,n):
    if d[i][j]<=l:
      table2[i][j]=1
      table2[j][i]=1
d2=floyd_warshall(csgraph=table2, directed=False, return_predecessors=False)
q=int(input())
for _ in range(q):
  s,t=map(int,input().split())
  if d2[s-1][t-1]==float("inf"):
    print(-1)
  else:
    print(int(d2[s-1][t-1])-1)

Solution (Python):
import sys
input = sys.stdin.buffer.readline


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

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

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


if __name__ == '__main__':
    main()

Solution (Python):
import sys

n, m, l = list(map(int, input().split()))
lines = sys.stdin.readlines()
INF = 10 ** 18

dists = [[INF] * n for _ in range(n)]

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

for line in lines[:m]:
    a, b, c = map(int, line.split())
    a -= 1
    b -= 1
    if c > l:
        continue
    dists[a][b] = c
    dists[b][a] = c

for k in range(n):
    dk = dists[k]
    for i in range(n):
        di = dists[i]
        for j in range(n):
            new_dist = di[k] + dk[j]
            if new_dist > l:
                continue
            if di[j] > new_dist:
                di[j] = new_dist

refuels = [[1 if dist < INF else INF for dist in row] for row in dists]

for k in range(n):
    rk = refuels[k]
    for i in range(n):
        ri = refuels[i]
        for j in range(n):
            new_dist = ri[k] + rk[j]
            if ri[j] > new_dist:
                ri[j] = new_dist

buf = []

for line in lines[m + 1:]:
    s, t = map(int, line.split())
    refuel = refuels[s - 1][t - 1]
    buf.append(-1 if refuel == INF else refuel - 1)

print('\n'.join(map(str, buf)))

Solution (Python):
import sys
n, m, l = map(int, sys.stdin.readline().split())
d = [[10**15] * (n+1) for _ in range(n+1)]
for i in range(n+1):
    d[i][i] = 0
for i in range(m):
    a, b, c = map(int, sys.stdin.readline().split())
    if c > l:
        continue
    d[a][b] = c
    d[b][a] = c

q = int(input())
qs = []
for i in range(q):
    s,t = map(int, sys.stdin.readline().split())
    qs.append([s, t])

for k in range(n+1):
    for i in range(n+1):
        for j in range(n+1):
            if d[i][k] + d[k][j] < d[i][j]:
                d[i][j] = d[i][k] + d[k][j]

for i in range(n+1):
    for j in range(n+1):
        if d[i][j] == 0:
            d[i][j] = 0
        elif d[i][j] <= l:
            d[i][j] = 1
        else:
            d[i][j] = 10**15
for k in range(n+1):
    for i in range(n+1):
        for j in range(n+1):
            if d[i][k] + d[k][j] < d[i][j]:
                d[i][j] = d[i][k] + d[k][j]
for i in range(q):
    st = qs[i][0]
    gl = qs[i][1]
    if d[st][gl] == 10**15:
        print(-1)
    else:
        print(d[st][gl]-1)

Solution (Python):
from scipy.sparse.csgraph import floyd_warshall
import sys
input = sys.stdin.readline

N, M, L = map(int, input().split())
INF = float('inf')
graph = [[INF] * N for _ in range(N)]

for i in range(N):
    graph[i][i] = 0

for _ in range(M):
    A, B, C = map(int, input().split())
    A, B = A - 1, B - 1
    if C <= L:
        graph[A][B] = C
        graph[B][A] = C

distance = floyd_warshall(graph, directed=False)

graph = [[INF] * N for _ in range(N)]
for i in range(N):
    for j in range(N):
        if distance[i][j] <= L:
            graph[i][j] = 1

supply = floyd_warshall(graph, directed=False)


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

Solution (Python):
n,m,l=map(int,input().split())
INF=10**10
graph=[[INF for i in range(n)] for j in range(n)]
fuel=[[INF for i in range(n)] for j in range(n)]
for i in range(n):
    graph[i][i]=0
for i in range(m):
    a,b,c=map(int,input().split())
    a-=1;b-=1
    if c>l:continue
    graph[a][b],graph[b][a]=c,c
for i in range(n):
  for j in range(n):
    for k in range(n):
      graph[j][k]=min(graph[j][k],graph[j][i]+graph[i][k])
for i in range(n):
    for j in range(n):
        if graph[i][j]<=l:
            fuel[i][j]=1
for i in range(n):
  for j in range(n):
    for k in range(n):
      fuel[j][k]=min(fuel[j][k],fuel[j][i]+fuel[i][k])
q=int(input())
for i in range(q):
    s,t=map(int,input().split())
    s-=1;t-=1
    if fuel[s][t]==INF:print(-1)
    else:print(fuel[s][t]-1)

Solution (Python):
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[]]*num
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))



import copy

N,M,L = II()
A,B,C = Line(M,3)
Q = I()
s,t = Line(Q,2)

E = [[float('inf')]*N for _ in range(N)]
for i in range(N):
    E[i][i] = 0
for i in range(M):
    E[A[i]-1][B[i]-1] = C[i]
    E[B[i]-1][A[i]-1] = C[i]

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

E2 = [[float('inf')]*N for _ in range(N)]

for i in range(N):
    E2[i][i] = 0
for i in range(N):
    for j in range(N):
        if E[i][j]<=L:
            E2[i][j] = 1
            E2[j][i] = 1

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

for i in range(Q):
    if E2[s[i]-1][t[i]-1] == float('inf'):
        print(-1)
    else:
        print(E2[s[i]-1][t[i]-1]-1)

Solution (Python):
import os
import sys

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

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N, M, L = list(map(int, sys.stdin.readline().split()))
ABC = [list(map(int, sys.stdin.readline().split())) for _ in range(M)]
Q = int(sys.stdin.readline())
S, T = list(zip(*[map(int, sys.stdin.readline().split()) for _ in range(Q)]))

D = np.full((N, N), 0)
for a, b, c in ABC:
    D[a - 1][b - 1] = c
    D[b - 1][a - 1] = c

floyd_warshall(D, directed=False, overwrite=True)
counts = floyd_warshall(D <= L, directed=False, unweighted=True)
S = np.array(S, dtype=int) - 1
T = np.array(T, dtype=int) - 1

ans = counts[S, T] - 1
ans[ans == np.inf] = -1
print(*ans.astype(int), sep='\n')

Solution (Python):
def main():
	from scipy.sparse.csgraph import floyd_warshall
	import numpy as np
	n, m, l, *L = map(int, open(0).read().split())
	abc = L[:3 * m];
	st = L[3 * m + 1:]
	r = [[float("inf")] * n for _ in range(n)]
	for a, b, c in zip(*[iter(abc)] * 3):
		if c <= l: r[a - 1][b - 1] = c
	fw = floyd_warshall(r, 0)
	ans = floyd_warshall(np.where(fw <= l, 1, fw), 0) - 1
	for s, t in zip(*[iter(st)] * 2):
		x = ans[s - 1, t - 1]
		if x == float("inf"):
			print(-1)
		else:
			print(int(x))


if __name__ == "__main__":
	main()

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

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

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




A= floyd_warshall(A,directed = False)

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


B= floyd_warshall(B,directed = False)
"""for c in range(1,N+1):
    for a in range(1,N+1):
        for b in range(1,N+1):
            B[a][b]=min(B[a][b],B[a][c]+B[c][b])"""


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

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

import numpy as np

N,M,L = map(int,readline().split())
ABCPST = np.array(read().split(),np.int64)
ABC = ABCPST[:M+M+M]
A = ABC[::3]; B = ABC[1::3]; C = ABC[2::3]
ST = ABCPST[M+M+M+1:]
S = ST[::2]; T = ST[1::2]


graph = csr_matrix((C,(A,B)),(N+1,N+1))
dist_mat = floyd_warshall(graph,directed=False)



graph2 = np.full((N+1,N+1),np.inf)
np.fill_diagonal(graph2,0)
graph2[dist_mat<=L+.5] = 1

dist_mat2 = floyd_warshall(graph2,directed=False)

dist_mat2[dist_mat2 == np.inf] = 0
dist_mat2 = (dist_mat2+.5).astype(int)

x = dist_mat2[S,T] - 1

print('\n'.join(x.astype(str)))

Solution (Python):
from collections import deque
import sys
import random
input = sys.stdin.readline


n, m, l = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]
graph = [[] for i in range(n)]

for i in range(m):
    a, b, cost = info[i]
    if cost > l:
        continue
    a -= 1
    b -= 1
    graph[a].append((b, cost))
    graph[b].append((a, cost))

for i in range(n):
    graph[i] = random.sample(graph[i], len(graph[i]))
    
def dfs(start):
    INF = float("inf")
    visited_t = [INF]*n 
    visited_l = [0]*n
    visited_t[start] = 0
    q = deque([start])
    while q:
        pos = q.popleft()
        for next_pos, cost in graph[pos]:
            tmp = cost + visited_l[pos]
            times = visited_t[pos]
            next_times = visited_t[next_pos]
            if tmp <= l:
                if next_times > times:
                    q.append(next_pos)
                    visited_t[next_pos] = times
                    visited_l[next_pos] = tmp
                elif next_times == times:
                    if visited_l[next_pos] > tmp:
                        q.append(next_pos)
                        visited_t[next_pos] = times
                        visited_l[next_pos] = tmp
                else:
                    continue
            else:
                tmp = cost
                if next_times > times + 1:
                    q.append(next_pos)
                    visited_t[next_pos] = times + 1
                    visited_l[next_pos] = tmp
                elif next_times == times + 1:
                    if visited_l[next_pos] > tmp:
                        q.append(next_pos)
                        visited_t[next_pos] = times + 1
                        visited_l[next_pos] = tmp
                else:
                    continue
    return visited_t

ans = [None]*n
for i in range(n):
    ans[i] = dfs(i)

INF = float("inf")
q = int(input())
query = [list(map(int, input().split())) for i in range(q)]
for i in range(q):
    a, b = query[i]
    a -= 1
    b -= 1
    tmp = ans[a][b]
    if tmp == INF:
        print(-1)
    else:
        print(tmp)

Solution (Python):
from collections import defaultdict, deque
import sys
input = sys.stdin.readline

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

start = defaultdict(lambda : [])
for i in range(Q) :
    s, t = map(int, input().split())
    start[s-1].append((t-1, i))

INF = N * N
ret = [-1] * Q
for s, d in start.items() :
    
    pre1 = [-1] * N
    pre2 = [INF] * N
    pre1[s] = L 
    pre2[s] = 0 
    queue = deque([(s, L, 0)])
    
    while queue :
        
        cur, rest, cost = queue.popleft()
        if pre2[cur] < cost or (pre2[cur] == cost and pre1[cur] > rest):
            continue
            
        for nex, c in v[cur] :
            if rest >= c :
                nrest = rest - c
                ncost = cost
            else :
                nrest = L - c
                ncost = cost + 1
                
            if ncost < pre2[nex] or (ncost == pre2[nex] and nrest > pre1[nex]) :                    
                queue.append((nex, nrest, ncost))
                pre1[nex] = nrest
                pre2[nex] = ncost
                
    
    
    
    
    for dest, i in d :
        if pre1[dest] == -1 :
            ret[i] = -1
        else :
            ret[i] = pre2[dest]
        
for r in ret :
    print(r)

Solution (Python):
n,m,l = map(int,input().split())
road = [[10**18 for _ in range(n)] for _ in range(n)]
for _ in range(m):
  a,b,c = map(int,input().split())
  a -= 1
  b -= 1
  road[a][b] = c
  road[b][a] = c

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

cango = [[1000 for _ in range(n)] for _ in range(n)]
for i in range(n):
  for j in range(n):
    if road[i][j] == 0:
      cango[i][j] = 0
    elif road[i][j] <= l:
      cango[i][j] = 1

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

q = int(input())
for _ in range(q):
  s,t = map(int,input().split())
  ans = cango[s-1][t-1]-1
  if ans > 500:
    print(-1)
  else:
    print(ans)

Solution (Python):
import sys

sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return list(map(int, sys.stdin.readline().split()))
def II(): return int(sys.stdin.readline())
def LS(): return list(map(list, sys.stdin.readline().split()))


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():
    n, m, l = LI()
    mem = [[INF for _ in range(n)] for _ in range(n)]
    for i in range(m):
        a, b, c = LI()
        mem[a-1][b-1] = c
        mem[b-1][a-1] = c
    for i in range(n):
        mem[i][i] = 0
    mem = warshall_floyd(mem, n)
    new_mem = [[INF for _ in range(n)] for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if mem[i][j] <= l:
                new_mem[i][j] = 1

    new_mem = warshall_floyd(new_mem, n)
    q = II()
    for i in range(q):
        s, t = LI()
        print(new_mem[s-1][t-1] - 1 if new_mem[s-1][t-1] < INF else -1)


if __name__ == '__main__':
    main()