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
sys.setrecursionlimit(pow(10, 6))

def main():
    n, m, l = map(int, input().split())
    d = [[float("inf") for _ in range(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())
        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):
                if d[i][j] > d[i][k] + d[k][j]:
                    d[i][j] = d[i][k] + d[k][j]
    
    dl = [[float("inf") for _ in range(n)] for _ in range(n)]
    for i in range(n):
        d[i][i] = 0

    for i in range(n):
        for j in range(i+1, n):
            if i != j and d[i][j] <= l:
                dl[i][j] = 1
                dl[j][i] = 1
    
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dl[i][j] > dl[i][k] + dl[k][j]:
                    dl[i][j] = dl[i][k] + dl[k][j]
    
    q = int(input())
    for _ in range(q):
        s, t = map(int, input().split())
        if dl[s-1][t-1] == float("inf"):
            print(-1)
        else:
            print(dl[s-1][t-1] - 1)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

S = [[float("inf")] * N for _ in range(N)]
warshall_floyd(d)

for i in range(N):
    for j in range(N):
        if d[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-1][t-1] == float("inf"):
        print(-1)
    else: 
        print(S[s-1][t-1]-1)

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy

N, M, L = map(int, input().split())
inf = 10**9 + 1
dist = [[inf] * N for i in range(N)]
for i in range(M):
    A, B, C = map(int, input().split())
    dist[A-1][B-1] = dist[B-1][A-1] = C

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

refill = [list(map(lambda x: 1 if x <= L else inf, d)) for d in dist]
for k in range(N):
    for i in range(N):
        for j in range(i+1, N):
            min_refill = min(refill[i][j], refill[i][k] + refill[k][j])
            refill[i][j] = refill[j][i] = min_refill

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from itertools import accumulate as acc
import bisect


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

l=[[10**12 for j in range(N+1)] for i in range(N+1)]
for i in range(M):
    a,b,c=map(int,input().split())
    l[a][b],l[b][a]=c,c

for i in range(1,N+1):
    for j in range(1,N+1):
        if i!=j:    
            p=l[i][j]
            for k in range(1,j):
                q=min(l[k][j],p+l[i][k])
                l[k][j],l[j][k]=q,q


l_2=[[1000 for j in range(N+1)] for i in range(N+1)]
for i in range(1,N+1):
    for j in range(1,i):
        if l[i][j]<=L: l_2[i][j],l_2[j][i]=1,1


for i in range(1,N+1):
    for j in range(1,N+1):
        if i!=j:
            p=l_2[i][j]
            for k in range(1,j):
                q=min(l_2[k][j],p+l_2[i][k])
                l_2[k][j],l_2[j][k]=q,q

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

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from itertools import accumulate as acc
import bisect


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

l=[[10**12 for j in range(N+1)] for i in range(N+1)]
for i in range(M):
    a,b,c=map(int,input().split())
    l[a][b],l[b][a]=c,c

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

l_2=[[1000 for j in range(N+1)] for i in range(N+1)]
for i in range(1,N+1):
    for j in range(1,i):
        if l[i][j]<=L: l_2[i][j],l_2[j][i]=1,1


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

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

Submission status: Time Limit Exceeded

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-1][t-1] == inf:
    print(-1)
  else:
    print(dddd[s-1][t-1]-1)

Submission status: Time Limit Exceeded

Solution code:
def main():
    INF = float('inf')
    N, M, L = map(int, input().split())
    g = [[INF for i in range(N)] for j in range(N)]
    dist = [[INF for i in range(N)] for j in range(N)]
    
    for i in range(M):
        a, b, c = map(int, input().split())
        if c >= g[a-1][b-1]: continue
        g[a-1][b-1] = c
        g[b-1][a-1] = c
        
    for i in range(N): 
        g[i][i] = 0
        dist[i][i] = 0
        
    for k in range(N):
        for i in range(N):
            for j in range(N):
                g[i][j] = min(g[i][j], g[i][k] + g[k][j])
        
    for i in range(N):
        for j in range(N):
            if i == j: continue
            elif g[i][j] <= L: dist[i][j] = 1
    
    for k in range(N):    
        for i in range(N):
            for j in range(N):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
             
    for i in range(int(input())):
        s, t = map(int, input().split())
        if dist[s-1][t-1] == INF: print(-1)
        else: print(dist[s-1][t-1] - 1)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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()))
    T[A-1][B-1] = C
    T[B-1][A-1] = C

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

for j in range(N):
    for i in range(N):
        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):
            T1[i][j] = min(T1[i][j], T1[i][k] + T1[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: Time Limit Exceeded

Solution code:
import numpy as np
INF=10**18
N,M,L=map(int,input().split())
d=np.zeros((N,N))
d[:,:]=INF
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: Time Limit Exceeded

Solution code:
n, m, l = map(int, input().split())
d = [[float('inf')] * n for _ in range(n)]
for _ in range(m):
    a, b, c = map(int, input().split())
    d[a-1][b-1] = c
    d[b-1][a-1] = c
for i in range(n):
    for j in range(n):
        for k in range(n):
            d[j][k] = min(d[j][k], d[j][i] + d[i][k])
d2 = [[float('inf')] * n for _ in range(n)]
for i in range(n):
    for j in range(n):
        if d[i][j] <= l:
            d2[i][j] = 1
for i in range(n):
    for j in range(n):
        for k in range(n):
            d2[j][k] = min(d2[j][k], d2[j][i] + d2[i][k])
q = int(input())
for _ in range(q):
    s, t = map(int, input().split())
    print(d2[s-1][t-1]-1 if d2[s-1][t-1] != float('inf') else -1)

Submission status: Time Limit Exceeded

Solution code:
def f_e():
    n, m ,l = map(int, input().split())
    g = [[float("inf")]*n for _ in range(n)]
    g2 = [[float("inf")]*n for _ in range(n)]
    for i in range(n):
        g[i][i] = 0
        g2[i][i] = 0

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

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

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

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

    q = int(input())
    for _ in range(q):
        s, t = map(lambda x: int(x)-1, input().split())
        print(g2[s][t]-1 if g2[s][t]<float("inf") else -1)

if __name__ == "__main__":
    f_e()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
import math

n,m,l = map(int,input().split())
adj = [[float('inf') for _ in range(n)] for _ in range(n)]
for _ in range(m):
    a,b,c = map(int,input().split())
    if c <= l:
        adj[a-1][b-1] = c
        adj[b-1][a-1] = c
    
import heapq

class Dijkstra(object):
    def dijkstra(self, adj, start):
        num = len(adj)          # グラフのノード数
        dist = [[float('inf'), float('inf')] for i in range(num)] # 始点から各頂点までの最短距離を格納する
        
        dist[start] = (0, 0)
        q = []                  # プライオリティキュー．各要素は，(startからある頂点vまでの仮の距離, 頂点vのID)からなるタプル
        heapq.heappush(q, (0, 0, start)) # 始点をpush

        while len(q) != 0:
            prov_cost, prov_fuel, src = heapq.heappop(q) # pop
            
            # 他の頂点の探索
            for dest in range(num):
                cost = adj[src][dest]
                if cost != float('inf'):
                    if prov_fuel + cost <= l:
                        new_cost = prov_cost
                        new_fuel = prov_fuel + cost
                    else:
                        new_cost = prov_cost + 1
                        new_fuel = cost
                    if dist[dest][0] > new_cost or (dist[dest][0] == new_cost and dist[dest][1] > new_fuel):
                        dist[dest] = (new_cost, new_fuel)
                        heapq.heappush(q, (new_cost, new_fuel, dest))
                        
        return dist



ans = []
for i in range(n):
    ans.append(Dijkstra().dijkstra(adj, i))
q = int(input())
for _ in range(q):
    s,t = map(int,input().split())
    if ans[s-1][t-1][0] == float('inf'):
        print(-1)
    else:
        print(ans[s-1][t-1][0])

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
import math

n,m,l = map(int,input().split())
adj = [[float('inf') for _ in range(n)] for _ in range(n)]
for _ in range(m):
    a,b,c = map(int,input().split())
    if c <= l:
        adj[a-1][b-1] = c
        adj[b-1][a-1] = c
    
import heapq

class Dijkstra(object):
    def dijkstra(self, adj, start, goal=None):
        num = len(adj)          # グラフのノード数
        dist = [[float('inf'), float('inf')] for i in range(num)] # 始点から各頂点までの最短距離を格納する
        prev = [float('inf') for i in range(num)] # 最短経路における，その頂点の前の頂点のIDを格納する
        
        dist[start] = [0, 0]
        q = []                  # プライオリティキュー．各要素は，(startからある頂点vまでの仮の距離, 頂点vのID)からなるタプル
        heapq.heappush(q, (0, 0, start)) # 始点をpush

        while len(q) != 0:
            prov_cost, prov_fuel, src = heapq.heappop(q) # pop
            
            # 他の頂点の探索
            for dest in range(num):
                cost = adj[src][dest]
                if cost != float('inf'):
                    if prov_fuel + cost <= l:
                        new_cost = prov_cost
                        new_fuel = prov_fuel + cost
                    else:
                        new_cost = prov_cost + 1
                        new_fuel = cost
                    if dist[dest][0] > new_cost or (dist[dest][0] == new_cost and dist[dest][1] > new_fuel):
                        dist[dest] = [new_cost, new_fuel]
                        heapq.heappush(q, (new_cost, new_fuel, dest))
                        prev[dest] = src            
                        
        if goal is not None:
            return self.get_path(goal, prev)
        else:
            return dist

    def get_path(self, goal, prev):
        '''
        始点startから終点goalまでの最短経路を求める
        '''
        path = [goal]           # 最短経路
        dest = goal

        # 終点から最短経路を逆順に辿る
        while prev[dest] != float('inf'):
            path.append(prev[dest])
            dest = prev[dest]

        # 経路をreverseして出力
        return list(reversed(path))

ans = []
for i in range(n):
    ans.append(Dijkstra().dijkstra(adj, i))
q = int(input())
for _ in range(q):
    s,t = map(int,input().split())
    if ans[s-1][t-1][0] == float('inf'):
        print(-1)
    else:
        print(ans[s-1][t-1][0])

Submission status: Time Limit Exceeded

Solution code:
from sys import setrecursionlimit as SRL, stdin

SRL(10 ** 7)
rd = stdin.readline
rrd = lambda: map(int, rd().strip().split())

n, m, l = rrd()
dis = [[10 ** 10] * 305 for _i in range(305)]
need = [[10 ** 10] * 305 for _i in range(305)]
for i in range(n):
    dis[i][i] = 0
for i in range(m):
    a, b, c = rrd()
    dis[a][b] = c
    dis[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 k in [i, j] or i in [k, j] or j in [i, k]:
                continue
            dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j])

for i in range(1, n + 1):
    for j in range(1, n + 1):
        if i == j:
            need[i][j] = 0
        elif dis[i][j] <= l:
            need[i][j] = 1

for k in range(1, n + 1):
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            if k in [i, j] or i in [k, j] or j in [i, k]:
                continue
            need[i][j] = min(need[i][j], need[i][k] + need[k][j])
q = int(input())

while q:
    s, t = rrd()
    if need[s][t] < 10 ** 10:
        print(need[s][t]-1)
    else:
        print(-1)
    q -= 1

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    return

#B
def B():
    return

#C
def C():
    return

#D
def D():
    return

#E
def E():
    n, m, l = LI()
    dist = [[inf] * n for i in range(n)]

    for _ in range(m):
        a, b, c = LI_()
        c += 1
        if c > l:
            continue
        dist[a][b] = c
        dist[b][a] = c

    supply = [[n] * n for i in range(n)]
    for k in range(n):
        distk = dist[k]
        for i in range(n):
            if i == k:
                continue
            disti = dist[i]
            for j in range(i + 1, n):
                if disti[k] + distk[j] < disti[j]:
                    disti[j] = disti[k] + distk[j]
                    dist[j][i] = disti[j]

    lis = [[] for i in range(n)]
    for i in range(n):
        for j in range(i + 1, n):
            if dist[i][j] <= l:
                supply[i][j] = 0
                supply[j][i] = 0
                lis[i].append(j)
                lis[j].append(i)

    for i in range(n):
        q = []
        for k in lis[i]:
            heappush(q, (0, k))
        supplyi = supply[i]

        while q:
            time, p = heappop(q)
            for k in lis[p]:
                if supplyi[k] > time:
                    supplyi[k] = time + 1
                    heappush(q, (time + 1, k))

    q = II()
    for _ in range(q):
        s, t = LI_()
        if dist[s][t] == inf:
            print(-1)
            continue
        else:
            print(supply[s][t])
    return


#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == '__main__':
    E()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    return

#B
def B():
    return

#C
def C():
    return

#D
def D():
    return

#E
def E():
    n, m, l = LI()
    dist = [[inf] * n for i in range(n)]

    for _ in range(m):
        a, b, c = LI_()
        c += 1
        if c > l:
            continue
        dist[a][b] = c
        dist[b][a] = c

    supply = [[n] * n for i in range(n)]
    for k in range(n):
        distk = dist[k]
        for i in range(n):
            if i == k:
                continue
            disti = dist[i]
            for j in range(i + 1, n):
                if disti[k] + distk[j] < disti[j]:
                    disti[j] = disti[k] + distk[j]
                    dist[j][i] = disti[j]

    lis = [[] for i in range(n)]
    for i in range(n):
        for j in range(i + 1, n):
            if dist[i][j] <= l:
                supply[i][j] = 0
                supply[j][i] = 0
                lis[i].append(j)
                lis[j].append(i)

    for i in range(n):
        q = []
        for k in lis[i]:
            heappush(q, (0, k))
        supplyi = supply[i]

        while q:
            time, p = heappop(q)
            distp = dist[p]
            for k in lis[p]:
                if supplyi[k] > time:
                    supplyi[k] = time + 1
                    heappush(q, (time + 1, k))

    q = II()
    for _ in range(q):
        s, t = LI_()
        if dist[s][t] == inf:
            print(-1)
            continue
        else:
            print(supply[s][t])
    return


#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == '__main__':
    E()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    return

#B
def B():
    return

#C
def C():
    return

#D
def D():
    return

#E
def E():
    n, m, l = LI()
    dist = [[inf] * n for i in range(n)]

    for _ in range(m):
        a, b, c = LI_()
        c += 1
        if c > l:
            continue
        dist[a][b] = c
        dist[b][a] = c

    supply = [[n] * n for i in range(n)]
    for k in range(n):
        distk = dist[k]
        for i in range(n):
            if i == k:
                continue
            disti = dist[i]
            for j in range(i + 1, n):
                if disti[k] + distk[j] < disti[j]:
                    disti[j] = disti[k] + distk[j]
                    dist[j][i] = disti[j]

    lis = [[] for i in range(n)]
    for i in range(n):
        for j in range(i + 1, n):
            if dist[i][j] <= l:
                supply[i][j] = 0
                supply[j][i] = 0
                lis[i].append(j)
                lis[j].append(i)

    for i in range(n):
        q = []
        for k in lis[i]:
            heappush(q, (0, k))
        supplyi = supply[i]

        while q:
            time, p = heappop(q)
            distp = dist[p]
            for k in lis[p]:
                if distp[k] <= l and supplyi[k] > time:
                    supplyi[k] = time + 1
                    heappush(q, (time + 1, k))

    q = II()
    for _ in range(q):
        s, t = LI_()
        if dist[s][t] == inf:
            print(-1)
            continue
        else:
            print(supply[s][t])
    return


#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == '__main__':
    E()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    return

#B
def B():
    return

#C
def C():
    return

#D
def D():
    return

#E
def E():
    n, m, l = LI()
    dist = [[inf] * n for i in range(n)]

    for _ in range(m):
        a, b, c = LI_()
        c += 1
        if c > l:
            continue
        dist[a][b] = c
        dist[b][a] = c

    supply = [[n] * n for i in range(n)]
    for k in range(n):
        distk = dist[k]
        for i in range(n):
            if i == k:
                continue
            disti = dist[i]
            for j in range(i + 1, n):
                if disti[k] + distk[j] < disti[j]:
                    disti[j] = disti[k] + distk[j]
                if distk[i] + dist[j][k] < dist[j][i]:
                    dist[j][i] = distk[i] + dist[j][k]

    lis = [[] for i in range(n)]
    for i in range(n):
        for j in range(i + 1, n):
            if dist[i][j] <= l:
                supply[i][j] = 0
                supply[j][i] = 0
                lis[i].append(j)
                lis[j].append(i)

    for i in range(n):
        q = []
        for k in lis[i]:
            heappush(q, (0, k))
        supplyi = supply[i]

        while q:
            time, p = heappop(q)
            distp = dist[p]
            for k in lis[p]:
                if distp[k] <= l and supplyi[k] > time:
                    supplyi[k] = time + 1
                    heappush(q, (time + 1, k))

    q = II()
    for _ in range(q):
        s, t = LI_()
        if dist[s][t] == inf:
            print(-1)
            continue
        else:
            print(supply[s][t])
    return


#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == '__main__':
    E()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    return

#B
def B():
    return

#C
def C():
    return

#D
def D():
    return

#E
def E():
    n, m, l = LI()
    dist = [[inf] * n for i in range(n)]

    for _ in range(m):
        a, b, c = LI_()
        c += 1
        if c > l:
            continue
        dist[a][b] = c
        dist[b][a] = c

    supply = [[n] * n for i in range(n)]
    for k in range(n):
        distk = dist[k]
        for i in range(n):
            if i == k:
                continue
            disti = dist[i]
            for j in range(i + 1, n):
                if disti[k] + distk[j] < disti[j]:
                    disti[j] = disti[k] + distk[j]
                if distk[i] + dist[j][k] < dist[j][i]:
                    dist[j][i] = distk[i] + dist[j][k]

    lis = [[] for i in range(n)]
    for i in range(n):
        for j in range(i + 1, n):
            if dist[i][j] <= l:
                supply[i][j] = 0
                supply[j][i] = 0
                lis[i].append(j)
                lis[j].append(i)

    for i in range(n):
        q = []
        for k in lis[i]:
            heappush(q, (0, k))

        while q:
            time, p = heappop(q)
            for k in lis[p]:
                if dist[p][k] <= l and supply[i][k] > time:
                    supply[i][k] = time + 1
                    heappush(q, (time + 1, k))

    q = II()
    for _ in range(q):
        s, t = LI_()
        if dist[s][t] == inf:
            print(-1)
            continue
        else:
            print(supply[s][t])
    return


#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == '__main__':
    E()