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:
from scipy.sparse.csgraph import floyd_warshall as fw
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

cost = fw(cost)

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

cost = fw(cost)

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

Submission status: Accepted

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

def main():
    input = sys.stdin.readline
    N, M, L = map(int, input().split())
    d = [[float('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())
        if c > L:
            continue
        d[a-1][b-1] = c
        d[b-1][a-1] = c
    
    G = floyd_warshall(d)

    e = [[float('inf')]*N for _ in range(N)]
    for i in range(N):
        e[i][i] = 0
    for i in range(N-1):
        for j in range(i+1, N):
            if G[i][j] <= L:
                e[i][j] = 1
                e[j][i] = 1
    
    H = floyd_warshall(e)
    
    Q = int(input())
    for _ in range(Q):
        s, t = map(int, input().split())
        if H[s-1][t-1] == float('inf'):
            print(-1)
            continue
        ans = H[s-1][t-1] - 1
        print(int(ans))
    
    exit()


if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:
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 range(N)]
kyuyu = [[float('inf')]*N for _ in range(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)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
from collections import deque
def getN():
    return int(input())
def getList():
    return list(map(int, input().split()))
import math

n, m, l = getList()

INF = 10 ** 10
vers = [[INF for j in range(n)] for i in range(n)]

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

for _ in range(m):
    a, b, c = getList()
    if c <= l:
        vers[a-1][b-1] = c
        vers[b - 1][a - 1] = c

def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    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

d2 = warshall_floyd(vers)

new_vers = [[INF for j in range(n)] for i in range(n)]
for i in range(n):
    new_vers[i][i] = 0

for i in range(n):
    for j in range(n):
        if i != j and d2[i][j] <= l:
            new_vers[i][j] = 1

d3 = warshall_floyd(new_vers)

# print(d3)
Q = getN()

for _ in range(Q):
    a, b = getList()
    if d3[a-1][b-1] == INF:
        print(-1)
    else:
        print(d3[a - 1][b - 1] - 1)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
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))  # type: int
    M = int(next(tokens))  # type: int
    L = int(next(tokens))  # type: int
    A = [int()] * (M)  # type: "List[int]"
    B = [int()] * (M)  # type: "List[int]"
    C = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
        C[i] = int(next(tokens))
    Q = int(next(tokens))  # type: int
    s = [int()] * (Q)  # type: "List[int]"
    t = [int()] * (Q)  # type: "List[int]"
    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()

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
#何とか法, AOJのgrl1c
#初め満杯
import sys
input = sys.stdin.readline
#print = sys.stdout.write

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)
#print(dp)
#print(*ans)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:

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)

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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)))

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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')

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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

#print(A)


A= floyd_warshall(A,directed = False)
#print(A)
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"""
#print(B)

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

#print(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))

Submission status: Accepted

Solution code:
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)

# 補給なしに行ける移動を1手とする

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

Submission status: Accepted

Solution code:
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() :
    # print(s, d)
    pre1 = [-1] * N
    pre2 = [INF] * N
    pre1[s] = L #のこりのガソリン
    pre2[s] = 0 #補充回数
    queue = deque([(s, L, 0)])
    
    while queue :
        # print(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
                
    # print(pre1)
    # print(pre2)
    # print()
    
    for dest, i in d :
        if pre1[dest] == -1 :
            ret[i] = -1
        else :
            ret[i] = pre2[dest]
        
for r in ret :
    print(r)

Submission status: Accepted

Solution code:
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
#print(road)
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])
#print(road)
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
#print(cango)
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])
#print(cango)
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)