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

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

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

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

inf=L+1
dist=[[inf]*N for i in range(N)]
for i in range(N):
    dist[i][i]=0
for A,B,C in ABC:
    dist[A-1][B-1]=min(dist[A-1][B-1],C)
    dist[B-1][A-1]=min(dist[B-1][A-1],C)

dist=Warshall_Floyd(N,dist)
dist_2=[[N+1]*N for i in range(N)]

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

dist_2=Warshall_Floyd(N,dist_2)

for s,t in st:
    if dist_2[s-1][t-1]==N+1:
        print(-1)
    else:
        print(dist_2[s-1][t-1]-1)

Solution (Python):
n,m,l = map(int,input().split())
abe = [list(map(int,input().split())) for i in range(m)]
dist = [[10**18 for i in range(n)] for i in range(n)]
for a,b,e in abe:
  dist[a-1][b-1] = e
  dist[b-1][a-1] = e
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])
for i in range(n):
  for j in range(n):
    if dist[i][j] <= l:
      dist[i][j] = 1
    else:
      dist[i][j] = 10**18
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])
q = int(input())
for i in range(q):
  s,t = map(int,input().split())
  x = dist[s-1][t-1]-1
  if x == 10**18-1:
    print(-1)
  else:
    print(x)

Solution (Python):
import sys
import numpy as np
from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall, shortest_path

input = sys.stdin.readline

def main():
    n, m, l = map(int, input().split())
    wf = [[0 for i in range(n)] for j in range(n)]
    for _ in range(m):
        a, b, c = map(int, input().split())
        wf[a-1][b-1] = wf[b-1][a-1] = c
    wf = np.array(wf)
    for i in range(n):
        wf[i][i] = 0
    wf = shortest_path(wf, method='FW')
    for i in range(n):
        for j in range(n):
            if wf[i][j] <= l:
                wf[i][j] = 1
            else:
                wf[i][j] = 301
    wf = shortest_path(wf, method='FW')
    q = int(input())
    ans = [None] * q
    for i in range(q):
        s, t = map(int, input().split())
        if wf[s-1][t-1] < 301:
            ans[i] = int(wf[s-1][t-1])
        else:
            ans[i] = 0
    for i in range(q):
        print(ans[i] - 1)

if __name__ == "__main__":
    main()

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def IS(): return sys.stdin.readline()[:-1]
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LII(rows_number): return [II() for _ in range(rows_number)]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]

def main():
	N,M,L = MI()
	to = [[] for _ in range(N)]
	dist = [[float("inf") for _ in range(N)] for _ in range(N)]

	def warshall_floyd(N):
		for mid in range(N):
			for s in range(N):
				for g in range(s+1,N):
					dist[s][g] = min(dist[s][g], dist[s][mid]+dist[mid][g])
					dist[g][s] = dist[s][g]


	for _ in range(M):
		a,b,c = MI()
		dist[a-1][b-1],dist[b-1][a-1]=c,c
	for i in range(N):
		dist[i][i] = 0

	warshall_floyd(N)

	for i in range(N):
		for j in range(i+1,N):
			if dist[i][j]<=L :
				dist[i][j],dist[j][i]=1,1
			else:
				dist[i][j],dist[j][i]=float("inf"),float("inf")

	warshall_floyd(N)

	Q = II()
	for _ in range(Q):
		s,t = MI()
		ans = dist[s-1][t-1]-1
		if(ans == float("inf")):
			print(-1)
		else:
			print(ans)

main()

Solution (Python):
import sys


INF = 1 << 32 - 1
S = sys.stdin.readlines()
N, M, L = map(int, S[0].split())

dp = [[INF] * N for _ in range(N)]

for i in range(1, M + 1):
    A, B, C = map(int, S[i].split())
    dp[A - 1][B - 1] = C
    dp[B - 1][A - 1] = C
for i in range(N):
    dp[i][i] = 0

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


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

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


Q = int(S[M + 1])
for i in range(M + 2, M + 2 + Q):
    s, t = map(int, S[i].split())
    refuel = dp2[s - 1][t - 1]
    if refuel >= 10 ** 3:
        print(-1)
    else:
        print(refuel - 1)

Solution (Python):
import sys


INF = 1 << 32 - 1
S = sys.stdin.readlines()
N, M, L = map(int, S[0].split())

dp = [[INF] * N for _ in range(N)]

for i in range(1, M + 1):
    A, B, C = map(int, S[i].split())
    dp[A - 1][B - 1] = C
    dp[B - 1][A - 1] = C
for i in range(N):
    dp[i][i] = 0

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


dp2 = [[INF] * N for _ in range(N)]
for i in range(N):
    for j in range(N):
        if dp[i][j] <= L:
            dp2[i][j] = 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])


Q = int(S[M + 1])
for i in range(M + 2, M + 2 + Q):
    s, t = map(int, S[i].split())
    refuel = dp2[s - 1][t - 1]
    if refuel >= 10 ** 3:
        print(-1)
    else:
        print(refuel - 1)

Solution (Python):
import sys


INF = 1 << 32 - 1
S = sys.stdin.readlines()
N, M, L = map(int, S[0].split())

dp = [[INF] * N for _ in range(N)]

for i in range(1, M + 1):
    A, B, C = map(int, S[i].split())
    dp[A - 1][B - 1] = C
    dp[B - 1][A - 1] = C
for i in range(N):
    dp[i][i] = 0

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


dp2 = [[INF] * N for _ in range(N)]
for i in range(N):
    for j in range(N):
        if dp[i][j] <= L:
            dp2[i][j] = 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])


Q = int(S[M + 1])
for i in range(M + 2, M + 2 + Q):
    s, t = map(int, S[i].split())
    refuel = dp2[s - 1][t - 1]
    if refuel >= INF:
        print(-1)
    else:
        print(refuel - 1)

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


def main():
    N, M, L = map(int, input().split())
    graph = [[0] * N for _ in range(N)]
    for _ in range(M):
        s, t, w = map(int, input().split())
        if w <= L:
            graph[s-1][t-1] = graph[t-1][s-1] = w
    graph = floyd_warshall(graph, directed=False)
    graph = floyd_warshall(graph <= L, directed=False)
    graph[np.isinf(graph)] = 0

    Q = int(input())
    ans = []
    for _ in range(Q):
        s, t = map(int, input().split())
        ans.append(int(graph[s-1][t-1]) - 1)
    print(*ans, sep='\n')


if __name__ == '__main__':
    main()

Solution (Python):
import sys

sys.setrecursionlimit(500000)
def input():
    return sys.stdin.readline()[:-1]

def main():
    N,M,L = list(map(int,input().split()))
    e_list = [[] for i in range(N)]
    for i in range(M):
        A,B,C = list(map(int,input().split()))
        A,B = A-1,B-1
        e_list[A].append((B,C))
        e_list[B].append((A,C))

    INF = float('inf')
    D = [[INF]*N for i in range(N)]
    for i in range(N):
        for j,d in e_list[i]:
            D[i][j]=d

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

    E = [[INF]*N for i in range(N)]

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

    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]

    Q = int(input())
    for i in range(Q):
        s,t = list(map(int,input().split()))
        s,t = s-1,t-1
        if E[s][t]>10**28:
            print(-1)
        else:
            print(E[s][t]-1)
            
if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline
N, m, l = map(int, input().split())
graph = [[] for i in range(N+1)]

INF = 2 ** 31 - 1
d = [[INF for i in range(N+1)] for j in range(N+1)]
for i in range(N+1):
    d[i][i] = 0
for i in range(m):
    a, b, c = map(int, input().split())
    d[a][b] = c
    d[b][a] = c


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

d2 = [[INF for i in range(N+1)] for j in range(N+1)]
for i in range(N+1):
    d[i][i] = 0

for i in range(N+1):
    for j in range(N+1):
        if d[i][j] <= l:
            d2[i][j] = 1

for k in range(N+1):
    for i in range(N+1):
        for j in range(N+1):
            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][t] == INF:
        print(-1)
    else:
        print(d2[s][t] - 1)

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

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

D = np.ones([N, N]) * np.inf
D[np.eye(N, dtype=bool)] = 0

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

D = floyd_warshall(D)
D2 = (D<=L)*1.0 
D2[D2==0] = np.inf


D2 = floyd_warshall(D2) - 1

Q = int(input())
for _ in range(Q):
  s, t = map(int, input().split())
  r = D2[s-1, t-1]
  if r < np.inf:
    print(int(r))
  else:
    print(-1)

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

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

def main():
  n, m, l = map(int, input().split())
  F = np.zeros((n, n))
  for _ in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    F[a, b] = c
    F[b, a] = c
  csr = csr_matrix(F)
  A = floyd_warshall(csr)
  G = np.zeros((n, n))
  for i in range(n-1):
    for j in range(i+1, n):
      if A[i][j] <= l:
        G[i, j] = 1
        G[j, i] = 1
  ncsr = csr_matrix(G)
  B =  floyd_warshall(ncsr)
  q = int(input())
  for _ in range(q):
    s, t = map(int, input().split())
    k = B[s-1][t-1]
    if k == float("inf"):
      print(-1)
    else:
      print(int(k)-1)
      
if __name__ == "__main__":
  main()

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())
F = np.zeros((n, n))
for _ in range(m):
  a, b, c = map(int, input().split())
  a -= 1
  b -= 1
  F[a, b] = c
  F[b, a] = c
csr = csr_matrix(F)
A = floyd_warshall(csr)
G = np.zeros((n, n))
for i in range(n-1):
  for j in range(i+1, n):
    if A[i][j] <= l:
      G[i, j] = 1
      G[j, i] = 1
ncsr = csr_matrix(G)
B =  floyd_warshall(ncsr)
q = int(input())
for _ in range(q):
  s, t = map(int, input().split())
  k = B[s-1][t-1]
  if k == float("inf"):
    print(-1)
  else:
    print(int(k)-1)

Solution (Python):
import sys
import math
import heapq
sys.setrecursionlimit(10**7)
INTMAX = 9323372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) 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 II(): return int(sys.stdin.readline())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res

N,M,L=LI()

LG=10**15
DIST=[[LG for _ in range(N+1)] for _ in range(N+1)]
for i in range(M):
    a,b,c = LI()
    if c <= L:
        DIST[a][b] = c
        DIST[b][a] = c

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

for i in range(1, N+1):
    for j in range(1, N+1):
        DIST[i][j] = 1 if DIST[i][j] <= L else LG

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

for i in range(II()):
    st, en = LI()
    if DIST[st][en] >= LG:
        print(-1)
    else:
        print(DIST[st][en] - 1)

Solution (Python):
import sys
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True 
BIG = 9999999999

def ddprint(x):
  if DBG:
    print(x)

def ws(dist):
    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])

n,m,l = inm()
dst = [ [] for i in range(n) ]
for i in range(m):
    a,b,c = inm()
    dst[a-1].append((b-1,c))
    dst[b-1].append((a-1,c))

dist1 = [ [BIG]*n for i in range(n) ]
for i in range(n):
    dist1[i][i] = 0
    for j,c in dst[i]:
        dist1[i][j] = c

ws(dist1)

dist2 = [ [BIG]*n for i in range(n) ]
for i in range(n):
    dist2[i][i] = 0
    for j in range(n):
        if dist1[i][j] <= l:
            dist2[i][j] = 1

ws(dist2)

q = inn()
for i in range(q):
    s,t = inm()
    d = dist2[s-1][t-1]
    print(d-1 if d<BIG else -1)

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


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

graph = floyd_warshall(graph)
another = [[float('inf')]*N for _ in range(N)]
for i in range(N):
    for j in range(N):
        if graph[i][j] <= L:
            another[i][j] = 1
another = floyd_warshall(another)
Q = int(input())
for _ in range(Q):
    s, t = map(lambda x: int(x)-1, input().split())
    if another[s][t] == float('inf'):
        print(-1)
    else:
        print(int(another[s][t])-1)

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


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

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

distant = floyd_warshall(distant)
another = [[float('inf')]*N for _ in range(N)]
for i in range(N):
    for j in range(N):
        if distant[i][j] <= L:  
            another[i][j] = 1
another = floyd_warshall(another)
Q = int(input())
for _ in range(Q):
    s, t = map(lambda x: int(x)-1, input().split())
    if another[s][t] == float('inf'):
        print(-1)
        continue
    print(int(another[s][t])-1)

Solution (Python):
def warshall_floyd(v_count: int, matrix: list) -> list:
    """ ワーシャルフロイド
    v_count: 頂点数
    matrix: 隣接行列(到達不能はfloat("inf"))
    """
    for i in range(v_count):
        for j, c2 in enumerate(row[i] for row in matrix):
            for k, (c1, c3) in enumerate(zip(matrix[j], matrix[i])):
                if c1 > c2+c3:
                    matrix[j][k] = c2+c3
    return matrix


INF = 10 ** 16
n, m, l = map(int, input().split())
mat = [[INF] * n for _ in range(n)]
for i in range(n):
    mat[i][i] = 0
for _ in range(m):
    a, b, c = map(int, input().split())
    mat[a - 1][b - 1] = c
    mat[b - 1][a - 1] = c
mat = warshall_floyd(n, mat)
fuel_mat = [[INF] * n for _ in range(n)]
for i in range(n):
    for j in range(n):
        if i == j:
            fuel_mat[i][j] = 0
        elif mat[i][j] <= l:
            fuel_mat[i][j] = 1
fuel_mat = warshall_floyd(n, fuel_mat)
q = int(input())
for _ in range(q):
    s, t = map(int, input().split())
    d = fuel_mat[s - 1][t - 1]
    if d == INF:
        print(-1)
    else:
        print(d - 1)

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
INF=10**18
def input():
    return sys.stdin.readline().rstrip()

def main():
    N,M,L=map(int,input().split())
    d=[[INF]*N for _ in range(N)]
    for _ in range(M):
        A,B,C=map(lambda x:int(x)-1,input().split())
        d[A][B]=C+1
        d[B][A]=C+1
    Q=int(input())
    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=[[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])
    for _ in range(Q):
        s,t=map(lambda x:int(x)-1,input().split())
        dist=d2[s][t]
        if dist>=INF:
            print(-1)
        else:
            print(dist-1)
            
if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline
N,M,L=map(int,input().split())

def war(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
INF=(L+1)*N
d=[[INF]*N for _ in range(N)]
d2=[[INF]*N for _ in range(N)]

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

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

d=war(d)

for i in range(N):
    for j in range(N):
        if d[i][j]<=L:
            d2[i][j]=1
for i in range(N):
    d2[i][i]=0
d2=war(d2)


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

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

N, M, L = map(int, input().split())
INF = 10 **9 +1
G = [[float('inf')] * N for i in range(N)]
for i in range(M):
  a, b, c = map(int, input().split())
  a, b, = a - 1, b -1
  G[a][b] = c
  G[b][a] = c


G = floyd_warshall(G)



E = [[float('inf')] * N for i in range(N)]
for i in range(N):
  for j in range(N):
    if G[i][j] <= L:
      E[i][j] = 1


E = floyd_warshall(E)


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

Solution (Python):
from math import isinf
from scipy.sparse.csgraph import shortest_path
from scipy.sparse import csr_matrix

INF = float('inf')

def main():
    N, M, L = list(map(int, input().split()))
    E = [[INF] * N for _ in range(N)]
    for _ in range(M):
        a, b, c = list(map(int, input().split()))
        E[a - 1][b - 1] = c
        E[b - 1][a - 1] = c
    EE = shortest_path(csr_matrix(E))
    E = [[1 if EE[i][j] <= L else INF for j in range(N)] for i in range(N)]
    EE = shortest_path(csr_matrix(E))
    Q = int(input())
    for _ in range(Q):
        s, t = map(int, input().split())
        x = EE[s - 1][t - 1]
        print(-1 if isinf(x) else int(x) - 1)
        

main()

Solution (Python):
def main():
    from sys import stdin
    input=stdin.readline
    
    import numpy as np
    import scipy.sparse.csgraph as sp

    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 = np.full((n, n), inf, dtype=np.int64)
    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
    dist = sp.shortest_path(dist)

    inf = 10**3
    dist2 = np.full((n, n), inf, dtype=np.int16)
    for i in range(n):
        for j in range(n):
            if dist[i][j] <= l:
                dist2[i][j] = 1
    dist2 = sp.shortest_path(dist2)

    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(int(dist2[s-1][t-1]))


main()

Solution (Python):


import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().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

n,m,l = LI()

dist = [[inf]*n for _ in range(n)]
dist2 = [[inf]*n for _ in range(n)]

for i in range(n):
    dist[i][i] = 0
    dist2[i][i] = 0
for _ in range(m):
    a,b,c = LI()
    dist[a-1][b-1] = c
    dist[b-1][a-1] = c

dist = warshall_floyd(dist)

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

dist2 = warshall_floyd(dist2)
q = I()
ans = []
for _ in range(q):
    s,t = LI()
    if dist2[s-1][t-1] == inf:
        print(-1)
    else:
        print(dist2[s-1][t-1]-1)

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

inf = 10 ** 13 + 1

n, m, l = list(map(int, input().split()))
way = [[inf for i in range(n)] for j in range(n)]
oil = [[400 for i in range(n)] for j in range(n)]

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

q = int(input())

query = []

for i in range(q):
    query.append(list(map(int, input().split())))


for k in range(n):
    for i in range(n):
        for j in range(n):
            if i == j:
                way[i][j] = 0
                continue
            way[i][j] = min(way[i][j],way[i][k] + way[k][j])
            

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

for k in range(n):
    for i in range(n):
        for j in range(n):
            if i == j:
                oil[i][j] = 0
                continue
            oil[i][j] = min(oil[i][j],oil[i][k] + oil[k][j])

for i in range(q):
    ans = oil[query[i][0] - 1][query[i][1] - 1] - 1
    if way[query[i][0] - 1][query[i][1] - 1] == inf or oil[query[i][0] - 1][query[i][1] - 1] == 400:
        ans = -1
    print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n,m,L=map(int,input().split())
    E=[[] for _ in range(n)]
    for _ in range(m):
        u,v,w=map(int,input().split())
        if(w>L): continue
        u-=1; v-=1
        E[u].append((v,w))
        E[v].append((u,w))

    
    
    A=[None]*n
    for s in range(n):
        dist=[(INF,INF)]*n
        dist[s]=(0,0)
        used=[0]*n
        for _ in range(n-1):
            v=min((dist[v],v) for v in range(n) if(not used[v]))[1]
            used[v]=1
            c,l=dist[v]
            for nv,w in E[v]:
                if(l+w>L):
                    nd=(c+1,w)
                else:
                    nd=(c,l+w)
                dist[nv]=min(dist[nv],nd)
        A[s]=dist

    for _ in range(int(input())):
        s,t=map(int,input().split())
        s-=1; t-=1
        res=A[s][t][0]
        print(res if(res!=INF) else -1)
resolve()

Solution (Python):

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

INF = 1<<30
dp = [[INF]*N for _ in range(N)]

for a,b,c in ABC:
    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])
        
d = [[INF]*N for _ in range(N)]
for i in range(N):
    for j in range(N):
        if dp[i][j]<=L:
            d[i][j] = 1
        
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])
        
for s,t in st:
    if d[s-1][t-1]!=INF:
        print(d[s-1][t-1]-1)
    else:
        print(-1)

Solution (Python):
import sys
import numpy as np
from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall, csgraph_to_dense
from scipy.sparse import issparse
sys.setrecursionlimit(10**7)

n, m, l = [int(i) for i in sys.stdin.readline().split()]
graph = [[0 for i in range(n)] for j in range(n)]
for i in range(m):
    a, b, c = [int(i) for i in sys.stdin.readline().split()]
    a -= 1
    b -= 1
    graph[a][b] = c
    graph[b][a] = c

res = floyd_warshall(csgraph_from_dense(graph))
if issparse(res):
    res = csgraph_to_dense(res)
res = np.where(res <= l, 1, 0)
new_res = floyd_warshall(res)
new_res[new_res == np.inf] = 0
q = int(input())
for j in range(q):
    s, t = [int(i) for i in sys.stdin.readline().split()]
    s -= 1
    t -= 1
    dis = new_res[s, t]
    print(int(dis) - 1)

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

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

D = np.ones([N, N]) * np.inf
D[np.eye(N, dtype=bool)] = 0

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

D = floyd_warshall(D)
D2 = D <= L

D2 = floyd_warshall(D2)

Q = int(input())
for _ in range(Q):
  s, t = map(int, input().split())
  r = D2[s-1, t-1] - 1
  if r < np.inf:
    print(int(r))
  else:
    print(-1)

Solution (Python):











import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log 
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    
    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])
    
    N,M,L=MI()
    ABC=LLIN(M)
    d=[[float("inf")] * N for i in range(N)]
    for i in range(N):
        d[i][i] = 0
    
    for a,b,c in ABC:
        a-=1
        b-=1
        d[a][b]=c
        d[b][a]=c

    warshall_floyd(d,N)

    D=[[float("inf")] * N for i in range(N)]
    for i in range(N):
        for j in range(N):
            if d[i][j]<=L:
                D[i][j] = 1
        
    warshall_floyd(D,N)

    Q=I()
    ST=LLIN_(Q)
    for s,t in ST:
        if D[s][t]==inf:
            print(-1)
        else:
            print(D[s][t]-1)
    

if __name__ == '__main__':
    main()

Solution (Python):
import sys


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    wn, wm, l = list(map(int, readline().split()))
    inf = 10 ** 13
    wl = [[inf] * wn for _ in range(wn)]
    for i in range(wn):
        wl[i][i] = 0

    for i in range(wm):
        wa, wb, wc = list(map(int, readline().split()))
        wl[wa - 1][wb - 1] = wc
        wl[wb - 1][wa - 1] = wc

    for i in range(wn):
        for j in range(wn):
            for k in range(wn):
                wl[j][k] = min(wl[j][k], wl[j][i] + wl[i][k])

    inf = 10 ** 13
    wwl = [[inf] * wn for _ in range(wn)]
    for i in range(wn):
        wwl[i][i] = 0

    for i in range(wn):
        for j in range(wn):
            if i != j and wl[i][j] <= l:
                wwl[i][j] = 1

    for i in range(wn):
        for j in range(wn):
            for k in range(wn):
                wwl[j][k] = min(wwl[j][k], wwl[j][i] + wwl[i][k])
    q = int(readline())
    for i in range(q):
        s, t = list(map(int, readline().split()))
        print(wwl[s-1][t-1] - 1 if wwl[s-1][t-1] != inf else -1)


if __name__ == '__main__':
    solve()