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: Runtime Error

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[i][j] == 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: Runtime Error

Solution code:
import math


def main():
    [N, M, L] = [int(x) for x in input().split()]
    edge_list = [[] for _ in range(N+1)]
    for _ in range(M):
        [A, B, C] = [int(x) for x in input().split()]
        edge_list[A].append((B, C))
        edge_list[B].append((A, C))

    Q = int(input())
    st_list = []
    for _ in range(Q):
        [s, t] = [int(x) for x in input().split()]
        st_list.append((s, t))

    # ダイクストラ法により最短経路を求める
    for st in st_list:
        start = st[0]
        goal = st[1]
        unsearched_nodes = list(range(N+1))
        distance = [math.inf for _ in range(N+1)]
        distance[start] = 0
        previous_nodes = [-math.inf] * (N+1)  # 最短経路でそのノードのひとつ前に到達するノードのリスト
        previous_nodes[start] = -1
        target_min_index = start

        while len(unsearched_nodes) > 1:
            # ターゲットになるノードからのびるエッジのリスト
            for edge in edge_list[target_min_index]:
                if edge[1] > L:
                    continue
                if distance[target_min_index] + edge[1] < distance[edge[0]]:
                    distance[edge[0]] = distance[target_min_index] + edge[1]
                    previous_nodes[edge[0]] = target_min_index
            # 最少経路が確定したノードを探して取り除く
            target_min_index = -1
            posible_min_distance = math.inf
            for node_index in unsearched_nodes:
                if posible_min_distance > distance[node_index]:
                    posible_min_distance = distance[node_index]
                    target_min_index = node_index
            if target_min_index == -1:
                print(-1)
                break
            unsearched_nodes.remove(target_min_index)
            if target_min_index == goal:
                # print('res', distance[goal], previous_nodes)
                break

        if target_min_index == -1:
            continue

        pass_node_list = []
        previous_node = goal
        while previous_node != -1:
            pass_node_list.append(previous_node)
            previous_node = previous_nodes[previous_node]
        pass_node_list = list(reversed(pass_node_list))
        # print(pass_node_list)

        fuel = L
        charge_num = 0
        for idx in range(len(pass_node_list)-1):
            for edge in edge_list[pass_node_list[idx]]:
                if edge[0] == pass_node_list[idx+1]:
                    if fuel >= edge[1]:
                        fuel -= edge[1]
                    else:
                        fuel = L - edge[1]
                        charge_num += 1
        print(charge_num)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

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, np.ones_like(res), np.zeros_like(res))
new_res = floyd_warshall(csgraph_from_dense(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: Runtime Error

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_from_dense(res)
res = np.where(res <= l, np.ones_like(res), np.zeros_like(res))
new_res = floyd_warshall(csgraph_from_dense(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: Runtime Error

Solution code:
import sys
import numpy as np
from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
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))
res = np.where(res <= l, np.ones_like(res), np.zeros_like(res))
if issparse(res):
    new_res = floyd_warshall(res)
else:
    new_res = floyd_warshall(csgraph_from_dense(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: Runtime Error

Solution code:
import sys
import numpy as np
from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
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))
res = np.where(res <= l, np.ones_like(res), np.zeros_like(res))

new_res = floyd_warshall(csgraph_from_dense(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: Runtime Error

Solution code:
import sys
import numpy as np
from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
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))
res = np.where(res <= l, np.ones_like(res), np.zeros_like(res))

new_res = floyd_warshall(csgraph_from_dense(res))
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] if not np.isinf(new_res[s, t]) else 0
    print(int(dis) - 1)

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
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))
res = np.where(res <= l, np.ones_like(res), np.zeros_like(res))

new_res = floyd_warshall(csgraph_from_dense(res))
q = int(input())
for i in range(q):
    s, t = [int(i) for i in sys.stdin.readline().split()]
    s -= 1
    t -= 1
    dis = new_res[s][t] if not np.isinf(new_res[s][t]) else 0
    print(int(dis) - 1)

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
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))
res = np.where(res <= l, 1, 0)

new_res = floyd_warshall(csgraph_from_dense(res))
q = int(input())
for i in range(q):
    s, t = [int(i) for i in sys.stdin.readline().split()]
    s -= 1
    t -= 1
    dis = new_res[s][t] if not np.isinf(new_res[s][t]) else 0
    print(int(dis) - 1)

Submission status: Runtime Error

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

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))
res = np.where(res <= l, 1, 0)

new_res = floyd_warshall(csgraph_from_dense(res))
q = int(input())
for i in range(q):
    s, t = [int(i) for i in sys.stdin.readline().split()]
    s -= 1
    t -= 1
    dis = new_res[s][t] if not np.isinf(new_res[s][t]) else 0
    print(int(dis) - 1)

Submission status: Runtime Error

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

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

for k in range(M):
    a,b,c = map(int,input().split())
    gurahu[a-1,b-1] = c
    gurahu[b-1,a-1] = c

gurahu = floyd_warshall(gurahu, directed=False)
gurahu = np.where(gurahu <= L and gurahu > 0, 1, 0)
gurahu = floyd_warshall(gurahu) - np.ones((N, N))

Q = int(input())

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

Submission status: Runtime Error

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

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

for k in range(M):
    a,b,c = map(int,input().split())
    gurahu[a-1][b-1] = c
    gurahu[b-1][a-1] = c

gurahu = floyd_warshall(gurahu, directed=False)
for s in range(N):
    for t in range(N):
        if gurahu[s][t] <= L:
            gurahu[s][t] = 0
        else:
            gurahu[s][t] = 1
gurahu = floyd_warshall(gurahu)

Q = int(input())

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

Submission status: Runtime Error

Solution code:
from collections import defaultdict



def dijkstra(s,t,route,n,w,l):
      d = [float("inf")] * n
    d[s] = 0

    unusedlist = list(range(n))
      
    while True:
          max = float("inf")
        max_i = -1
        for i,item in enumerate(unusedlist):
            if d[item] < max:
                max = d[item]
                max_i = i
            
        if max_i == -1:
               break
           
        v = unusedlist[max_i]
        del unusedlist[max_i]

        e_l = d[v]
        subcost = route[v]
        if subcost == 0: continue
        for j in unusedlist: #range(n):
            try:
                cost = subcost[j]
            except:
                continue
            if cost == 0: continue

            if l-e_l%l >= cost:
                next_d = e_l + cost
            else:
                next_d = (1 + e_l//l)*l + cost
            d[j] = min(d[j],next_d)

    if not t in unusedlist:
        return (d[t]-1)//l
    else:
        return -1



if __name__ == '__main__':
    route = defaultdict(defaultdict)

    n,m,l = list(map(lambda x: int(x), input().split()))

    for i_num in range(m):
        a,b,c = list(map(lambda x: int(x), input().split()))

        if c > l:
            m -= 1
            continue
        else:
            route[a-1][b-1] = c
            route[b-1][a-1] = c
 
    q = int(input())

    for i_num in range(q):
        s,t = list(map(lambda x: int(x), input().split()))    
        print(dijkstra(s-1,t-1,route,n,m,l))

Submission status: Runtime Error

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

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

graph = [[float('inf') for _ in range(n)] for _ in range(n)]


for a, b, c in abc:
    graph[a-1][b-1] = c 
    graph[b-1][a-1] = c
for i in range(n):
    graph[i][i] = 0

# print(graph)

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

graph = warshall_floyd(graph)

for i in range(n):
    for j in range(n):
        if i!=j and graph[i][j] <= l:
            graph[i][j] = 1
        if graph[i][j] > l:
            graph[i][j] = float('inf')

graph = warshall_floyd(graph)

for s, t in st:
    print(graph[s-1][t-1]-1 if graph[s-1][t-1] != float('inf') else -1)

Submission status: Runtime Error

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

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

graph = [[float('inf') for _ in range(n)] for _ in range(n)]


for a, b, c in abc:
    graph[a-1][b-1] = c 
    graph[b-1][a-1] = c
for i in range(n):
    graph[i][i] = 0

# print(graph)

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

graph = warshall_floyd(graph)

for i in range(n):
    for j in range(n):
        if 0 < graph[i][j] <= l:
            graph[i][j] = 1
        if graph[i][j] > l:
            graph[i][j] = float('inf')

graph = warshall_floyd(graph)

for s, t in st:
    print(graph[s-1][t-1]-1 if graph[s-1][t-1] != float('inf') else -1)

Submission status: Runtime Error

Solution code:
N, M, L = map(int, input().split())
singular = [[float('inf') for i in range(N)] for j in range(N)]
for i in range(N): edges[i][i] = 0
for i in range(M):
    A, B, C = map(int, input().split())
    A, B = A-1, B-1
    singular[A][B] = C
    singular[B][A] = C

for k in range(N):
    for i in range(N):
        for j in range(N):
            singular[i][j] = min(singular[i][j], singular[i][k] + singular[k][j])
for i in range(N):
    for j in range(N):
        if singular[i][j] <= L:
            singular[i][j] = 0
        else:
            singular[i][j] = float('inf')

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

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

Submission status: Runtime Error

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

"""
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 = map(int, input().split())

d = [[0 for i 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[i][i] = 0

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


for i in range(N):
    for j in range(N):
        if d[i][j] <= L:
            S[i][j] = 1
            S[j][i] = 1
            
S = floyd_warshall(S, directed = False)

Q = int(input())

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

Submission status: Runtime Error

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

"""
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 = map(int, input().split())

d = [[0 for i 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[i][i] = 0

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


for i in range(N):
    for j in range(N):
        if d[i][j] <= L:
            S[i][j] = 1
            S[j][i] = 1
            
S = floyd_warshall(S, directed = False)

Q = int(input())

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

Submission status: Runtime Error

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

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

d = [[float("inf") for i in range(N)] for i in range(N)]

for i in range(M):
    A, B, C = map(int, input().split())
    if C <= L:
        d[A-1][B-1] = C
        d[B-1][A-1] = C
for i in range(N):
    d[i][i] = 0

s = [[0] * N for _ in range(N)]
d2 = warshall_floyd(d)

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

warshall_floyd(s)



Q = int(input())

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

Submission status: Runtime Error

Solution code:
# ワ―シャルフロイドで解くよ
def main():
    import sys
    input = sys.stdin.readline  # 1行ごとの入力を繰り返し扱う場合の高速化
    N, M, L = map(int, input().split())
    # distanceを格納(未到達は無限遠として初期化)
    d = [[10 ** 12] * N for _ in range(N)]  
    # input-edges
    for i in range(M):
        a, b, c = map(int, input().split())
        if L >= c: # 距離がLより大きいのは無視
            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][k] + d[k][j], d[i][j])
    
    # 先ほど求めた町間の内、最短距離がL以下のものを距離1で結ぶ。
    edge = [[10 ** 12] * N for _ in range(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][k] + edge[k][j], edge[i][j])
    
    # input-query
    Q = int(input())
    for _ in range(N):
        s, t = map(int, input().split())
        if edge[s - 1][t - 1] >= 10 ** 12:
            print(-1)
        else:
            print(edge[s - 1][t - 1] - 1)  # 最初に燃料Lがある分、マイナス1をする。
    
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
n, m, l = map(int, input().split())
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
inf = 10**12
d = [[inf for i in range(n)] for i in range(n)] 
#d[u][v] : 辺uvのコスト(存在しないときはinf)
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 #自身のところに行くコストは０
dd = warshall_floyd(d)
ddd = [[inf for i in range(n)] for i in range(n)]
for i in range(n):
  for j in range(n):
    if dd[i][j] <= l:
      ddd[i][j] = 1
dddd = warshall_floyd(ddd)
q = int(input())
for i in range(q):
  s, t = map(int, input().split())
  if dddd[s][t] == inf:
    print(-1)
  else:
    print(dddd[s-1][t-1]-1)

Submission status: Runtime Error

Solution code:
n, m, l = map(int, input().split())
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
inf = 10**12
d = [[inf for i in range(n)] for i in range(n)] 
#d[u][v] : 辺uvのコスト(存在しないときはinf)
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 #自身のところに行くコストは０
dd = warshall_floyd(d)
ddd = [[inf for i in range(n)] for i in range(n)]
for i in range(n):
  for j in range(n):
    if dd[i][j] <= l:
      ddd[i][j] = 1
dddd = warshall_floyd(ddd)
q = int(input())
for i in range(q):
  s, t = map(int, input().split())
  if dddd[s][t] == inf:
    print(-1)
  else
    print(dddd[s-1][t-1]-1)

Submission status: Runtime Error

Solution code:
INF=10**18
N,M,L=map(int,input().split())
d=[[INF for i in range(N)] for j in range(N)]
for i in range(N):
    d[i][i]=0
for m in range(M):
    A,B,C=map(int,input().split())
    d[A-1][B-1]=C
    d[B-1][A-1]=C

for k in range(N):
    for i in range(N):
        for j in range(N):
            d[i][j]=min(d[i][j],d[i][k]+d[k][j])
for i in range(N):
        for j in range(N):
            if d[i][j]<=L:
                d[i][j]=1
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])
ans=[]
Q=int(input())
for i in range(Q):
    s,t=map(int,input().split())
    dis=d[s-1][t-1]
    if dis==INF:
        ans.append(-1)
    else:
        ans.append(dis-1)

for a in ans:
    print(int(a))

Submission status: Runtime Error

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

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

T = []
T1 = []
for _ in range(N):
    T.append([float("inf")] * N)
    T1.append([float("inf")] * N)
for n in range(N):
    T[n][n] = 0
    T1[n][n] = 0

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

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

for j in range(N):
    for i in range(N):
        if i == j:
            continue
        if T[j][i] <= L:
            T1[j][i] = 1
            T1[i][j] = 1

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

Q = int(input())
for _ in range(Q):
    S, G = list(map(int, input().split()))
    if math.isinf(T1[S-1][G-1]):
        print(-1)
    else:
        print(T1[S-1][G-1]-1)

Submission status: Runtime Error

Solution code:
n, m, l = map(int, input().split())
abc = [tuple(map(int,input().split())) for i in range(m)]
q = int(input())
st = [tuple(map(int,input().split())) for i in range(q)]

lmod = 10^len(str(l))

def warshall_floyd(dp):
    #d[i][j]: iからjへの最短距離 + lmod * 補給回数
    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])
                if dp[i][j]%lmod >= l:
                    dp[i][j] = dp[i][j] - l + lmod 

    return dp


dp = [[float('inf') for i in range(n)] for i in range(n)] 
for a,b,c in abc:
    a = a - 1
    b = b - 1
    if c > l:
        c = float('inf')     
    
    dp[a][b] = c
    dp[b][a] = c
for i in range(n):
    dp[i][i] = 0

dp_ = warshall_floyd(dp)



for s,t in st:
    s = s-1
    t = t-1
    if dp_[s][t] == float('inf'):
        print(-1)
    else:
        print(dp_[s][t]//lmod)

Submission status: Runtime Error

Solution code:
import sys

N, M, L = list(map(int, sys.stdin.readline().strip().split(" ")))
INF = 10**10

def warshall_floyd(g_mat):
    dp = [[INF for _ in range(N)] for _ in range(N)]
    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])
    return dp

graph = [[INF for _ in range(N)] for _ in range(N)]

for _ in range(M):
    a, b, c = list(map(int, sys.stdin.readline().strip().split(" ")))
    graph[a-1][b-1] = c
    graph[b-1][a-1] = c

dist_graph = warshall_floyd(graph)
bool_graph = [[INF for _ in range(N)] for _ in range(N)]

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

ans_graph = warshall_floyd(bool_graph)

Q = int(sys.stdin.readline().strip())
for _ in range(Q):
    s, t = list(map(int, sys.stdin.readline().strip().split(" ")))
    ans = ans_graph[s][t]
    print(ans if ans != INF else -1)

Submission status: Runtime Error

Solution code:
#import numpy as np
import sys
from scipy.sparse.csgraph import floyd_warshall,csgraph_from_dense
from scipy.sparse import csr_matrix
input = sys.stdin.readline
def inputs():return [int(x) for x in input().split()]
N = int(input())
a,b =inputs()
M = int(input())
graph= [[10**9]*(N+1) for _ in range(N+1)]
E = {i:[] for i in range(N+1)}
for i in range(M):
  x,y = inputs()
  graph[x][y] = 1
  graph[y][x] = 1
  E[x].append(y)
  E[y].append(x)
G = csgraph_from_dense(graph, null_value=10**9)
dist_mat = floyd_warshall(graph,directed=False)
visited=[-1]*(N+1)
stk =[[a,-1,0]]
cnt=0
while stk:
  v,p,path =stk.pop()
  if v==b and path==dist_mat[a][b]:
    cnt+=1
    cnt%=(10**9+7)
  #visited[v]=1
  for i in E[v]:
    if i != p and path<dist_mat[a][b]:
      stk.append([i,v,path+1])
print(cnt%(10**9+7))

Submission status: Runtime Error

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

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

ABCQST = np.array(read().split(), dtype=np.int64)
ABC = ABCQST[:3*M]
A = ABC[::3]; B = ABC[1::3]; C = ABC[2::3]

Q = ABCQST[3*M]

ST = ABCST[3*M + 1:]
S = ST[::2]; T = ST[1::2]

graph = csr_matrix((C, (A, B)), (N, N))
d = floyd_warshall(graph, directed=False)

d[d <= L] = 1
d[d > L] = INF

d = floyd_warshall(d, directed=False).astype(int)
d[d == INF] = 0

d -= 1
print('\n'.join(d.astype(str)[S, T]))

Submission status: Runtime Error

Solution code:
import numpy as np
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix
INF = 10**12
N, M, L = map(int, input().split())

A = []; B = []; C = []
for i in range(M):
    a, b, c = map(int, input().split())
    A.append(a - 1); B.append(b - 1); C.append(c)
A = np.array(A); B = np.array(B); C = np.array(C)

graph = csr_matrix((C, (A, B)), (N, N))
d = floyd_warshall(graph, directed=False)

d[0 < d <= L] = 1
#d[d > L] = INF

d = floyd_warshall(d, directed=False)

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

Submission status: Runtime Error

Solution code:
import numpy as np
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix
INF = 10**12
N, M, L = map(int, input().split())

A = []; B = []; C = []
for i in range(M):
    a, b, c = map(int, input().split())
    A.append(a - 1); B.append(b - 1); C.append(c)
A = np.array(A); B = np.array(B); C = np.array(C)

graph = csr_matrix((C, (A, B)), (N, N))
d = floyd_warshall(graph, directed=False)

d[d <= L] = 1
d[d > L] = INF

d = floyd_warshall(d, directed=False)

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