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
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,m,L=map(int,input().split())
    E=[[] for _ in range(n)]
    for _ in range(m):
        a,b,c=map(int,input().split())
        if(c>L): continue
        a-=1; b-=1
        E[a].append((b,c))
        E[b].append((a,c))
    A=[0]*n
    # pure Dijkstraを全ての始点で行う
    for u in range(n):
        dist=[(INF,INF)]*n # (補給回数,使用燃料)
        dist[u]=(0,0)
        calculated=[False]*n
        for _ in range(n-1):
            v=min((dist[v],v) for v in range(n) if(not calculated[v]))[1]
            calculated[v]=True
            now=dist[v]
            for nv,w in E[v]:
                if(now[1]+w<=L):
                    next=(now[0],now[1]+w)
                else:
                    next=(now[0]+1,w)
                if(dist[nv]>next):
                    dist[nv]=next
        A[u]=dist
    # output
    Q=int(input())
    for _ in range(Q):
        s,t=map(int,input().split())
        s-=1; t-=1
        ans=A[s][t][0]
        print(ans if ans!=INF else -1)
resolve()

Submission status: Accepted

Solution code:
#!/usr/bin/pypy
# coding: utf-8

N,M,L=map(int, raw_input().split())
RG=[[ 0 if i==j else float('inf') for i in range(N)] for j in range(N)]

for i in xrange(M):
    f,t,c = map(int, raw_input().split())
    if c <= L:
        RG[f-1][t-1] = c
        RG[t-1][f-1] = c

for k in xrange(N):
    for i in xrange(N):
        for j in xrange(i, N):
            t = RG[i][k] + RG[k][j]
            if RG[i][j] > t:
                RG[i][j] = t
                RG[j][i] = t

FG=[[float('inf') for i in range(N)] for j in range(N)]
for i in xrange(N):
    for j in xrange(i, N):
        if RG[i][j] <= L:
            FG[i][j] = 1
            FG[j][i] = 1

for k in xrange(N):
    for i in xrange(N):
        for j in xrange(i, N):
            t = FG[i][k] + FG[k][j]
            if FG[i][j] > t:
                FG[i][j] = t
                FG[j][i] = t

Q=int(raw_input())
for i in xrange(Q):
    s, t = map(int, raw_input().split())
    v = FG[s-1][t-1]
    if v == float('inf'):
        print (str(-1))
    else:
        print (str(int(v-1)))

Submission status: Accepted

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

n,m,l = map(int,input().split())
A = [list(map(int,input().split())) for i in range(m)]
q = int(input())
S = [list(map(int,input().split())) for i in range(q)]

from scipy.sparse.csgraph import floyd_warshall

for i in range(m):  # ノード番号が1始まりで与えられている場合
    for j in range(2):
        A[i][j] -= 1

for i in range(q):  # ノード番号が1始まりで与えられている場合
    for j in range(2):
        S[i][j] -= 1

M = [[float("inf")] * n for i in range(n)]

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

for i in range(m):
    M[A[i][0]][A[i][1]] = A[i][2]
    M[A[i][1]][A[i][0]] = A[i][2]

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

M = floyd_warshall(M)

for i in range(n):
    for j in range(n):
        M[i][j] = 1 if M[i][j] <= l else float("inf")

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

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

M = floyd_warshall(M)

for i in range(q):
    ans = M[S[i][0]][S[i][1]]-1
    if ans == float("inf"):
        ans = -1
    print(int(ans))

Submission status: Accepted

Solution code:
n,m,l = map(int,input().split())
A = [list(map(int,input().split())) for i in range(m)]
q = int(input())
S = [list(map(int,input().split())) for i in range(q)]

from scipy.sparse.csgraph import floyd_warshall

for i in range(m):  # ノード番号が1始まりで与えられている場合
    for j in range(2):
        A[i][j] -= 1

for i in range(q):  # ノード番号が1始まりで与えられている場合
    for j in range(2):
        S[i][j] -= 1

M = [[float("inf")] * n for i in range(n)]

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

for i in range(m):
    M[A[i][0]][A[i][1]] = A[i][2]
    M[A[i][1]][A[i][0]] = A[i][2]

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

M = floyd_warshall(M)

for i in range(n):
    for j in range(n):
        M[i][j] = 1 if M[i][j] <= l else float("inf")

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

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

M = floyd_warshall(M)

for i in range(q):
    ans = M[S[i][0]][S[i][1]]-1
    if ans == float("inf"):
        ans = -1
    print(int(ans))

Submission status: Accepted

Solution code:
import sys


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n, m, l = list(map(int, input().rstrip('\n').split()))
    wn = n
    wm = m
    inf = 10 ** 11
    wl = [[inf] * wn for _ in range(wn)]
    for i in range(wn):
        wl[i][i] = 0

    for i in range(wm):
        wa, wb, wc = list(map(int, input().rstrip('\n').split()))
        wl[wa - 1][wb - 1] = wc
        wl[wb - 1][wa - 1] = wc

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

    wn = n
    wm = m
    inf = 10 ** 11
    wl2 = [[inf] * wn for _ in range(wn)]
    for i in range(wn):
        wl2[i][i] = 0

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

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

    q = int(input().rstrip('\n'))
    for i in range(q):
        s, t = list(map(int, input().rstrip('\n').split()))
        print(wl2[s-1][t-1] - 1 if wl2[s-1][t-1] != inf else -1)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
n,m,l = map(int,input().split())
inf = 10 ** 18
d1 = [[inf for _ in range(n)] for _ in range(n)]
for i in range(n):
  d1[i][i] = 0
for _ in range(m):
  a,b,c = map(int,input().split())
  a -= 1
  b -= 1
  d1[a][b] = c
  d1[b][a] = c
for k in range(n):
  for i in range(n):
    for j in range(n):
      d1[i][j] = min(d1[i][j], d1[i][k]+d1[k][j])
d2 = [[inf for _ in range(n)] for _ in range(n)]
for i in range(n):
  for j in range(n):
    if d1[i][j] == 0:
      d2[i][j] = 0
    elif d1[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 = int(input())
for _ in range(q):
  s,t = map(int,input().split())
  s -= 1
  t -= 1
  ans = d2[s][t]
  if ans >= inf:
    print(-1)
  else:
    print(ans-1)

Submission status: Accepted

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

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

inf = (l+1)*n
d = [[inf]*n for _ in range(n)]
for i in range(n):
    d[i][i] = 0
for a,b,c in town:
    a -= 1
    b -= 1
    d[a][b] = c
    d[b][a] = c
    
def warshall_floyd(d,n):
    for k in range(n):
        for j in range(n):
            for i 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 val<=l else inf for val in row]
    d2[i][i] = 0

warshall_floyd(d2,n)
 
for s,t in query:
    s -= 1
    t -= 1
    count = (d2[s][t]%inf)-1
    print(count)

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:
n,m,l=map(int,input().split())
g=[[999999999999 if i!=j else 0 for j in range(n)] for i in range(n)]
for i in range(m):
    a,b,c=map(int,input().split())
    a,b=a-1,b-1
    if c>l:
        continue
    g[a][b]=c
    g[b][a]=c

for k in range(n):
    for i in range(n):
        for j in range(n):
            if g[i][j]>g[i][k]+g[k][j]:
                g[i][j] = g[i][k]+g[k][j]

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

for k in range(n):
    for i in range(n):
        for j in range(n):
            if g[i][j]>g[i][k]+g[k][j]:
                g[i][j] = g[i][k]+g[k][j]

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

Submission status: Accepted

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


n,m,l= map(int,input().split()) #n:頂点数　w:辺の数

d=[[float("inf") for i in range(n)] for i in range(n)] 
#d[u][v] : 辺uvのコスト(存在しないときはinf)
for i in range(m):
    a,b,c = map(int,input().split())
    d[a-1][b-1]=c
    d[b-1][a-1]=c
for i in range(n):
    d[i][i] = 0 #自身のところに行くコストは０
warshall_floyd(d)

d2=[[float("inf") for i in range(n)] for i in range(n)] 
for i in range(n):
    for j in range(n):
        if d[i-1][j-1]<=l:
            d2[i-1][j-1]=1
            d2[j-1][i-1]=1
warshall_floyd(d2)
q=int(input())
l=[list(map(int, input().split())) for i in range(q)]
for i in range(q):
    if d2[l[i][0]-1][l[i][1]-1]-1!=float('inf'):
        print(d2[l[i][0]-1][l[i][1]-1]-1)
    else:
        print(-1)

Submission status: Accepted

Solution code:
import sys


def naive_dijkstra(links, n, l):
    F30 = (1 << 30) - 1
    INF = 10 ** 18

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

    for s in range(n):
        rs = refuels[s]

        dists = [INF] * n
        dists[s] = 0
        remain_nodes = set(range(n))

        for _ in range(n):
            v = -1
            w = INF
            for u in remain_nodes:
                if dists[u] < w:
                    v = u
                    w = dists[u]
            if v == -1:
                break
            remain_nodes.remove(v)

            count = w >> 30
            used = w & F30
            rs[v] = count

            for u, c in links[v]:
                if l - used < c:
                    nw = ((count + 1) << 30) | c
                else:
                    nw = w + c
                if nw < dists[u]:
                    dists[u] = nw

    return refuels


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

links = [set() for _ in range(n)]

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

dists = naive_dijkstra(links, n, l)
buf = []

for line in lines[m + 1:]:
    s, t = map(int, line.split())
    buf.append(dists[s - 1][t - 1])

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from scipy.sparse.csgraph import floyd_warshall

N, M, L = map(int,input().split())
  
d = [[0 for i in range(N)] for j in range(N)] 
for i in range(M):
    x,y,z = map(int,input().split())
    d[x-1][y-1] = z
    d[y-1][x-1] = z
for i in range(N):
    d[i][i] = 0

d = floyd_warshall(d, directed = False)
LN = [[0 for i in range(N)] for j in range(N)]

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

LN = floyd_warshall(LN, directed = False)    
s = []
t = []
Q = int(input())
for i in range(Q):
    s1, t1 = map(int,input().split())
    s.append(s1)
    t.append(t1)
for i in range(Q):
    if LN[s[i]-1][t[i]-1] == float("inf"):
        print(-1)
    else:
        print(int(LN[s[i]-1][t[i]-1]-1))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
input = lambda: sys.stdin.readline().rstrip()
inpl = lambda: list(map(int,input().split()))
N, M, L = inpl()
road = [[] for _ in range(N)]
ABC = []
for i in range(M):
    A, B, C = inpl()
    if C <= L:
        road[A-1].append((B-1,C))
        road[B-1].append((A-1,C))
        ABC.append((A-1,B-1,C))

INF = 10**12
cur1 = [[INF]*N for _ in range(N)]
for a, b, c in ABC:
    cur1[a][b] = cur1[b][a] = c
for k in range(N):
    prev1 = cur1
    cur1 = [[INF]*N for _ in range(N)] 
    for j in range(N):
        for i in range(N):
            cur1[j][i] = min(prev1[j][i], prev1[k][i]+prev1[j][k])

cur2 = [[INF]*N for j in range(N)]
for j in range(N):
    for i in range(N):
        if cur1[j][i] <= L:
            cur2[j][i] = 1
for k in range(N):
    prev2 = cur2
    cur2 = [[INF]*N for _ in range(N)]
    for j in range(N):
        for i in range(N):
            cur2[j][i] = min(prev2[j][i], prev2[k][i]+prev2[j][k])

Q = int(input())
ST = [inpl() for _ in range(Q)]
for s,t in ST:
    if cur2[s-1][t-1] >= INF:
        print(-1)
    else:
        print(cur2[s-1][t-1]-1)

Submission status: Accepted

Solution code:
n, m, L = map(int, input().split())
abc = [list(map(int, input().split())) for _ in range(m)]
q = int(input())
st = [list(map(int, input().split())) for _ in range(q)]

d = [[float('inf') for _ in range(n)] for _ in range(n)]
for a, b, c in abc:
    if c > L:
        continue
    d[a-1][b-1] = c
    d[b-1][a-1] = c

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

warshall_floyd(d)

for i in range(n):
    for j in range(n):
        if i == j:
            continue
        elif d[i][j] <= L:
            d[i][j] = 1
        else:
            d[i][j] = float('inf')

warshall_floyd(d)

for s, t in st:
    if d[s-1][t-1] == float('inf'):
        print(-1)
    else:
        print(d[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())
edge = [[0]*n for _ in range(n)]
for i in range(m):
    a,b,c = map(int,input().split())
    edge[a-1][b-1] = c
    edge[b-1][a-1] = c

edge = floyd_warshall(edge)
    
for i in range(n):
    for j in range(n):
        if edge[i][j]<=l:
            edge[i][j] = 1
        else:
            edge[i][j] = 0
                
edge = floyd_warshall(edge)

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

Submission status: Accepted

Solution code:
import sys

inp = sys.stdin
# inp = open("testdata.txt", "r")
def input():
	return inp.readline().strip()

	
n, m, l = map(int, input().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

adjl = [[float('inf') for j in range(n)] for i in range(n)]
for i in range(n):
	adjl[i][i] = 0

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

adjl = warshall_floyd(adjl)

for i in range(n):
	for j in range(n):
		if i==j: adjl[i][j] = 0
		else: adjl[i][j] = 1 if adjl[i][j] <= l else float("inf")

adjl = warshall_floyd(adjl)

q = int(input())

for _ in range(q):
	a, b = map(int, input().split())
	ans = adjl[a-1][b-1]
	print(-1 if ans==float("inf") else ans-1)

Submission status: Accepted

Solution code:
from math import isinf


class WarshallFloyd(object):

    def __init__(self, adj):
        """
        ワーシャル・フロイド法によって全頂点間の最短距離を O(|V|^3) で計算する。

        :param adj: 隣接行列 adj[i][j] でi番目の頂点からj番目の頂点へのコストを示す パスがなければINF
        """
        self._dist = adj  # 各頂点間の最短距離 初期値として隣接行列をそのまま用い、[i, i]要素を0に初期化する
        for i in range(len(adj)):
            self._dist[i][i] = 0

        self._solve()

    def _solve(self):
        v_len = len(self._dist)
        for i in range(v_len):  # 経由する頂点
            for j in range(v_len):  # 開始頂点
                for k in range(v_len):  # 終端
                    self._dist[j][k] = min(self._dist[j][k], self._dist[j][i] + self._dist[i][k])

    def distance(self, start, goal):
        return self._dist[start][goal]

    def path(self, start, goal):
        pass


N, M, L = map(int, input().split())
adj = [[float('inf') for _ in range(N)] for _ in range(N)]
for A, B, C in [tuple(map(int, input().split())) for _ in range(M)]:
    adj[A - 1][B - 1] = C
    adj[B - 1][A - 1] = C

wf = WarshallFloyd(adj)

adj2 = [[float('inf') for _ in range(N)] for _ in range(N)]
for i in range(N):
    for j in range(N):
        if i == j:
            continue
        if wf.distance(i, j) <= L:
            adj2[i][j] = 1
wf2 = WarshallFloyd(adj2)

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

Submission status: Accepted

Solution code:
inf = 10 ** 10

########ワーシャルフロイド法

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

##############################
n,w,L = map(int,input().split()) #n:頂点数　w:辺の数

d = [[inf for i in range(n)] for i in range(n)] 
#d[u][v] : 辺uvのコスト(存在しないときはinf)
for i in range(w):
    x,y,z = map(int,input().split())
    x -= 1
    y -= 1
    d[x][y] = z
    d[y][x] = z
for i in range(n):
    d[i][i] = 0 #自身のところに行くコストは０
d = warshall_floyd(d)

D = [[inf for i in range(n)] for i in range(n)]

for i in range(n):
    for j in range(n):
        if i == j:
            D[i][j] = 0
        elif d[i][j] <= L:
            D[i][j] = 1

D = warshall_floyd(D)

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

Submission status: Accepted

Solution code:
########ワーシャルフロイド法

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


##############################
n, w, L = map(int, input().split())  # n:頂点数　w:辺の数
inf = 10**18
d = [[inf for i in range(n)] for _ in range(n)]
# d[u][v] : 辺uvのコスト(存在しないときはinf)
for i in range(w):
    x, y, z = map(int, input().split())
    x -= 1
    y -= 1
    d[x][y] = z
    d[y][x] = z
for i in range(n):
    d[i][i] = 0  # 自身のところに行くコストは０
d = warshall_floyd(d)

D = [[inf for i in range(n)] for i in range(n)]

for i in range(n):
    for j in range(n):
        if i == j:
            D[i][j] = 0
        elif d[i][j] <= L:
            D[i][j] = 1

D = warshall_floyd(D)

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

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import floyd_warshall

N,M,L = map(int,input().split())
abc = [[int(i) for i in input().split()] for j in range(M)]
Q = int(input())
st = [[int(i) for i in input().split()] for j in range(Q)]
INF = 1<<30
Path = [[INF for i in range(N)] for j in range(N)]
AnsPath = [[INF for i in range(N)] for j in range(N)]

def PathInit():
    for i in range(N):
        Path[i][i] = 0

PathInit()
for i,j,k in abc:
    Path[i-1][j-1] = k
    #双方向
    Path[j-1][i-1] = k

Path = floyd_warshall(Path)

for i in range(N):
    for j in range(N):
        if Path[i][j] <= L:
            AnsPath[i][j] = 1
AnsPath = floyd_warshall(AnsPath)
for s,t in st:
    if AnsPath[s-1][t-1] == INF:
        print(-1)
    else:
        print(int(AnsPath[s-1][t-1]-1))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
import numpy as np
from scipy.sparse.csgraph import floyd_warshall

n,m,l=map(int,input().split())
ans=[[0]*n for i in range(n)]
for i in range(m):
    a,b,c=[int(j) for j in input().split()]
    ans[a-1][b-1]=c
    ans[b-1][a-1]=c
q=int(input())
st=[]
for i in range(q):
    st.append([int(j)-1 for j in input().split()])

ans=floyd_warshall(ans)

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

ans=floyd_warshall(ans)

for i,j in st:
    if ans[i][j]==float("inf"):
        print(-1)
    else:
        print(int(ans[i][j])-1)

Submission status: Accepted

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

n,m,l=map(int,input().split())
ans=[[0]*n for i in range(n)]
for i in range(m):
    a,b,c=[int(j) for j in input().split()]
    ans[a-1][b-1]=c
    ans[b-1][a-1]=c
q=int(input())
st=[]
for i in range(q):
    st.append([int(j)-1 for j in input().split()])

ans=floyd_warshall(ans)

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

ans=floyd_warshall(ans)

for i,j in st:
    if ans[i][j]==float("inf"):
        print(-1)
    else:
        print(int(ans[i][j])-1)

Submission status: Accepted

Solution code:
import sys
import numpy as np
import scipy.sparse as ss
f=ss.csgraph.floyd_warshall
def main():
  t=np.fromstring(sys.stdin.buffer.read(),int,sep=' ')
  n,m,l=t[:3]
  m=m*3+3
  d=f(f(ss.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]]
  d[d>n]=0
  print('\n'.join((d.astype(int)-1).astype(str).tolist()))
main()

Submission status: Accepted

Solution code:
import sys
import numpy as np
import scipy.sparse
f=scipy.sparse.csgraph.floyd_warshall
def main():
  t=np.fromstring(sys.stdin.buffer.read(),int,sep=' ')
  n,m,l=t[:3]
  m=m*3+3
  d=f(f(scipy.sparse.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]]
  d[d>n]=0
  print('\n'.join((d.astype(int)-1).astype(str).tolist()))
main()

Submission status: Accepted

Solution code:
import sys
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall as f
def main():
  t=np.fromstring(sys.stdin.buffer.read(),int,sep=' ')
  n,m,l=t[:3]
  m=m*3+3
  d=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]]
  d[d>n]=0
  print('\n'.join((d.astype(int)-1).astype(str).tolist()))
main()

Submission status: Accepted

Solution code:
import sys
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall as f
def main():
  t=np.fromstring(sys.stdin.buffer.read(),int,sep=' ')
  n,m,l=t[:3]
  m=m*3+3
  print('\n'.join((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).astype(int)%n-1).astype(str).tolist()))
main()

Submission status: Accepted

Solution code:
import sys
from numpy import fromstring
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall
def main():
  t=fromstring(sys.stdin.buffer.read(),'i',sep=' ')
  n,m,l=t[:3]
  m=m*3+3
  print('\n'.join((floyd_warshall(floyd_warshall(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).astype(int)%n-1).astype(str).tolist()))
main()

Submission status: Accepted

Solution code:
import sys
from numpy import fromstring
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall as f
def main():
  t=fromstring(sys.stdin.buffer.read(),'i',sep=' ')
  n,m,l=t[:3]
  m=m*3+3
  print('\n'.join((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).astype(int)%n-1).astype(str).tolist()))
main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs= sys.stdin.buffer.readlines
#rstrip().decode('utf-8')

import numpy as np
#import operator
#import bisect
#from heapq import heapify,heappop,heappush
#from math import gcd
#from fractions import gcd
#from collections import deque
#from collections import defaultdict
#from collections import Counter
#from itertools import accumulate
#from itertools import groupby
#from itertools import permutations
#from itertools import combinations
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall
#from scipy.sparse.csgraph import csgraph_from_dense
#from scipy.sparse.csgraph import dijkstra
#sys.setrecursionlimit(10**7)

#map(int,input().split())

def main():
    N,M,L=map(int,input().split())
    ABCQST=np.array(read().split(),np.int64)
    ABC=ABCQST[:3*M]
    A=ABC[::3]
    B=ABC[1::3]
    C=ABC[2::3]
    ST=ABCQST[3*M+1:]
    S=ST[::2]
    T=ST[1::2]

    graph1=csr_matrix((C,(A,B)),(N+1,N+1))
    graph1_dist=floyd_warshall(graph1,directed=False)

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

    graph2_dist=floyd_warshall(graph2,directed=False)
    graph2_dist[graph2_dist==np.inf]=0
    graph2_dist=(graph2_dist+0.5).astype(int)
    ans=graph2_dist[S,T]-1
    print("\n".join(ans.astype(str)))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall as f
def main():
  t=np.fromfile(open(0,'rb'),'i',sep=' ')
  n,m,l=t[:3]
  m=m*3+3
  print('\n'.join((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).astype(int)%n-1).astype(str).tolist()))
main()

Submission status: Accepted

Solution code:
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall as f
def main():
  t=np.fromfile(open(0),'i',sep=' ')
  n,m,l=t[:3]
  m=m*3+3
  print('\n'.join((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).astype(int)%n-1).astype(str).tolist()))
main()

Submission status: Accepted

Solution code:
import sys
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall as f
def main():
  t=np.fromstring(sys.stdin.buffer.read(),'i',sep=' ')
  n,m,l=t[:3]
  m=m*3+3
  print('\n'.join((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).astype(int)%n-1).astype(str).tolist()))
main()

Submission status: Accepted

Solution code:
def main():
  import sys
  import numpy as np
  from scipy.sparse import csr_matrix
  from scipy.sparse.csgraph import floyd_warshall as f
  t=np.fromstring(sys.stdin.buffer.read(),'i',sep=' ')
  n,m,l=t[:3]
  m=m*3+3
  print('\n'.join((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).astype(str).tolist()))
main()

Submission status: Accepted

Solution code:
import sys
from numpy import*
from scipy.sparse import*
f=csgraph.floyd_warshall
def main():
  t=fromstring(sys.stdin.buffer.read(),'i',sep=' ')
  n,m,l=t[:3]
  m=m*3+3
  print('\n'.join((clip(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]],0,n).astype(int)%n-1).astype(str).tolist()))
main()

Submission status: Accepted

Solution code:
def main():
  import sys
  import numpy as np
  from scipy.sparse import csr_matrix
  from scipy.sparse.csgraph import floyd_warshall as f
  t=np.fromstring(sys.stdin.buffer.read(),'i',sep=' ')
  n,m,l=t[:3]
  m=m*3+3
  print('\n'.join((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).astype(int)%n-1).astype(str).tolist()))
main()

Submission status: Accepted

Solution code:
def main():
  import sys
  import numpy as np
  from scipy.sparse import csr_matrix
  from scipy.sparse.csgraph import floyd_warshall
  t=np.fromstring(sys.stdin.buffer.read(),'i',sep=' ')
  n,m,l=t[:3]
  t=t[3:]
  m*=3
  print('\n'.join((floyd_warshall(floyd_warshall(csr_matrix((t[2:m:3],(t[:m:3],t[1:m:3])),[n+1]*2),0)<=l)[t[m+1::2],t[m+2::2]].clip(0,n).astype(int)%n-1).astype(str).tolist()))
main()

Submission status: Accepted

Solution code:
def main():
  import sys
  import numpy as np
  from scipy.sparse import csr_matrix
  from scipy.sparse.csgraph import floyd_warshall
  t=np.fromstring(sys.stdin.buffer.read(),'i',sep=' ')
  n,m,l=t[:3]
  t=t[3:]
  m*=3
  print('\n'.join(map(str,map(int,floyd_warshall(floyd_warshall(csr_matrix((t[2:m:3],(t[:m:3],t[1:m:3])),[n+1]*2),0)<=l)[t[m+1::2],t[m+2::2]].clip(0,n)%n-1))))
main()

Submission status: Accepted

Solution code:
n,m,l=map(int,input().split())
INF=1001001001
dist=[[INF for i in range(n)] for j in range(n)]
dist2=[[INF for i in range(n)] for j in range(n)]
for i in range(n):
  dist[i][i]=0
  dist2[i][i]=0
for i in range(m):
  a,b,c=map(int,input().split())
  a-=1
  b-=1
  dist[a][b]=c
  dist[b][a]=c
#print("dist",dist)
for k in range(n):
  for i in range(n):
    for j in range(n):
      dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j])
for i in range(n):
  for j in range(n):
    if dist[i][j]<=l:
      dist2[i][j]=1
#print("dist2 pre",dist2)
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])
#print("dist2",dist2)
q=int(input())
for i in range(q):
  s,t=map(int,input().split())
  if dist2[s-1][t-1]==INF:
    print(-1)
  else:
    print(dist2[s-1][t-1]-1)