Problem:


Score : 500 points

Problem Statement

There are N towns numbered 1 to N and M roads. The i-th road connects Town A_i and Town B_i bidirectionally and has a length of C_i.

Takahashi will travel between these towns by car, passing through these roads. The fuel tank of his car can contain at most L liters of fuel, and one liter of fuel is consumed for each unit distance traveled. When visiting a town while traveling, he can full the tank (or choose not to do so). Travel that results in the tank becoming empty halfway on the road cannot be done.

Process the following Q queries:

The tank is now full. Find the minimum number of times he needs to full his tank while traveling from Town s_i to Town t_i. If Town t_i is unreachable, print -1.

Constraints

All values in input are integers.

2 \leq N \leq 300

0 \leq M \leq \frac{N(N-1)}{2}

1 \leq L \leq 10^9

1 \leq A_i, B_i \leq N

A_i \neq B_i

\left(A_i, B_i\right) \neq \left(A_j, B_j\right) (if i \neq j)

\left(A_i, B_i\right) \neq \left(B_j, A_j\right) (if i \neq j)

1 \leq C_i \leq 10^9

1 \leq Q \leq N\left(N-1\right)

1 \leq s_i, t_i \leq N

s_i \neq t_i

\left(s_i, t_i\right) \neq \left(s_j, t_j\right) (if i \neq j)

Input

Input is given from Standard Input in the following format:

N M L
A_1 B_1 C_1
:
A_M B_M C_M
Q
s_1 t_1
:
s_Q t_Q

Output

Print Q lines.

The i-th line should contain the minimum number of times the tank needs to be fulled while traveling from Town s_i to Town t_i. If Town t_i is unreachable, the line should contain -1 instead.

Sample Input 1

3 2 5
1 2 3
2 3 3
2
3 2
1 3

Sample Output 1

0
1

To travel from Town 3 to Town 2, we can use the second road to reach Town 2 without fueling the tank on the way.

To travel from Town 1 to Town 3, we can first use the first road to get to Town 2, full the tank, and use the second road to reach Town 3.

Sample Input 2

4 0 1
1
2 1

Sample Output 2

-1

There may be no road at all.

Sample Input 3

5 4 4
1 2 2
2 3 2
3 4 3
4 5 2
20
2 1
3 1
4 1
5 1
1 2
3 2
4 2
5 2
1 3
2 3
4 3
5 3
1 4
2 4
3 4
5 4
1 5
2 5
3 5
4 5

Sample Output 3

0
0
1
2
0
0
1
2
0
0
0
1
1
1
0
0
2
2
1
0



Sample input:
3 2 5
1 2 3
2 3 3
2
3 2
1 3


Sample output:
0
1

Submission status: Accepted

Solution code:
import sys

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


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

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

    paths = floyd_warshall(paths)
    paths = floyd_warshall(paths <= le)
    paths[np.isinf(paths)] = 0

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

    print(*answer, sep='\n')
    #print("\n".join(map(str, answer)))


if __name__ == "__main__":
    solve()

Submission status: Accepted

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


def use_fast_io():
    global input
    import io
    import sys
    f = io.BytesIO(sys.stdin.buffer.read())
    input = f.readline


use_fast_io()


def solve():
    n, m, le = map(int, input().split())
    g1 = (le + 1) * np.zeros((n, n))
    for _ in range(m):
        a, b, c = map(int, input().split())
        if c <= le:
            g1[a - 1, b - 1] = c
            g1[b - 1, a - 1] = c

    fw1 = floyd_warshall(g1, directed=False)

    g2 = 1000 * np.zeros((n, n))
    g2[fw1 <= le] = 1

    fw2 = floyd_warshall(g2, directed=False)

    q = int(input())
    res_list = [-1] * q
    for i in range(q):
        s, t = map(int, input().split())
        res = fw2[s - 1, t - 1]
        if res <= n:
            res_list[i] = int(res - 1)

    for r in res_list:
        print(r)


if __name__ == "__main__":
    solve()

Submission status: Accepted

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

input = sys.stdin.readline


def solve():
    n, m, le = map(int, input().split())
    g1 = (le + 1) * np.zeros((n, n))
    for _ in range(m):
        a, b, c = map(int, input().split())
        if c <= le:
            g1[a - 1, b - 1] = c
            g1[b - 1, a - 1] = c

    fw1 = floyd_warshall(g1, directed=False)

    g2 = 1000 * np.zeros((n, n))
    g2[fw1 <= le] = 1

    fw2 = floyd_warshall(g2, directed=False)

    q = int(input())
    res_list = [-1] * q
    for i in range(q):
        s, t = map(int, input().split())
        res = fw2[s - 1, t - 1]
        if res <= n:
            res_list[i] = int(res - 1)

    for r in res_list:
        print(r)

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
n, m, l = map(int, input().split())
ls = [list(map(int, input().split())) for _ in range(m)]
q = int(input())
query = [list(map(int, input().split())) for _ in range(q)]

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

for road in ls:
    dist[road[0]-1][road[1]-1] = dist[road[1]-1][road[0]-1] = road[2]

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

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

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

for el in query:
    ans = dist2[el[0]-1][el[1]-1]-1
    if dist2[el[0]-1][el[1]-1] == INF:
        ans = -1
    print(ans)

Submission status: Accepted

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

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

def Warshall_Floyd(d,N=None):
    if N==None : N = len(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])

Warshall_Floyd(d,N)

d2 = [None]*N
for i,row in enumerate(d):
    d2[i] = [1 if e<=L else INF for e in row]
    d2[i][i] = 0

Warshall_Floyd(d2,N)

for s,t in ST:
    s-=1;t-=1
    ans = (d2[s][t]%INF)-1
    print(ans)

Submission status: Accepted

Solution code:
def Warshall_Floyd(dist,n,restoration=False):
    next_point = [[j for j in range(n)] for _ in range(n)]
    for i in range(n):
        for j in range(n):
            for k in range(n):
                if dist[j][k] > dist[j][i] + dist[i][k]:
                    next_point[j][k] = next_point[j][i]
                    dist[j][k] = min(dist[j][k], dist[j][i] + dist[i][k])
    if restoration:
        return dist,next_point
    else:
        return dist

n,m,l = map(int,input().split())
inf = 10**18
dist = [[inf for i in range(n)] for j in range(n)]

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

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

dist = Warshall_Floyd(dist,n)
route = [[inf for i in range(n)] for j in range(n)]
for i in range(n):
    for j in range(n):
        if i == j:
            route[i][j] = 0
        elif dist[i][j] <= l:
            route[i][j] = 1

route = Warshall_Floyd(route,n)

q = int(input())


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

Submission status: Accepted

Solution code:
from scipy.sparse import csr_matrix #pypyだとエラーになるので、pythonを使うこと
from scipy.sparse.csgraph import shortest_path, floyd_warshall
import numpy as np

import sys
def input():
	return sys.stdin.readline().strip()

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

A = [0]*M
B = [0]*M
C = [0]*M
for i in range(M):
	Ai, Bi, Ci = list(map(int, input().split()))
	A[i] = Ai - 1
	B[i] = Bi - 1
	C[i] = Ci

graph = csr_matrix((C, (A, B)), shape=(N, N))
#print(graph)
dist = floyd_warshall(graph, directed=False)

graph2 = np.full((N, N), np.inf)
graph2[dist <= L] = 1
graph2 = csr_matrix(graph2)
num = floyd_warshall(graph2, directed=False)


num = num.tolist()

Q = int(input())
for q in range(Q):
	s, t = list(map(int, input().split()))
	if num[s - 1][t - 1] < 10000000:
		print(int(num[s - 1][t - 1] - 1))
	else:
		print(-1)

Submission status: Accepted

Solution code:
from scipy.sparse import csr_matrix #pypyだとエラーになるので、pythonを使うこと
from scipy.sparse.csgraph import shortest_path, floyd_warshall
import numpy as np

import sys
def input():
	return sys.stdin.readline().strip()

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

A = np.zeros(M)
B = np.zeros(M)
C = np.zeros(M)
for i in range(M):
	Ai, Bi, Ci = list(map(int, input().split()))
	A[i] = Ai - 1
	B[i] = Bi - 1
	C[i] = Ci

graph = csr_matrix((C, (A, B)), shape=(N, N))
#print(graph)
dist = floyd_warshall(graph, directed=False)

graph2 = np.full((N, N), np.inf)
graph2[dist <= L] = 1
graph2 = csr_matrix(graph2)
num = floyd_warshall(graph2, directed=False)


num = num.tolist()

Q = int(input())
for q in range(Q):
	s, t = list(map(int, input().split()))
	if num[s - 1][t - 1] < 10000000:
		print(int(num[s - 1][t - 1] - 1))
	else:
		print(-1)

Submission status: Accepted

Solution code:
from scipy.sparse import csr_matrix #pypyだとエラーになるので、pythonを使うこと
from scipy.sparse.csgraph import shortest_path, floyd_warshall
import numpy as np

import sys
def input():
	return sys.stdin.readline().strip()

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

A = np.zeros(M)
B = np.zeros(M)
C = np.zeros(M)
for i in range(M):
	Ai, Bi, Ci = list(map(int, input().split()))
	A[i] = Ai - 1
	B[i] = Bi - 1
	C[i] = Ci

graph = csr_matrix((C, (A, B)), shape=(N, N))
#print(graph)
dist = floyd_warshall(graph, directed=False)

graph2 = np.full((N, N), np.inf)
graph2[dist <= L] = 1
graph2 = csr_matrix(graph2)
num = floyd_warshall(graph2, directed=False)


Q = int(input())
for q in range(Q):
	s, t = list(map(int, input().split()))
	if num[s - 1][t - 1] < 10000000:
		print(int(num[s - 1][t - 1] - 1))
	else:
		print(-1)

Submission status: Accepted

Solution code:
from scipy.sparse import csr_matrix #pypyだとエラーになるので、pythonを使うこと
from scipy.sparse.csgraph import shortest_path, floyd_warshall
import numpy as np

import sys
def input():
	return sys.stdin.readline().strip()

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

A = np.zeros(M)
B = np.zeros(M)
C = np.zeros(M)
for i in range(M):
	Ai, Bi, Ci = list(map(int, input().split()))
	A[i] = Ai - 1
	B[i] = Bi - 1
	C[i] = Ci

graph = csr_matrix((C, (A, B)), shape=(N, N))
#print(graph)
dist = floyd_warshall(graph, directed=False)
graph2 = np.full((N, N), np.inf)
for i in range(N):
	for j in range(N):
		if dist[i, j] <= L:
			graph2[i, j] = 1
graph2 = csr_matrix(graph2)
num = shortest_path(graph2, directed=False)


Q = int(input())
for q in range(Q):
	s, t = list(map(int, input().split()))
	if num[s - 1][t - 1] < 10000000:
		print(int(num[s - 1][t - 1] - 1))
	else:
		print(-1)

Submission status: Accepted

Solution code:

from scipy.sparse import csr_matrix #pypyだとエラーになるので、pythonを使うこと
from scipy.sparse.csgraph import shortest_path, floyd_warshall
import numpy as np

import sys
def input():
	return sys.stdin.readline().strip()

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

graph = np.full((N, N), np.inf)
for i in range(M):
	A, B, C = list(map(int, input().split()))
	graph[A - 1, B - 1] = C
	graph[B - 1, A - 1] = C

graph = csr_matrix(graph)
dist = floyd_warshall(graph, directed=False)
graph2 = np.full((N, N), np.inf)
for i in range(N):
	for j in range(N):
		if dist[i, j] <= L:
			graph2[i, j] = 1
graph2 = csr_matrix(graph2)
num = shortest_path(graph2, directed=False)


Q = int(input())
for q in range(Q):
	s, t = list(map(int, input().split()))
	if num[s - 1][t - 1] < 10000000:
		print(int(num[s - 1][t - 1] - 1))
	else:
		print(-1)

Submission status: Accepted

Solution code:
from scipy.sparse import csr_matrix #pypyだとエラーになるので、pythonを使うこと
from scipy.sparse.csgraph import shortest_path, floyd_warshall
import numpy as np

import sys
def input():
	return sys.stdin.readline().strip()

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

graph = np.full((N, N), np.inf)
for i in range(M):
	A, B, C = list(map(int, input().split()))
	graph[A - 1, B - 1] = C
	graph[B - 1, A - 1] = C


dist = floyd_warshall(graph, directed=False)
graph2 = np.full((N, N), np.inf)
for i in range(N):
	for j in range(N):
		if dist[i, j] <= L:
			graph2[i, j] = 1
graph2 = csr_matrix(graph2)
num = shortest_path(graph2, directed=False)


Q = int(input())
for q in range(Q):
	s, t = list(map(int, input().split()))
	if num[s - 1][t - 1] < 10000000:
		print(int(num[s - 1][t - 1] - 1))
	else:
		print(-1)

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import floyd_warshall
import sys
input = sys.stdin.readline
def solve():
  inf = float("Inf")
  n,m,l = (int(i) for i in input().split())
  path = [[-1*inf]*n for _ in range(n)]
  for i in range(m):
    a,b,c = (int(i) for i in input().split())
    path[a-1][b-1] = c
    path[b-1][a-1] = c
  d = floyd_warshall(path)
  q = int(input())
  minipath = [[-1*inf]*n for _ in range(n)]
  for i in range(n):
    for j in range(n):
      if d[i][j] <= l:
        minipath[i][j] = 1
  d2 = floyd_warshall(minipath)

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

solve()

Submission status: Accepted

Solution code:
from scipy.sparse import csr_matrix #pypyだとエラーになるので、pythonを使うこと
from scipy.sparse.csgraph import shortest_path
import numpy as np

import sys
def input():
	return sys.stdin.readline().strip()

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

graph = np.full((N, N), np.inf)
for i in range(M):
	A, B, C = list(map(int, input().split()))
	graph[A - 1, B - 1] = C
	graph[B - 1, A - 1] = C


dist = shortest_path(graph, method='FW', directed=False)
graph2 = np.full((N, N), np.inf)
for i in range(N):
	for j in range(N):
		if dist[i, j] <= L:
			graph2[i, j] = 1
graph2 = csr_matrix(graph2)
num = shortest_path(graph2, method="FW", directed=False)


Q = int(input())
for q in range(Q):
	s, t = list(map(int, input().split()))
	if num[s - 1][t - 1] < 10000000:
		print(int(num[s - 1][t - 1] - 1))
	else:
		print(-1)

Submission status: Accepted

Solution code:
# ABC143E - Travel by Car
def floyd_warshall(dist):
    """
    Compute the shortest paths of all pairs and modify dist.
    """
    V = len(dist)
    for i in range(V):  # intermediate point
        for j, c2 in enumerate(dist[j][i] for j in range(V)):  #  source
            for k, (c1, c3) in enumerate(zip(dist[j], dist[i])):  # target
                if c2 + c3 < c1:
                    dist[j][k] = c2 + c3


def main():
    # FW -> once more FW to edges <= L
    N, M, L, *X = map(int, open(0).read().split())
    ABC, ST = X[: 3 * M], X[3 * M + 1 :]
    INF = 1 << 60
    dist = [[INF] * (N + 1) for _ in range(N + 1)]
    for i in range(N + 1):
        dist[i][i] = 0
    for v, u, cost in zip(*[iter(ABC)] * 3):
        dist[v][u] = dist[u][v] = cost
    floyd_warshall(dist)

    # assume distance within L as 1 and compute the number of fueling
    modified_dist = [[1 if x <= L else INF for x in d] for d in dist]
    floyd_warshall(modified_dist)
    ans = []
    for s, t in zip(*[iter(ST)] * 2):
        x = modified_dist[s][t]
        if x < INF:
            ans.append(x - 1)
        else:
            ans.append(-1)
    print("\n".join(map(str, ans)))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
from scipy.sparse.csgraph import floyd_warshall

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, M, L = MAP()
G = list2d(N, N, INF)
for i in range(M):
    a, b, c = MAP()
    a -= 1
    b -= 1
    G[a][b] = c
    G[b][a] = c

res = floyd_warshall(G)

G2 = list2d(N, N, INF)
for i in range(N):
    for j in range(i, N):
        # 最短距離がL以下の2点なら燃料1回で行ける
        if res[i][j] <= L:
            G2[i][j] = 1
            G2[j][i] = 1

# 燃料使用回数をコストとした最短経路
res2 = floyd_warshall(G2)

for i in range(INT()):
    a, b = MAP()
    a -= 1
    b -= 1
    ans = res2[a][b]
    if ans != INF:
        print(ans-1)
    else:
        print(-1)

Submission status: Accepted

Solution code:
inf = 10**10
n,m,l = map(int,input().split())

def warshall_floyd(d):
    for i in range(n):
        for j in range(n):
            for k in range(n):
                d[j][k] = min(d[j][k],d[j][i]+d[i][k])
    return d

G = [[inf] * n for _ in range(n)] #重み付きグラフ
for i in range(n):
    G[i][i] = 0
for _ in range(m):
    a,b,c = map(int,input().split())
    G[a-1][b-1] = c
    G[b-1][a-1] = c

G = warshall_floyd(G)
P = [[0] * n for _ in range(n)]

for i in range(n):
    for j in range(n):
        if i == j:
            P[i][j] = 0
        elif G[i][j] <= l:
            P[i][j] = 1
        else:
            P[i][j] = inf

p = warshall_floyd(P)
q = int(input())

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

Submission status: Accepted

Solution code:
def warshall_floyd(G):
    import copy
    ret = copy.deepcopy(G)
    for k in range(N):
        for i in range(N):
            for j in range(N):
                ret[i][j] = min(ret[i][j], ret[i][k] + ret[k][j])
    return ret


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

G = [[INF] * N for _ in range(N)]
for i in range(M):
    A, B, C = map(int, input().split())
    G[A - 1][B - 1], G[B - 1][A - 1] = C, C

MinG = warshall_floyd(G)
GL = [[1 if MinG[i][j] <= L else INF for j in range(N)] for i in range(N)]
MinGL = warshall_floyd(GL)

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

Submission status: Accepted

Solution code:
import sys
import numpy as np

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

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n, m, l = map(int, readline().split())
rest = np.array(read().split(), np.int64)
abc = rest[: m + m + m]
a = abc[::3]
b = abc[1::3]
c = abc[2::3]
st = rest[m + m + m + 1 :]
s = st[::2]
t = st[1::2]


dist_graph = csr_matrix((c, (a, b)), (n + 1, n + 1))
dist_path = floyd_warshall(dist_graph, directed=False)

cost_graph = np.full((n + 1, n + 1), np.inf)
np.fill_diagonal(cost_graph, 0)
cost_graph[dist_path <= l] = 1

cost_path = floyd_warshall(cost_graph, directed=False)

cost_path[cost_path == np.inf] = 0
cost_path = (cost_path).astype(int)

x = cost_path[s, t] - 1

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N, M, L = map(int, input().split())
INF = float('inf')
VD = [[INF] * N for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    VD[a][b] = c
    VD[b][a] = c
for i in range(N):
    VD[i][i] = 0
 
for k in range(N):
    for i in range(N):
        for j in range(N):
            if VD[i][j] > VD[i][k] + VD[k][j]:
                VD[i][j] = VD[i][k] + VD[k][j]
 
WD = [[INF] * N for _ in range(N)]
for i in range(N):
    WD[i][i] = 0
    for j in range(i+1,N):
        d = VD[i][j]
        if d <= L:
            WD[i][j] = 1
            WD[j][i] = 1
 
for k in range(N):
    for i in range(N):
        for j in range(N):
            if WD[i][j] > WD[i][k] + WD[k][j]:
                WD[i][j] = WD[i][k] + WD[k][j]
 
Q = int(input())
for _ in range(Q):
    s, t = map(int, input().split())
    print(WD[s-1][t-1]-1 if WD[s-1][t-1] < INF else -1)

Submission status: Accepted

Solution code:
N,M,L = map(int,input().split())
INF = 10**13
D = [[INF]*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())
    D[A-1][B-1] = C
    D[B-1][A-1] = C

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

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

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

for i in range(N):
    for j in range(N):
        if F[i][j] == INF:
            F[i][j] = -1
        elif i != j:
            F[i][j] -= 1

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

Submission status: Accepted

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


n, m, energy = map(int, input().split())
edges = [[float('INF')]*n for _ in range(n)]
for i in range(m):
    a, b, c = map(int, input().split())
    edges[a-1][b-1] = c
    edges[b-1][a-1] = c

G = csgraph_from_dense(edges, null_value=float('INF'))
dist = floyd_warshall(G, directed=False)

L_edges = [[0]*n for _ in range(n)]
for i in range(n-1):
    for j in range(i, n):
        if dist[i][j] <= energy:
            L_edges[i][j] = 1
            L_edges[j][i] = 1

G = csgraph_from_dense(L_edges, null_value=0)
answers = floyd_warshall(G, directed=False)

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

Submission status: Accepted

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


n, m, energy = map(int, input().split())
edges = [[float('INF')]*n for _ in range(n)]

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

G = csgraph_from_dense(edges, null_value=float('INF'))
dist = floyd_warshall(G)  # dist[i][j] = min_distance between i and j

L_edges = [[0]*n for _ in range(n)]
for i in range(n-1):
    for j in range(i, n):
        if dist[i][j] <= energy:
            L_edges[i][j] = 1
            L_edges[j][i] = 1

G = csgraph_from_dense(L_edges, null_value=0)
answers = floyd_warshall(G)
for i in range(n):
    for j in range(n):
        if answers[i][j] == float('INF'):
            answers[i][j] = 0
            answers[j][i] = 0

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

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import csgraph_from_dense
from scipy.sparse.csgraph import floyd_warshall

n, m, energy = map(int, input().split())
edges = [[float('INF')]*n for _ in range(n)]

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

G = csgraph_from_dense(edges, null_value=float('INF'))
dist = floyd_warshall(G)

L_edges = [[float('INF')]*n for _ in range(n)]
for i in range(n-1):
    for j in range(i, n):
        if dist[i][j] <= energy:
            L_edges[i][j] = 1
            L_edges[j][i] = 1

G = csgraph_from_dense(L_edges, null_value=float('INF'))
answers = floyd_warshall(G)

Q = int(input())
for i in range(Q):
    s, t = map(int, input().split())
    ans = answers[s-1][t-1] - 1
    if ans == float('INF'):
        ans = -1
    print(int(ans))

Submission status: Accepted

Solution code:
N, M, L = map(int, input().split())
INF = 10 ** 12

G = [[INF] * (N+1) for _ in range(N+1)]

for _ in range(M):
    a, b, c = map(int, input().split())
    G[a][b] = c
    G[b][a] = c


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

GL = [[INF] * (N+1) for _ in range(N+1)]
for i in range(1, N):
    for j in range(i+1, N+1):
        if G[i][j] <= L:
            GL[i][j] = 1
            GL[j][i] = 1

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

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

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import numpy as np
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix

N, M, L = [int(_) for _ in readline().split()]
ABCQST = np.array(read().split(), dtype=int)
ABC = ABCQST[:3 * M]
ST = ABCQST[3 * M + 1:]
A, B, C = ABC[::3], ABC[1::3], ABC[2::3]
S, T = ST[::2], ST[1::2]
G = csr_matrix((C, (A, B)), shape=(N + 1, N + 1))
G2 = floyd_warshall(G, directed=0)
G3 = np.full((N + 1, N + 1), np.inf)
np.fill_diagonal(G3, 0)
G3[G2 <= L] = 1
G4 = floyd_warshall(G3, directed=0)
G4[G4 == np.inf] = 0
#print(*(G4.astype(int)[S, T] - 1), sep='\n')
print('\n'.join((G4.astype(int)[S, T] - 1).astype(str)))

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import numpy as np
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix

N, M, L = [int(_) for _ in readline().split()]
ABCQST = np.array(read().split(), dtype=np.int64)
ABC = ABCQST[:3 * M]
ST = ABCQST[3 * M + 1:]
A, B, C = ABC[::3], ABC[1::3], ABC[2::3]
S, T = ST[::2], ST[1::2]
G = csr_matrix((C, (A, B)), shape=(N + 1, N + 1))
G2 = floyd_warshall(G, directed=0)
G3 = np.full((N + 1, N + 1), np.inf)
np.fill_diagonal(G3, 0)
G3[G2 <= L] = 1
G4 = floyd_warshall(G3, directed=0)
G4[G4 == np.inf] = 0
#print(*(G4.astype(int)[S, T] - 1), sep='\n')
print('\n'.join((G4.astype(int)[S, T] - 1).astype(str)))

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import numpy as np
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix

N, M, L = [int(_) for _ in readline().split()]
ABCQST = np.array(read().split(), dtype=np.int64)
ABC = ABCQST[:3 * M]
ST = ABCQST[3 * M + 1:]
A, B, C = ABC[::3], ABC[1::3], ABC[2::3]
S, T = ST[::2], ST[1::2]
G = csr_matrix((C, (A, B)), shape=(N + 1, N + 1))
G2 = floyd_warshall(G, directed=0)
G3 = np.full((N + 1, N + 1), np.inf)
np.fill_diagonal(G3, 0)
G3[G2 <= L] = 1
G4 = floyd_warshall(G3, directed=0)
G4[G4 == np.inf] = 0
print(*(G4.astype(np.int64)[S, T] - 1), sep='\n')

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import numpy as np
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix

N, M, L = [int(_) for _ in readline().split()]
ABCQST = np.array(read().split(), dtype=np.int64)
ABC = ABCQST[:3 * M]
ST = ABCQST[3 * M + 1:]
A, B, C = ABC[::3], ABC[1::3], ABC[2::3]
S, T = ST[::2], ST[1::2]
G = csr_matrix((C, (A, B)), shape=(N + 1, N + 1))
G2 = floyd_warshall(G, directed=0)
G3 = np.full((N + 1, N + 1), np.inf)
np.fill_diagonal(G3, 0)
G3[G2 <= L] = 1
G4 = floyd_warshall(G3, directed=0)
G4[G4 == np.inf] = 0
print(*(G4[S, T] - 1).astype(np.int64), sep='\n')

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import numpy as np
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix

N, M, L = [int(_) for _ in readline().split()]
ABCQST = np.array([int(_) for _ in read().split()], dtype=np.int64)
ABC = ABCQST[:3 * M]
ST = ABCQST[3 * M + 1:]
A, B, C = ABC[::3], ABC[1::3], ABC[2::3]
S, T = ST[::2], ST[1::2]
G = csr_matrix((C, (A, B)), shape=(N + 1, N + 1))
G2 = floyd_warshall(G, directed=0)
G3 = np.full((N + 1, N + 1), np.inf)
np.fill_diagonal(G3, 0)
G3[G2 <= L] = 1
G4 = floyd_warshall(G3, directed=0)
G4[G4 == np.inf] = 0
print(*(G4[S, T] - 1).astype(np.int64), sep='\n')

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import numpy as np
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix

N, M, L = [int(_) for _ in readline().split()]
ABCQST = np.array([int(_) for _ in read().split()], dtype=np.int64)
ABC = ABCQST[:3 * M]
ST = ABCQST[3 * M + 1:]
A, B, C = ABC[::3], ABC[1::3], ABC[2::3]
S, T = ST[::2], ST[1::2]
G = csr_matrix((C, (A, B)), shape=(N + 1, N + 1))
G2 = floyd_warshall(G, directed=0)
G3 = G2 <= L
G4 = floyd_warshall(G3, directed=0)
G4[G4 == 0] = 1
G4[G4 == np.inf] = 0
G4 -= 1
print(*G4[S, T].astype(np.int64), sep='\n')

Submission status: Accepted

Solution code:
from scipy.sparse import*
f=csgraph.floyd_warshall
t=map(int,open('/dev/fd/0').read().split())
n,m,l=t[:3]
m=m*3+3
for i in f(f(csr_matrix((t[5:m:3],(t[3:m:3],t[4:m:3])),[n+1]*2),0)<=l)[t[m+1::2],t[m+2::2]].clip(0,n)%n-1:print i

Submission status: Accepted

Solution code:
from scipy.sparse import*
f=csgraph.johnson
t=map(int,open('/dev/fd/0').read().split())
n,m,l=t[:3]
m=m*3+3
for i in f(f(csr_matrix((t[5:m:3],(t[3:m:3],t[4:m:3])),[n+1]*2),0)<=l)[t[m+1::2],t[m+2::2]].clip(0,n)%n-1:print i

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#ABC143 E

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()
graph = [[] for _ in range(n)]
d = [[inf]*n for _ in range(n)]
for _ in range(m):
    a,b,c = LI()
    graph[a-1].append((b-1,c))
    graph[b-1].append((a-1,c))
    d[a-1][b-1] = c
    d[b-1][a-1] = c

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

d = warshall_floyd(d)

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

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