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
import numpy as np
from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall, shortest_path

input = sys.stdin.readline

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

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

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

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

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


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

	warshall_floyd(N)

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

	warshall_floyd(N)

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

main()

Submission status: Accepted

Solution code:
import sys


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

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

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

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


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

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


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

Submission status: Accepted

Solution code:
import sys


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

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

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

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


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

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


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

Submission status: Accepted

Solution code:
import sys


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

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

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

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


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

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


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

Submission status: Accepted

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


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

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

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

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

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

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

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

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

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

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

Submission status: Accepted

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

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


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

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

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

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


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

Submission status: Accepted

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

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

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

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

D = floyd_warshall(D)
D2 = (D<=L)*1.0 # boolean -> float
D2[D2==0] = np.inf
# D2 = (D <= L) + (D > L)*np.inf

D2 = floyd_warshall(D2) - 1

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

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
import numpy as np
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix
n, m, l = map(int, input().split())
F = np.zeros((n, n))
for _ in range(m):
  a, b, c = map(int, input().split())
  a -= 1
  b -= 1
  F[a, b] = c
  F[b, a] = c
csr = csr_matrix(F)
A = floyd_warshall(csr)
G = np.zeros((n, n))
for i in range(n-1):
  for j in range(i+1, n):
    if A[i][j] <= l:
      G[i, j] = 1
      G[j, i] = 1
ncsr = csr_matrix(G)
B =  floyd_warshall(ncsr)
q = int(input())
for _ in range(q):
  s, t = map(int, input().split())
  k = B[s-1][t-1]
  if k == float("inf"):
    print(-1)
  else:
    print(int(k)-1)

Submission status: Accepted

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

N,M,L=LI()

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

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

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

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

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

Submission status: Accepted

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

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

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

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

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

ws(dist1)

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

ws(dist2)

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

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import floyd_warshall

# ダイクストラを二回行う
N, M, L = map(int, input().split())
graph = [[float('inf')]*N for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    graph[a][b] = c
    graph[b][a] = c

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

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import floyd_warshall

# ダイクストラではなくワーシャルフロイドで解く
N, M, L = map(int, input().split())
# graph = [[] for _ in range(N)]
distant = [[float('inf')]*N for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    a, b = a-1, b-1
    if c > L:
        continue
    distant[a][b] = c
    distant[b][a] = c

distant = floyd_warshall(distant)
another = [[float('inf')]*N for _ in range(N)]
for i in range(N):
    for j in range(N):
        if distant[i][j] <= L:  # 行けるところまでいくという印象
            another[i][j] = 1
another = floyd_warshall(another)
Q = int(input())
for _ in range(Q):
    s, t = map(lambda x: int(x)-1, input().split())
    if another[s][t] == float('inf'):
        print(-1)
        continue
    print(int(another[s][t])-1)
    # if distant[s][t] == float('inf'):
    #     print(-1)
    #     continue
    # print(int(distant[s][t])//L + min(1, int(distant[s][t]) % L) - 1)
# 燃料が4で
# 1 -> 4 -> 2
# のとき、距離は7だから一見すると補給回数は1で良さそうだけど、実は2回必要
# 今、２点間の最小距離を求めておいて、もう一つのグラフは「最短距離がL以下の2点に辺(重み1)を張る」

Submission status: Accepted

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


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

Submission status: Accepted

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

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

Submission status: Accepted

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

def war(d):
    for k in range(N):
        for i in range(N):
            for j in range(N):
                d[i][j]=min(d[i][j],d[i][k]+d[k][j])
    return d
INF=(L+1)*N
d=[[INF]*N for _ in range(N)]
d2=[[INF]*N for _ in range(N)]

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

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

d=war(d)

for i in range(N):
    for j in range(N):
        if d[i][j]<=L:
            d2[i][j]=1
for i in range(N):
    d2[i][i]=0
d2=war(d2)
#print(d)
#print(d2)
Q=int(input())
for i in range(Q):
    s,t=map(int,input().split())
    print(d2[s-1][t-1] %INF -1)

Submission status: Accepted

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

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

#全点間最短距離を計算
G = floyd_warshall(G)


#コストL以下で移動可能な頂点間のコスト1の辺を張る
E = [[float('inf')] * N for i in range(N)]
for i in range(N):
  for j in range(N):
    if G[i][j] <= L:
      E[i][j] = 1

#全点間最短距離を計算
E = floyd_warshall(E)

#クエリに答えていく
Q = int(input())
for i in range(Q):
  s, t = map(int, input().split())
  s, t = s - 1, t-1
  print(int(E[s][t] - 1) if E[s][t] != float('inf') else -1)

Submission status: Accepted

Solution code:
from math import isinf
from scipy.sparse.csgraph import shortest_path
from scipy.sparse import csr_matrix

INF = float('inf')

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

main()

Submission status: Accepted

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

    n, m, l = map(int, input().split())
    abc = [list(map(int, input().split())) for _ in [0]*m]
    q = int(input())
    st = [list(map(int, input().split())) for _ in [0]*q]
    inf = 10**12
    dist = np.full((n, n), inf, dtype=np.int64)
    for i in range(n):
        dist[i][i] = 0
    for a, b, c in abc:
        dist[a-1][b-1] = c
        dist[b-1][a-1] = c
    dist = sp.shortest_path(dist)

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

    for i in range(n):
        for j in range(n):
            if dist2[i][j] == inf:
                dist2[i][j] = -1
            else:
                dist2[i][j] -= 1
    for s, t in st:
        print(int(dist2[s-1][t-1]))


main()

Submission status: Accepted

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

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

"""
"""

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

n,m,l = LI()

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

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

dist = warshall_floyd(dist)

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

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
#道がない場合、infで初期化したい
inf = 10 ** 13 + 1
#input
n, m, l = list(map(int, input().split()))
way = [[inf for i in range(n)] for j in range(n)]
oil = [[400 for i in range(n)] for j in range(n)]

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

q = int(input())

query = []

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

#ワーシャルフロイド法を使い、各道への最短経路を調べる。計算量はO(N**3)
for k in range(n):
    for i in range(n):
        for j in range(n):
            if i == j:
                way[i][j] = 0
                continue
            way[i][j] = min(way[i][j],way[i][k] + way[k][j])
            
#oilの補給できる回数もワーシャルフロイドで求める。まず、一補給でいけるところに辺を張る
for i in range(n):
    for j in range(n):
        if i == j:
            oil[i][j] = 0
        if way[i][j] <= l:
            oil[i][j] = oil[j][i] = 1
#の後でワーシャルフロイド
for k in range(n):
    for i in range(n):
        for j in range(n):
            if i == j:
                oil[i][j] = 0
                continue
            oil[i][j] = min(oil[i][j],oil[i][k] + oil[k][j])

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

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):
        u,v,w=map(int,input().split())
        if(w>L): continue
        u-=1; v-=1
        E[u].append((v,w))
        E[v].append((u,w))

    # 各始点からの Dijkstra
    # dist は (補給回数、補給してからの使用料)
    A=[None]*n
    for s in range(n):
        dist=[(INF,INF)]*n
        dist[s]=(0,0)
        used=[0]*n
        for _ in range(n-1):
            v=min((dist[v],v) for v in range(n) if(not used[v]))[1]
            used[v]=1
            c,l=dist[v]
            for nv,w in E[v]:
                if(l+w>L):
                    nd=(c+1,w)
                else:
                    nd=(c,l+w)
                dist[nv]=min(dist[nv],nd)
        A[s]=dist

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

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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

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

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

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

D2 = floyd_warshall(D2)

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

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    # ワーシャルフロイド
    def warshall_floyd(d, N):
        for k in range(N):
            for i in range(N):
                for j in range(N):
                    d[i][j]=min(d[i][j], d[i][k] + d[k][j])
    
    N,M,L=MI()
    ABC=LLIN(M)
    d=[[float("inf")] * N for i in range(N)]
    for i in range(N):
        d[i][i] = 0
    
    for a,b,c in ABC:
        a-=1
        b-=1
        d[a][b]=c
        d[b][a]=c

    warshall_floyd(d,N)

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

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys


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

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

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

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

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

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


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
#juppy's code for testing run time only. 
def main():
    import sys
    input = sys.stdin.readline
    n,m,l = map(int,input().split())
    d = [[10**12]*n for _ in [0]*n]
    for i in range(m):
        a,b,c = map(int,input().split())
        if l >= c:
            d[a-1][b-1] = d[b-1][a-1] = c
    for i in range(n):
        d[i][i] = 0
 
    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])
 
    edge = [[10**12]*n for _ in [0]*n]
    for i in range(n):
        for j in range(n):
            if d[i][j] <= l:
                edge[i][j] = 1
 
    for k in range(n):
        for i in range(n):
            for j in range(n):
                edge[i][j] = min(edge[i][j],edge[i][k] + edge[k][j])
 
    q = int(input())
    for _ in [0]*q:
        s,t = map(int,input().split())
        if edge[s-1][t-1] >= 10**12:
            print(-1)
        else:
            print(edge[s-1][t-1]-1)
 
if __name__ == '__main__':
    main()