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 math

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

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

Q = int(input())
query = [(0, 0) for _ in range(Q)]

for i in range(Q):
    query[i] = tuple(map(int, input().split()))

# Warshall-Floyd
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])

fuel_cost = [[math.inf]*N for _ in range(N)]

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

# Warshall-Floyd
for i in range(N):
    for j in range(N):
        for k in range(N):
            fuel_cost[j][k] = min(fuel_cost[j][k], fuel_cost[j][i] + fuel_cost[i][k])

for i in range(Q):
    if fuel_cost[query[i][0] - 1][query[i][1] - 1] == math.inf:
        print(-1)
    else:
        print(fuel_cost[query[i][0] - 1][query[i][1] - 1] - 1)

Submission status: Accepted

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))


"""
全点対探索 & Nが小さいのでワーシャルフロイド．クエリも多めだし
合計距離から補給の回数をうまく計算するのは難しい，
残燃料を持つのも厳しい．
距離バージョンではなくて補給回数バージョンで新しいグラフとか作りたい

新しいグラフは距離がL以下の全点に対してならコスト1の辺を結ぶ．
最初からLあるのでコスト-1

"""
def main():
    
    def warshall_floyd(d):
        #d[i][j]: iからjへの最短距離
        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])
        return d
    
    mod=10**9+7
    N,M,L=MI()
    inf = 10**12
    d=[[inf]*N for _ in range(N)]
    for i in range(M):
        a,b,c=MI()
        a-=1
        b-=1
        d[a][b]=c
        d[b][a]=c
        
    d=warshall_floyd(d)
    
    nd=[[inf]*N for _ in range(N)] # 距離がL以下ならコスト1で結ぶ
    
    for i in range(N):
        for j in range(N):
            if d[i][j]<=L:
                nd[i][j]=1
    
    nd =warshall_floyd(nd)
    
    Q=I()
    for _ in range(Q):
        s,t=MI()
        s-=1
        t-=1
        ans=nd[s][t]
        if ans >= inf:
            ans=0
        print(ans-1)
        
    
    
    
main()

Submission status: Accepted

Solution code:
def warshall_floyd(n, edges):
    d = [[float('inf')] * n for _ in range(n)]
    for i in range(n):
        d[i][i] = 0
    for vf, vt, w in edges:
        d[vf][vt] = w
    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 = map(int, input().split())
edges = []
for _ in range(m):
    a, b, w = map(int, input().split())
    if w <= l:
        edges.append((a-1, b-1, w))
        edges.append((b-1, a-1, w))
wf = warshall_floyd(n, edges)

edges.clear()
for i in range(n):
    for j in range(i + 1, n):
        if wf[i][j] <= l:
            edges.append((i, j, 1))
            edges.append((j, i, 1))
wf = warshall_floyd(n, edges)

q = int(input())
ans = [0] * q
for i in range(q):
    s, t = map(lambda x:int(x) - 1, input().split())
    ans[i] = -1 if wf[s][t] == float('inf') else wf[s][t] - 1
for x in ans:
    print(x)

Submission status: Accepted

Solution code:

import numpy as np
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix
def resolve():
    INF = 10 ** 18
    N, M, L = map(int, input().split())
    G = [[INF] * N for _ in range(N)]
    for _ in range(M):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        G[a][b] = G[b][a] = c

    G = csr_matrix(G)
    dist = floyd_warshall(G, directed=False)

    G2 = np.full((N, N), np.inf)  # 値をINFにした配列
    np.fill_diagonal(G2, 0)  # G[i][i]は動いていない状態なのでコスト0
    G2[dist <= L] = 1

    dist2 = floyd_warshall(G2, directed=False)

    Q = int(input())
    for _ in range(Q):
        a, b = map(lambda x: int(x) - 1, input().split())
        if dist2[a][b] == np.inf:
            print(-1)
        else:
            print(int(dist2[a][b]) - 1)


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:

def resolve():
    INF = 10 ** 18
    N, M, L = map(int, input().split())
    G = [[INF] * N for _ in range(N)]
    for _ in range(M):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        G[a][b] = G[b][a] = c

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

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

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

    Q = int(input())
    for _ in range(Q):
        a, b = map(lambda x: int(x) - 1, input().split())
        if Cost[a][b] == INF:
            print(-1)
        else:
            print(Cost[a][b] - 1)


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
# INF =  float("inf")
INF = 10**18
import bisect
import statistics
mod = 10**9+7
# mod = 998244353

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[j][k])

    return d

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

d = [[INF for j in range(N)] for i in range(N)]
for i in range(M):
    a, b, c = map(int,input().split())
    d[a-1][b-1] = c
    d[b-1][a-1] = c

d = warshall_floyd(d, N)

dd = [[INF for j in range(N)] for i in range(N)]
for i in range(N):
    for j in range(i+1, N):
        if d[i][j] <= L:
            dd[i][j] = 1
            dd[j][i] = 1

dd = warshall_floyd(dd, N)

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

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, m, l = map(int, input().split())
    cost = [[f_inf] * n for _ in range(n)]
    for i in range(n):
        cost[i][i] = 0
    for _ in range(m):
        a, b, c = map(int, input().split())
        cost[a - 1][b - 1] = c
        cost[b - 1][a - 1] = c

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

    res = [[f_inf] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if cost[i][j] <= l:
                res[i][j] = 1

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

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


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
n,m,l = map(int,input().split())
g = [[float('inf')]*n for _ in range(n)]
for _ in range(m):
    a,b,c = map(int,input().split())
    a-=1
    b-=1
    g[a][b] = c
    g[b][a] = c
for k in range(n):
    for i in range(n):
        for j in range(n):
            g[i][j] = min(g[i][j],g[i][k] + g[k][j])
h = [[float('inf')]*n for _ in range(n)]
for i in range(n):
    for j in range(n):
        if g[i][j]<=l:
            h[i][j] = 1

for k in range(n):
    for i in range(n):
        for j in range(n):
            h[i][j] = min(h[i][j],h[i][k] + h[k][j])
Q = int(input())
for _ in range(Q):
    s,t = map(int,input().split())
    s -=1
    t-=1
    if h[s][t] ==float('inf'):
        print(-1)
    else:
        print(h[s][t]-1)

Submission status: Accepted

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

n, m, l = map(int, input().split())
INF = 1 << 60

# 距離のmatrixを作る
dist = [[INF] * n for _ in range(n)]

# 対角行列の成分は０
for i in range(n):
    dist[i][i] = 0

# 燃料の最大値より小さい場合に辺が張れる
for _ in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    if c > l:
        continue
    dist[a][b] = c
    dist[b][a] = c

# 全点間の最短距離を求める
dist = floyd_warshall(csr_matrix(dist))

# 初期状態を１にする。燃料が足りない経路は迂回したいのでINFを置いておく
dist2 = np.full_like(dist, 1)
dist2[np.where(dist > l)] = INF

# 足し込むことで何回給油するべきかがわかる
dist2 = floyd_warshall(dist2, directed=False)
dist2 = dist2.astype(int)

# 無限大の経路は辿れない。-1を出力したいので０を置いていく
dist2[dist2 == INF] = 0

q = int(input())

# 初期状態を１としているので、１を引いて答えとする
ans = []
for _ in range(q):
    s, t = map(int, input().split())
    ans.append(dist2[s - 1, t - 1] - 1)

print(*ans, sep="\n")

Submission status: Accepted

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

n, m, l = map(int, input().split())
INF = 1 << 60

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

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

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


dist = floyd_warshall(csr_matrix(dist))

dist2 = np.full_like(dist, 1)
dist2[np.where(dist > l)] = INF
dist2 = floyd_warshall(dist2, directed=False)
dist2[dist2 == INF] = 0
dist2 = dist2.astype(int)

q = int(input())

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

print(*ans, sep="\n")

Submission status: Accepted

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

n, m, l = map(int, input().split())
INF = 1 << 60

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

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

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


dist = floyd_warshall(csr_matrix(dist))

dist2 = np.full_like(dist, 1)
dist2[np.where(dist > l)] = INF
dist2 = floyd_warshall(dist2, directed=False)
dist2[dist2 == INF] = 0
dist2 = dist2.astype(int)

q = int(input())

ans = []
for _ in range(q):
    s, t = map(int, input().split())
    if dist[s - 1, t - 1] == -1:
        ans.append(-1)
    else:
        ans.append(dist2[s - 1, t - 1] - 1)

print(*ans, sep="\n")

Submission status: Accepted

Solution code:
# ABC143-E

import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())


N,M,L = MI()

inf = 10**12
cost = [[inf]*(N+1) for _ in range(N+1)]  # cost[i][j] = 町iから町jへ移動するのにかかる燃料の総和

# WarshallFloyd法

for i in range(M):
    a,b,c = MI()
    cost[a][b] = c
    cost[b][a] = c

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

ans = [[inf]*(N+1) for _ in range(N+1)]  # ans[i][j] = 町iから町jへ移動するために必要な燃料補給の回数+1

# WarshallFloyd法、再び

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

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

Q = I()
for i in range(Q):
    s,t = MI()
    if ans[s][t] == inf:
        print(-1)
        continue
    print(ans[s][t]-1)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, M, L = mapint()
dist = [[10**18]*N for _ in range(N)]
for _ in range(M):
    a, b, c = mapint()
    dist[a-1][b-1] = c
    dist[b-1][a-1] = c

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

oil = [[10**18]*N for _ in range(N)]
for i in range(N-1):
    for j in range(i+1, N):
        if dist[i][j]<=L:
            oil[i][j] = 1
            oil[j][i] = 1

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

Q = int(input())
for _ in range(Q):
    s, t = mapint()
    if oil[s-1][t-1]>=10**17:
        print(-1)
    else:
        print(oil[s-1][t-1]-1)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし


N,M,L = MI()


class WarshallFloyd():
    def __init__(self,N):  # Nは頂点の個数
        self.N = N
        self.d = [[float('inf')]*N for i in range(N)]  # d[i][j] = iからjへの最短距離,0-indexed
    def add(self,u,v,c,directed = False):
        if directed is False:  # 無向グラフの場合
            self.d[u][v] = c
            self.d[v][u] = c
        else:  # 有向グラフの場合
            self.d[u][v] = c
    def WarshallFloyd_search(self):
        for k in range(self.N):
            for i in range(self.N):
                for j in range(self.N):
                    self.d[i][j] = min(self.d[i][j],self.d[i][k] + self.d[k][j])
        return self.d


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

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

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

Q = I()
for i in range(Q):
    s,t = MI()
    if d2[s-1][t-1] == float('inf'):
        print(-1)
        continue
    print(d2[s-1][t-1]-1)

Submission status: Accepted

Solution code:
def warshall_floyd(d,n):
    #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


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

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


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

    for a in ansl: print(a)



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

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


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


if __name__ == '__main__':
    solve()

Submission status: Accepted

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

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

#############
# Functions #
#############

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


#####Shorten#####
def DD(arg): return defaultdict(arg)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

#############
# Main Code #
#############


  
N,M,L = IL()

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

  def add(self, u, v, c, directed=False):
    if directed is False:
      self.d[u][v] = c
      self.d[v][u] = c
    else:
      self.d[u][v] = c

  def WarshallFloyd_search(self):
    for k in range(self.N):
      for i in range(self.N):
        for j in range(self.N):
          self.d[i][j] = min(self.d[i][j], self.d[i][k] + self.d[k][j])
    hasNegativeCycle = False
    for i in range(self.N):
      if self.d[i][i] < 0:
        hasNegativeCycle = True
        break
    for i in range(self.N):
      self.d[i][i] = 0
    return hasNegativeCycle, self.d
  
W = WarshallFloyd(N)
for _ in range(M):
  u,v,c = IL()
  if c>L: continue
  W.add(u-1,v-1,c)

_,d = W.WarshallFloyd_search() 


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

_,d = W.WarshallFloyd_search() 

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

Submission status: Accepted

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

import numpy as np

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

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

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

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

Submission status: Accepted

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

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

floyd_warshall(dp1)

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

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys


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


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
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))
    print(*solve(N, M, L, A, B, C, Q, s, t), sep="\n")

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

if __name__ == '__main__':
    #test()
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys


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


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
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))
    print(*solve(N, M, L, A, B, C, Q, s, t), sep="\n")

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

if __name__ == '__main__':
    #test()
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys


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


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
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))
    print(*solve(N, M, L, A, B, C, Q, s, t), sep="\n")

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

if __name__ == '__main__':
    #test()
    main()