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: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from collections import deque
from heapq import heapify, heappush as hpush, heappop as hpop
N, M, L = map(int, input().split())
X = [[] for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    X[a-1].append([b-1, c])
    X[b-1].append([a-1, c])

def dijkstra(n, E, i0=0):
    h = [[0, i0]]
    D = [-1] * n
    done = [0] * n
    D[i0] = 0
    
    while h:
        d, i = hpop(h)
        done[i] = 1
        for j, w in E[i]:
            nd = d + w
            if D[j] < 0 or D[j] >= nd:
                if done[j] == 0:
                    hpush(h, [nd, j])
                    D[j] = nd
    return [d if d >= 0 else 1<<100 for d in D]
def BFS(n, E, i0=0):
    Q = deque([i0])
    D = [-1] * n
    D[i0] = 0
    while Q:
        x = Q.popleft()
        for c in E[x]:
            if D[c] == -1:
                D[c] = D[x] + 1
                Q.append(c)
    return [d if d >= 0 else 1<<100 for d in D]

Y = [[] for _ in range(N)]
for i in range(N):
    D1 = dijkstra(N, X, i)
    for j in range(N):
        if i == j: continue
        if D1[j] <= L:
            Y[i].append(j)

for _ in range(int(input())):
    s, t = map(int, input().split())
    s -= 1
    t -= 1
    a = BFS(N, Y, s)[t]-1
    print(a if a < 1 << 50 else -1)

Submission status: Time Limit Exceeded

Solution code:
import sys
from heapq import heappop, heappush


def dijkstra(s, links, f9, f30):
    q = [s]
    ret = [-1] * n
    visited = set()
    while q:
        item = heappop(q)

        v = item & f9
        if v in visited:
            continue
        visited.add(v)

        count = item >> 39
        used = (item >> 9) & f30
        ret[v] = count

        for u, c in links[v]:
            if l - used < c:
                new_item = ((count + 1) << 39) + (c << 9) + u
            else:
                new_item = (count << 39) + ((used + c) << 9) + u
            heappush(q, new_item)

    return ret


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

f9 = (1 << 9) - 1
f30 = (1 << 30) - 1

ans = [dijkstra(v, links, f9, f30) for v in range(n)]
buf = []

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

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


n, m, l = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]
graph = [[] for i in range(n)]

for i in range(m):
    a, b, cost = info[i]
    if cost > l:
        continue
    a -= 1
    b -= 1
    graph[a].append((b, cost))
    graph[b].append((a, cost))

def dfs(start):
    INF = float("inf")
    visited = [[INF, 0] for i in range(n)] # 回数, 残り燃料
    visited[start] = [0, 0]
    q = deque([start])
    while q:
        pos = q.popleft()
        for next_pos, cost in graph[pos]:
            tmp = cost + visited[pos][1]
            if tmp <= l:
                if visited[next_pos][0] > visited[pos][0]:
                    q.append(next_pos)
                    visited[next_pos] = [visited[pos][0], tmp]
                elif visited[next_pos][0] == visited[pos][0]:
                    if visited[next_pos][1] > tmp:
                        q.append(next_pos)
                        visited[next_pos] = [visited[pos][0], tmp]
                else:
                    continue
            else:
                tmp = cost
                if visited[next_pos][0] > visited[pos][0] + 1:
                    q.append(next_pos)
                    visited[next_pos] = [visited[pos][0] + 1, tmp]
                elif visited[next_pos][0] == visited[pos][0] + 1:
                    if visited[next_pos][1] > tmp:
                        q.append(next_pos)
                        visited[next_pos] = [visited[pos][0] + 1, tmp]
                else:
                    continue
    visited =list(zip(*visited))
    return visited[0]

ans = [None]*n
for i in range(n):
    ans[i] = dfs(i)

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

Submission status: Time Limit Exceeded

Solution code:
nm = lambda : map(int,input().split())
nl = lambda : list(nm())
import heapq as h

n,m,l = nm()
g = [list() for _ in range(n+1)]
ans = [0]
for _ in range(m):
    a,b,c = nm()
    g[a].append((b,c))
    g[b].append((a,c))
q = int(input())

def move(tup,cost):
    if tup[1] + cost > 0:
        if l < cost:
            return -1
        return (tup[0]+1,cost-l)
    return (tup[0],tup[1]+cost)

for st in range(1,n+1):
    dist = [-1]*(n+1)
    que = [((0,-l),st)]
    while que:
        tup,v = h.heappop(que)
        if dist[v] != -1 and dist[v] < tup:
            continue
        dist[v] = tup
        for x,c in g[v]:
            new = move(tup,c)
            if new != -1 and dist[x] == -1:
                h.heappush(que,(new,x))
    ans.append(dist)

for _ in range(q):
    s,t = nm()
    if ans[s][t] == -1:
        print(-1)
    else:
        print(ans[s][t][0])

Submission status: Time Limit Exceeded

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

D2 = [[float("inf") for i in range(n)] for i in range(n)]
for i in range(m):
    if Edge[i][2] <= l:
        D2[Edge[i][0]-1][Edge[i][1]-1] = Edge[i][2]
        D2[Edge[i][1]-1][Edge[i][0]-1] = Edge[i][2]
for i in range(n):
    D2[i][i] = 0

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

D2 = warshall_floyd(D2)

D = [[float("inf") for i in range(n)] for i in range(n)]
for i in range(m):
    if Edge[i][2] <= l:
        D[Edge[i][0]-1][Edge[i][1]-1] = 1
        D[Edge[i][1]-1][Edge[i][0]-1] = 1
for i in range(n):
    D[i][i] = 0
for i in range(n):
    for j in range(n):
        if D2[i][j] <= l:
            D[i][j] = 1

D = warshall_floyd(D)

for query in Query:
    if D[query[0]-1][query[1]-1] != float('inf'):
        print(D[query[0]-1][query[1]-1]-1)
    else:
        print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
from heapq import heappop, heappush
from operator import itemgetter
from collections import deque, defaultdict, Counter
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10**9 + 7
INF = float('inf')

def sol():
    N, M, L = map(int, input().split())
    edges = [[] for _ in range(N)]

    for _ in range(M):
        fr, to, cost = map(int, input().split())
        fr -= 1
        to -= 1
        edges[fr].append((to, cost))
        edges[to].append((fr, cost))

    Q = int(input())
    ans = []
    for _ in range(Q):
        start, end = map(int, input().split())
        start -= 1
        end -= 1

        que = [(0, start, L, 0)]
        cntList = [INF] * N
        while que:
            cnt, now, fuel, var = heappop(que)

            if cntList[now] <= cnt:
                continue

            cntList[now] = cnt

            for to, cost in edges[now]:
                c = cnt
                f = fuel
                v = var
                if f - cost < 0:
                    if v == 0:
                        continue
                    c += 1
                    f = L
                    v -= 1
                heappush(que, (c, to, f - cost, v + 1))

        if cntList[end] == INF:
            ans.append(-1)
        else:
            ans.append(cntList[end])

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

sol()

Submission status: Time Limit Exceeded

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

inf = 1e10
d1 = [[inf] * 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] = 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] * N for _ in range(N)]
for i in range(N):
    d2[i][i] = 0
for i in range(N):
    for j in range(N):
        if 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, t = s-1, t-1
    if d2[s][t] < inf:
        print(d2[s][t]-1)
    else:
        print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N, M, L = map(int, input().split())
D = [[1<<100] * N for _ in range(N)]
for i in range(N):
    D[i][i] = 0
for _ in range(M):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    D[a][b] = c
    D[b][a] = 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])
def BFS(n, E, i0=0):
    Q = deque([i0])
    D = [-1] * n
    D[i0] = 0
    while Q:
        x = Q.popleft()
        for c in E[x]:
            if D[c] == -1:
                D[c] = D[x] + 1
                Q.append(c)
    return [d if d >= 0 else 1<<100 for d in D]

Y = [[] for _ in range(N)]
for i in range(N):
    for j in range(N):
        if i == j: continue
        if D[i][j] <= L:
            Y[i].append(j)

for _ in range(int(input())):
    s, t = map(int, input().split())
    s -= 1
    t -= 1
    a = BFS(N, Y, s)[t]-1
    print(a if a < 1 << 50 else -1)

Submission status: Time Limit Exceeded

Solution code:
n,m,l = map(int, input().split())
G = [[] 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:
        G[a].append((b,c))
        G[b].append((a,c))

from collections import deque

def check(s,t):
    DP1 = [-1]*n
    DP2 = [float("inf")]*n
    
    q = deque()
    q.append((s,0,l))
    while q:
        cur, cnt, rem = q.popleft()
        if DP2[cur] < cnt:
            continue
        if DP2[cur] == cnt and DP1[cur] > rem:
            continue
        DP2[cur] = cnt
        DP1[cur] = rem
        for to, c in G[cur]:
            if rem >= c:
                if DP2[to] > cnt or (DP2[to] == cnt and DP1[to]<rem-c):
                    q.appendleft((to,cnt,rem-c))
            if DP2[to] > cnt+1:
                q.append((to,cnt+1,l-c))
    ret = DP2[t]
    if ret == float("inf"):
        ret = -1
    return ret



q = int(input())
ans = []
for i in range(q):
    s,t = map(int, input().split())
    s,t = s-1, t-1
    ans.append(check(s,t))
print(*ans, sep="\n")

Submission status: Time Limit Exceeded

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())


from heapq import heappush, heappop


def dijkstra(graph: list, start, INF=float('inf')) -> list:
    n = len(graph)
    dist = [INF] * n
    visited = [False] * n

    dist[start] = 0
    que = [(0, start)]

    while que:
        cost, cur = heappop(que)

        if visited[cur]:
            continue

        visited[cur] = True

        for nextnode, edgecost in graph[cur]:
            nextcost = cost + edgecost
            if nextcost < dist[nextnode]:
                dist[nextnode] = nextcost
                heappush(que, (nextcost, nextnode))

    return dist

n, m, l = li()
graph = [[] for _ in range(n)]
costgraph = [[] for _ in range(n)]
for _ in range(m):
    a, b, c = li()
    a -= 1
    b -= 1
    graph[a].append((b, c))
    graph[b].append((a, c))

for st in range(n):
    dist = dijkstra(graph, st)
    for ds in range(n):
        if st == ds:
            continue

        if dist[ds] <= l:
            costgraph[st].append((ds, 1))

q = ni()
INF = float("inf")

for _ in range(q):
    st, ds = li_()
    dist = dijkstra(costgraph, st, INF)
    if dist[ds] == INF:
        print(-1)
    else:
        print(dist[ds] - 1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from heapq import heapify, heappush as hpush, heappop as hpop
N, M, L = map(int, input().split())
X = [[] for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    X[a-1].append([b-1, c])
    X[b-1].append([a-1, c])

def dijkstra(n, E, i0=0):
    h = [[0, i0]]
    D = [-1] * n
    done = [0] * n
    D[i0] = 0
    
    while h:
        d, i = hpop(h)
        done[i] = 1
        for j, w in E[i]:
            nd = d + w
            if D[j] < 0 or D[j] >= nd:
                if done[j] == 0:
                    hpush(h, [nd, j])
                    D[j] = nd
    return [d if d >= 0 else 1<<100 for d in D]
def BFS(n, E, i0=0):
    Q = deque([i0])
    D = [-1] * n
    D[i0] = 0
    while Q:
        x = Q.popleft()
        for c in E[x]:
            if D[c] == -1:
                D[c] = D[x] + 1
                Q.append(c)
    return [d if d >= 0 else 1<<100 for d in D]

Y = [[] for _ in range(N)]
for i in range(N):
    D1 = dijkstra(N, X, i)
    for j in range(N):
        if i == j: continue
        if D1[j] <= L:
            Y[i].append(j)

for _ in range(int(input())):
    s, t = map(int, input().split())
    s -= 1
    t -= 1
    a = BFS(N, Y, s)[t]-1
    print(a if a < 1 << 50 else -1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from heapq import heapify, heappush as hpush, heappop as hpop
N, M, L = map(int, input().split())
X = [[] for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    X[a-1].append([b-1, c])
    X[b-1].append([a-1, c])

def dijkstra(n, E, i0=0):
    h = [[0, i0]]
    D = [1 << 100] * n
    done = [0] * n
    D[i0] = 0
    
    while h:
        d, i = hpop(h)
        done[i] = 1
        for j, w in E[i]:
            nd = d + w
            if D[j] < 0 or D[j] >= nd:
                if done[j] == 0:
                    hpush(h, [nd, j])
                    D[j] = nd
    return D
def BFS(n, E, i0=0):
    Q = deque([i0])
    D = [1<<100] * n
    D[i0] = 0
    while Q:
        x = Q.popleft()
        for c in E[x]:
            if D[c] == 1<<100:
                D[c] = D[x] + 1
                Q.append(c)
    return D

Y = [[] for _ in range(N)]
for i in range(N):
    D1 = dijkstra(N, X, i)
    for j in range(N):
        if i == j: continue
        if D1[j] <= L:
            Y[i].append(j)

for _ in range(int(input())):
    s, t = map(int, input().split())
    s -= 1
    t -= 1
    a = BFS(N, Y, s)[t]-1
    print(a if a < 1 << 50 else -1)

Submission status: Accepted

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

N, M, L = map(int, input().split())
Map = np.full((N, N), 10**12, dtype='int64')
for _ in range(M):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    Map[a][b] = c
    Map[b][a] = c
Q = int(input())
Query = [tuple(map(int, input().split())) for _ in range(Q)]
graph = floyd_warshall(Map).astype('int64')
graph[graph <= L] = 1
graph[graph > L] = 10**12
A = floyd_warshall(graph).astype('int64')
for s, t in Query:
    if A[s - 1][t - 1] >= 10**12:
        print(-1)
    else:
        print(int(A[s - 1][t - 1] - 1))

Submission status: Accepted

Solution code:
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix

f=lambda:map(int,input().split())
N,M,L=f()
G=[[0]*N for _ in [0]*N]
for _ in [0]*M:
    a,b,c=f()
    G[a-1][b-1]=c
    G[b-1][a-1]=c
    
csr=csr_matrix(G)

D=floyd_warshall(csr)
INF=float('inf')
G=[[INF]*N for _ in [0]*N]
for i in range(N):
    for j in range(N):
        if i!=j and D[i][j]<=L:
            G[i][j]=1
            G[j][i]=1
csr=csr_matrix(G)
res=floyd_warshall(csr)
Q=int(input())
for _ in [0]*Q:
    s,t=f()
    r=res[s-1][t-1]
    print(int(r-1) if r<INF else -1)

Submission status: Accepted

Solution code:
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix

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

G = np.full((N, N), np.inf)
np.fill_diagonal(G, 0)
for _ in range(M):
    a, b, c = map(int, input().split())
    G[a-1][b-1] = G[b-1][a-1] = c
D = floyd_warshall(G, directed=False)

G2 = np.full((N, N), np.inf)
np.fill_diagonal(G2, 0)
G2[D <= L] = 1
D2 = floyd_warshall(G2, directed=False)

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

Submission status: Accepted

Solution code:
import sys
import math
import heapq


def input():
    return sys.stdin.readline().rstrip()


def dijkstra(s, n, es, L):
    # n:頂点数, es: 辺uvのコスト
    d = [10 ** 14 + 7] * n
    # 探索リスト
    S = [(0, s)]
    # 優先度付きキューを使うと計算量が少なくなるよ
    heapq.heapify(S)
    used = [False] * n

    d[s] = 0

    while S:
        # 最小コストの頂点を取り出し
        dg, v = heapq.heappop(S)
        if used[v] == True:
            continue
        used[v] = True
        for u, w in es[v]:
            if d[v] % L + w > L:
                cost = d[v] - d[v] % L + L + w
            else:
                cost = d[v] + w

            if d[u] > cost:
                d[u] = cost
                heapq.heappush(S, (d[u], u))

        # print("d", d)
    return d


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

    dp = [[L+2]*N for _ in range(N)]
    for i in range(N):
        dp[i][i] =0
    for i in range(M):
        x, y, z = map(int, input().split())
        if z > L:
            continue

        x = x - 1
        y = y - 1
        dp[x][y] =z
        dp[y][x]=z



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

    ls =warshal(dp,N)
    for i in range(N):
        for j in range(N):
            if ls[i][j] <=L:
                ls[i][j] =1
            else:
                ls[i][j] =500
    vs = warshal(ls,N)

    Q =int(input())

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





if __name__ == "__main__":
    main()

# \n

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
inf = 1000
inf5 = 10**10
n, m, l = map(int, input().split())
graph = [[inf5] * (n+1) for _ in range(n+1)]
for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a][b] = c
    graph[b][a] = c

inf = 1000


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


warshall_floyd(graph)

ans = [[inf] * (n+1) for _ in range(n+1)]
for i in range(1, n+1):
    for j in range(1, n+1):
        if graph[i][j] <= l:
            ans[i][j] = 1

warshall_floyd(ans)
q = int(input())
for _ in range(q):
    s, t = map(int, input().split())
    if ans[s][t] == inf:
        print(-1)
        continue
    print(ans[s][t] - 1)

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, M, L = map(int, readline().split())
    G = [[INF] * N for _ in range(N)]
    for _ in range(M):
        a, b, c = map(int, readline().split())
        G[a - 1][b - 1] = G[b - 1][a - 1] = c
    for i in range(N):
        G[i][i] = 0

    Q, *ST = map(int, read().split())

    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]

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

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

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

    ans = [0] * Q
    for i, (s, t) in enumerate(zip(*[iter(ST)] * 2)):
        s -= 1
        t -= 1
        if H[s][t] == INF:
            ans[i] = -1
        else:
            ans[i] = H[s][t] - 1

    print(*ans, sep='\n')
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import math
import itertools
import heapq as hq
n,m,l = ma()
INF=10**15
cost = [[INF]*n for i in range(n)]
for i in range(m):
    a,b,c = ma();a-=1;b-=1
    cost[a][b]=c
    cost[b][a]=c

def wf(cost):
    l = len(cost[0])
    for k in range(l):
        for i in range(l):
            for j in range(l):
                cost[i][j] =  min(cost[i][j],cost[i][k] + cost[k][j])
wf(cost)
rest = [[INF]*n for i in range(n)]
for i in range(n):
    for j in range(n):
        if cost[i][j]<=l:
            rest[i][j]=1
wf(rest)
q = ni()
for i in range(q):
    s,t = ma();s-=1;t-=1
    print(rest[s][t] -1) if rest[s][t] !=INF else print(-1)

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heapify, heappop, heappush
import math
import random
import string
from copy import deepcopy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

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

N, M, L = getNM()
edges = [getList() for i in range(M)]
Q = getN()
query = [getList() for i in range(Q)]

dist = [[float('inf')] * N for i in range(N)]
for i in range(N):
    dist[i][i] = 0
for i in range(M):
    a, b, c = edges[i]
    dist[a - 1][b - 1] = c
    dist[b - 1][a - 1] = c

def warshall_floyd(dist):
    for k in range(N):
        # i:start j:goal k:中間地点でループ回す
        for i in range(N):
            for j in range(N):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    return dist

# まず一回回す
warshall_floyd(dist)

# distの抽象化
# edgesの張り替え
dist_alta = [[float('inf')] * N for i in range(N)]
for i in range(N):
    for j in range(i, N):
        if i == j:
            dist_alta[i][j] = 0
            continue
        if dist[i][j] <= L:
            dist_alta[i][j] = 1
            dist_alta[j][i] = 1

warshall_floyd(dist_alta)

for s, t in query:
    if dist_alta[s - 1][t - 1] == float('inf'):
        print(-1)
        continue
    print(dist_alta[s - 1][t - 1] - 1)

Submission status: Accepted

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

N,M,L=map(int,input().split())
INF = 1 << 31
dist=np.array([[INF for _ in range(N)] for _ in range(N)])

for i in range(N):
  dist[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

dist = floyd_warshall(dist)

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

dist = floyd_warshall(dist)
dist[dist==INF]=0
#dist=dist.astype(int)
#print(dist)

Q=int(input())
ans=[0]*Q
for q in range(Q):
  s,t=map(int,input().split())
  s-=1
  t-=1
  ans[q]=int(dist[s][t]-1)

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

Submission status: Accepted

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

N,M,L=map(int,input().split())
INF = 1 << 31
dist=np.array([[INF for _ in range(N)] for _ in range(N)])

for i in range(N):
  dist[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

dist = floyd_warshall(dist)

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

dist = floyd_warshall(dist)
dist[dist==INF]=0
#dist=dist.astype(int)
#print(dist)

Q=int(input())
ans=[0]*Q
for q in range(Q):
  s,t=map(int,input().split())
  s-=1
  t-=1
  ans[q]=int(dist[s][t]-1)

for a in ans:
  print(-1 if a==INF else a)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
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)]

INF = float('inf')
ds = [[INF]*N for i in range(N)]
for a,b,c in ABC:
    a,b = a-1,b-1
    ds[a][b] = ds[b][a] = c
for i in range(N):
    ds[i][i] = 0

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

ls = [[INF]*N for i in range(N)]
for i in range(N-1):
    for j in range(i+1,N):
        if ds[i][j] <= L:
            ls[i][j] = ls[j][i] = 1
for i in range(N):
    ls[i][i] = 0

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

ans = []
for s,t in ST:
    ans.append(-1 if ls[s-1][t-1]==INF else ls[s-1][t-1] - 1)
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
import sys
import math

input = sys.stdin.readline


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


N, M, L = map(int, input().split())
d = [[math.inf] * N for _ in range(N)]
for i in range(N):
    d[i][i] = 0
for _ in range(M):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    d[a][b] = c
    d[b][a] = c
warshall_floyd(d)
for i in range(N):
    for j in range(N):
        d[i][j] = 1 if d[i][j] <= L else math.inf
for i in range(N):
    d[i][i] = 0
warshall_floyd(d)


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

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
from heapq import heappop, heappush
from collections import defaultdict
from collections import Counter
from collections import deque
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())
N, M, L = map(int, input().split())
dist = [[INF] * N for _ in range(N)]
for i in range(M):
    a, b, c = map(int, input().split())
    if c > L:
        continue
    a -= 1
    b -= 1
    dist[a][b] = c
    dist[b][a] = c
Q = int(input())

for k in range(N):
    for i in range(N):
        for j in range(N):
            if dist[i][j] > dist[i][k] + dist[k][j]:
                dist[i][j] = dist[i][k] + dist[k][j]
fuel = [[INF] * N for _ in range(N)]
for i in range(N):
    for j in range(N):
        fuel[i][j] = 1 if dist[i][j] <= L else INF
for k in range(N):
    for i in range(N):
        for j in range(N):
            if fuel[i][j] > fuel[i][k] + fuel[k][j]:
                fuel[i][j] = fuel[i][k] + fuel[k][j]
for i in range(Q):
    s,t = map(int, input().split())
    if fuel[s - 1][t - 1] != INF:
        print(fuel[s - 1][t - 1] - 1)
    else:
        print(-1)