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:
\#!/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: Runtime Error

Solution code:
    from heapq import heapify, heappop, heappush, nlargest, nsmallest
     
     
    N, M, L = map(int, input().split())
     
    G = [list(map(int, input().split())) for _ in range(M)]
    Q = int(input())
    Query = [list(map(int, input().split())) for _ in range(Q)]
     
    nei_graph = [[float('inf')] * N for _ in range(N)]
    for a, b, c in G:
        if c <= L:
            nei_graph[a - 1][b - 1] = c
            nei_graph[b - 1][a - 1] = c
     
    for a, b, c in G:
        nei_graph[a - 1][a - 1] = 0
     
     
    def dijkstra(start_node, end_node, nei_graph):
        visited = set()
     
        nodes = []
        heapify(nodes)
        heappush(nodes, [start_node, 0, L, 0])
     
        dist = [float('inf')] * N
        dist[start_node] = 0
     
        while nodes:
            node, d, remain, cnt = heappop(nodes)
            if node in visited:
                continue
     
            if node == end_node:
                return cnt
     
            visited.add(node)
     
            for i, edge in enumerate(nei_graph[node]):
                if edge == float('inf') or d + edge > dist[i]:
                    continue
     
                dist[i] = d + edge
     
                if remain < edge:
                    new_remain = L - edge
                    new_cnt = cnt + 1
                else:
                    new_remain = remain - edge
                    new_cnt = cnt
     
                heappush(nodes, [i, dist[i], new_remain, new_cnt])
     
        if end_node not in visited:
            return -1
     
     
    for start, end in Query:
        print(dijkstra(start - 1, end - 1, nei_graph))

Submission status: Runtime Error

Solution code:
from enum import Enum
from queue import Queue

import numpy as np

import collections
import bisect
import sys
import math

BIG_NUM = 200000000000
MOD = 1000000007
EPS = 0.000000001

def warshall_floyd(d,n):
    #d[i][j]:iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

N,M,L = map(int,input().split())
d = [[BIG_NUM for i in range(N)] for j 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
for i in range(N):
    d[i][i] = 0

d = warshall_floyd(d,N)
for i in range(N):
    for j in range(i,N):
        if d[i][j] < L:
            d[i][j] = 1
            d[j][i] = 1
        else:
            d[i][j] = 0
            d[j][i] = 0
    d[i][i] = 1

d = warshall_floyd(d,N)
Q = int(input())
for q in range(Q):
    s,t = map(int,input().split())
    if d[s][t] <= BIG_NUM:
        print(-1)
    else:
        print(int(d[s][t]-1))

Submission status: Runtime Error

Solution code:
class Graph(object):
  def __init__(self, N):
    self.N = N
    self.adj = None
    self.init_adj()
  
  def init_adj(self):
    self.adj = [[float("INF") for _ in range(self.N)] for _  in range(self.N)]
    for i in range(self.N):
      self.adj[i][i] = 0

  def add_edge(self, u, v, w):
    self.adj[u-1][v-1] = w
    self.adj[v-1][u-1] = w

  def print_adj(self):
    for i in range(self.N):
      print(self.adj[i])

  def floyd_warshall(self):
    for k in range(self.N):
      for i in range(self.N):
        for j in range(self.N):
          self.adj[i][j] = min(self.adj[i][j], self.adj[i][k] + self.adj[k][j])




if __name__ == "__main__":
  N, M, L = map(int, input().split())
  queries = []
  graph = Graph(N)
  for i in range(M):
    u, v, w = list(map(int, input().split()))
    graph.add_edge(u, v, w)
  Q = int(input())
  for i in range(Q):
    s, t = list(map(int, input().split()))
    queries.append([s, t])
  
  # print("queries:", queries)
  # print("-----")
  graph.floyd_warshall()
  # print("adj:")
  # graph.print_adj()
  adj = np.asarray(graph.adj)
  fuel_once = np.where(adj <= L, 1, float("INF"))
  # print("----")
  # print(fuel_once)
  # print("----")
  adj = fuel_once-np.eye(N)
  graph.adj = adj.tolist()
  graph.floyd_warshall()
  

  for s, t in queries:
    min_dist = graph.adj[s-1][t-1]
    # print(f"from: {s} to: {t}, min dist = {min_dist}")
    if min_dist == float("INF"):
      print(-1)
    else:
      print((int(min_dist))-1)

Submission status: Runtime Error

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

n, m, l = map(int, input().split())
abc = []
for _ in range(m):
    abc.append(map(int, input().split()))
q = int(input())
st = []
for _ in range(q):
    st.append(map(int, input().split()))

adjacency_matrix = np.zeros((n, n))
for a, b, c in abc:
    adjacency_matrix[a-1, b-1] = c
    adjacency_matrix[b-1, a-1] = c

shotest = dijkstra(adjacency_matrix)
fuel_once = np.where(shotest <= l, 1, 0)
fuel_times = dijkstra(fuel_once)

for s, t in st:
    ans = fuel_times[s-1][t-1]
    if np.isinf(ans):
        print(-1)
    else:
        print(int(ans) - 1)

Submission status: Runtime Error

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

n, m, l = map(int, input().split())
abc = []
for _ in range(m):
    abc.append(map(int, input().split()))
q = int(input())
st = []
for _ in range(q):
    s, t = map(int, input().split())
    s -= 1
    t -= 1
    st.append((s,t))

adjacency_matrix = np.zeros((n, n))
for (a, b, c) in abc:
    adjacency_matrix[a-1][b-1] = c
    adjacency_matrix[b-1][a-1] = c

shotest = dijkstra(adjacency_matrix)
fuel_once = np.where(shotest <= l, 1, 0)
fuel_times = dijkstra(fuel_once).astype(int)

for tap in st:
    s, t = tap
    if shotest[s][t] < np.inf:
        print(fuel_times[s][t] - 1)
    else:
        print(-1)

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra

n, m, l = map(int, input().split())
abc = []
for _ in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    abc.append([a, b, c])
    abc.append([b, a, c])
q = int(input())
st = []
for _ in range(q):
    s, t = map(int, input().split())
    s -= 1
    t -= 1
    st.append((s,t))


if m == 0:
    print(-1)
    sys.exit()

a, b, c = np.array(abc).T
adjacency_matrix = csr_matrix((c, (a,b)), (n, n))

shotest = dijkstra(adjacency_matrix)
fuel_once = np.where(shotest <= l, 1, 0)
fuel_times = dijkstra(fuel_once).astype(int)

for tap in st:
    s, t = tap
    if shotest[s][t] < np.inf:
        print(fuel_times[s][t] - 1)
    else:
        print(-1)

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra

n, m, l = map(int, input().split())
abc = []
for mi in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    abc.append([a, b, c])
    abc.append([b, a, c])
q = int(input())
st = []
for i in range(q):
    s, t = map(int, input().split())
    s -= 1
    t -= 1
    st.append((s,t))


if m == 0:
    print(-1)
    sys.exit()

a, b, c = np.array(abc).T
adjacency_matrix = csr_matrix((c, (a,b)), (n, n))

shotest = dijkstra(adjacency_matrix)
fuel_once = np.where(shotest <= l, 1, 0)
once_dijkstra = dijkstra(fuel_once)
fuel_times = np.where(once_dijkstra > 0, once_dijkstra - 1, once_dijkstra).astype(int)

for tap in st:
    s, t = tap
    print(fuel_times[s][t])

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra


def get_path(graph, s, t):
    if s == t:
        return [], [], 0
    else:
        path_cost, town = dijkstra(adjacency_matrix, return_predecessors=True, indices=s)
        path, costs, pre_cost = get_path(graph, s, town[t])
        path.append(town[t])
        costs.append(path_cost[t] - pre_cost)
        return path, costs, path_cost[t]


n, m, l = map(int, input().split())
abc = []
for mi in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    abc.append([a, b, c])
    abc.append([b, a, c])
q = int(input())
st = []
for i in range(q):
    s, t = map(int, input().split())
    st.append([s,t])


if m == 0:
    print(-1)
    sys.exit()

a, b, c = np.array(abc).T
adjacency_matrix = csr_matrix((c, (a,b)), (n, n))

for element in st:
    start, end = element[0]-1, element[1]-1
    _, costs, _ = get_path(adjacency_matrix, start, end)

    count = 0
    tmp_fuel = l
    for cost in costs:
        if tmp_fuel < cost:
            tmp_fuel = l
            count += 1
        tmp_fuel -= cost
    print(count)

Submission status: Runtime Error

Solution code:
from math import inf
n,m,l=map(int,input().split())
adj=[[inf for i in range(n+1)] for j in range(n+1)]

for i in range(1,n+1):
    adj[i][i]=0
            
for w in range(m):
    a,b,c=map(int,input().split())
    adj[a][b]=adj[b][a]=c

for k in range(1,n+1):
    for i in range(1,n+1):
        for j in range(1,n+1):
            adj[i][j]=min(adj[i][j],adj[i][k]+adj[k][j])
            
for i in range(1,n+1):
    for j in range(1,n+1):
        if adj[i][j]<=l:
            adj[i][j]=1
        else:
            adj[i][j]=inf
        if i==j:
            adj[i][j]=0

for k in range(1,n+1):
    for i in range(1,n+1):
        for j in range(1,n+1):
            adj[i][j]=min(adj[i][j],adj[i][k]+adj[k][j])
            
q=int(input())
for w in range(q):
    a,b=map(int,input().split())
    if adj[a][b]==inf:
        print(-1)
    else:
        print(adj[a][b]-1)

Submission status: Runtime Error

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

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

from scipy.sparse.csgraph import floyd_warshall

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

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

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

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

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

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

# M = floyd_warshall(M)

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

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

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

# M = floyd_warshall(M)

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

Submission status: Runtime Error

Solution code:
input_iter = iter(input_str.split("\n"))
def input() : return next(input_iter)
n,m,l=map(int,input().split())
abc=[list(map(int,input().split())) for _ in [0]*m]
q=int(input())
st=[list(map(int,input().split())) for _ in [0]*q]
inf=10**12
dist=[[inf]*n for _ in [0]*n]
for i in range(n):
    dist[i][i]=0
for a,b,c in abc:
    dist[a-1][b-1]=c
    dist[b-1][a-1]=c
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])
inf=10**3
dist2=[[inf]*n for _ in [0]*n]
for i in range(n):
    for j in range(n):
        if dist[i][j]<=l:
            dist2[i][j]=1
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])
for i in range(n):
    for j in range(n):
        if dist2[i][j]==inf:
            dist2[i][j]=-1
        else:
            dist2[i][j]-=1
for s,t in st:
    print(dist2[s-1][t-1])

Submission status: Runtime Error

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

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

def warshall_floyd(d,n):
    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])

inf = (l+1)*n
d = [[inf]*n for _ in range(n)]
for i in range(n):
    d[i][i] = 0
for a,b,c in town:
    a -= 1
    b -= 1
    d[a][b] = c
    d[b][a] = c
    
warshall_floyd(n,d)

d2 = [None]*n
for i,row in enumerate(d):
    d2[i] = [1 if val<=l else inf for val in row]
    d2[i][i] = 0

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

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Thu Oct 24 23:58:46 2019

@author: Tomomasa Takahashi
"""

class Digraph():
    """
    Directed weighted graph.
    
    edges is a dictionary mapping each node to a edges starting from it
        key: node; value: dictionary of edges starting from that node
            value dictionary: key: end node of edge, value: weight (cost) of the edge
    """
    def __init__(self, adj_list=None):
        """
        Initialize either empty graph or one from a dictionary adjacency list
        """
        self.edges = {}
        self.num_edges = 0
        if isinstance(adj_list, dict):
            for src, values in adj_list.items():
                for dest, weight in values.items():
                    self.add_edge(src, dest, weight)
    
    def add_node(self,node):
        # Adds a vertex to graph (based on key value)       
        self.edges[node] = dict()

    def add_edge(self,src,dest,weight):
        # Adds the (v,w) edge, making sure the two nodes exist
        if not self.has_node(src): 
            self.add_node(src)
        if not self.has_node(dest): 
            self.add_node(dest)
        if not self.has_edge(src, dest):
            self.num_edges += 1
            self.edges[src][dest] = weight
  
    def children_of(self, v):
        # Returns a node's children
        return self.edges[v].items()
    
    def get_nodes(self):
        # Returns a node's children
        return self.edges.keys()
        
    def has_node(self, v):
        # Checks if node exists
        return v in self.edges
        
    def has_edge(self, v, w):
        # Checks if edge exists
        return w in self.edges[v]

    def list_edges(self):
        # Creates list of edges
        ll = []
        for src,values in self.edges.items():
            for dest,weight in values.items():
                ll.append([src,dest,weight])
        return ll
    
    def __str__(self):
        # Returns a string representation of the graph
        result = ''
        for src in self.edges:
            for dest,weight in self.edges[src].items():
                result = result + src + '->'\
                         + dest + ', length ' + str(weight) + '\n'
        return result[:-1] # omit final newline
    
    def connected(self, start):
        visited = set()
        to_visit=[start]
        while len(to_visit)>0:
            current = to_visit.pop(0)
            visited.add(current)
            for node, weight in self.children_of(current):
                if not node in visited:
                    to_visit.append(node)
        return visited

    def warshall_floyd(self):
        nodes = self.get_nodes()
        dist={}
        #initialize
        for src in nodes:
            dist_src={}
            for dest in nodes:
                if self.has_edge(src, dest):
                    dist_src[dest] = self.edges[src][dest]
                elif src != dest:
                    dist_src[dest] = float('inf')
                else:
                    dist_src[dest] = 0
            dist[src]=dist_src
        #construct
        for via in nodes:
            for src in nodes:
                for dest in nodes:
                    dist[src][dest] = min(dist[src][dest], dist[src][via]+dist[via][dest])
        return dist
    
    def dijkstra(self, start):
        # Visited nodes X initially empty  
        X = set()
        X.add(start)
        # Previous nodes
        prev_nodes = {start:None}
        # Shortest distances to all nodes from s
        A = dict() 
        for node in self.get_nodes(): 
            A[node] = float('Inf') # initialize to "infinity"           
        A[start] = 0 # distance zero to itself
        # Main loop
        connected_nodes = self.connected(start)
        # Loop while we haven't visited all nodes
        while len(X) < len(connected_nodes):              
            # Store mininimum edge and distance when looping
            min_edge = [] # list [src, dest, weight]
            min_dist = float('inf')
            # Loop through all edges starting in X and not ending in X
            # Find minimum Dijksta score
            for src in X:
                for dest, weight in self.children_of(src): # edges starting from src
                    if dest not in X: # edge not ending in X
                        # Update minimum-Dijkstra-score edge if find one
                        if A[src] + weight < min_dist: 
                            min_edge = [src, dest, weight] 
                            min_dist = A[src] + weight
                            prev_nodes[dest] = src
            # Update A[min_e_dest] = A[min_e_source] + A[min_e_weight]        
            A[min_edge[1]] = A[min_edge[0]] + min_edge[2]
            # Add destination node from min edge to visited nodes
            X.add(min_edge[1])  
        return A, prev_nodes

class Graph(Digraph):
    """ 
    Undirected graph: two one-way edges for every edge
    """
    def add_edge(self, src, dest,weight):
        Digraph.add_edge(self, src, dest, weight)
        Digraph.add_edge(self, dest, src, weight)
        
N,M,L = map(int, input().split())
graph_1 = Graph()
for i in range(N):
    graph_1.add_node(i+1)
for i in range(M):
    src,dest,weight = map(int, input().split())
    graph_1.add_edge(src,dest,weight)
    
graph_2 = Graph()

dist = graph_1.warshall_floyd()

for src in range(1,N+1):
    for dest in range(1,N+1):
        if dest != src and dist[src][dest]<=L:
            graph_2.add_edge(src, dest, 1)
            
dist2 = graph_2.warshall_floyd()
            
Q=int(input())
for i in range(Q):
    src, dest = map(int, input().split())
    ans = dist2[src][dest]
    if ans == float('inf'):
        print(-1)
    else:
        print(ans-1)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Thu Oct 24 23:58:46 2019

@author: Tomomasa Takahashi
"""

class Digraph():
    """
    Directed weighted graph.
    
    edges is a dictionary mapping each node to a edges starting from it
        key: node; value: dictionary of edges starting from that node
            value dictionary: key: end node of edge, value: weight (cost) of the edge
    """
    def __init__(self, adj_list=None):
        """
        Initialize either empty graph or one from a dictionary adjacency list
        """
        self.edges = {}
        self.num_edges = 0
        if isinstance(adj_list, dict):
            for src, values in adj_list.items():
                for dest, weight in values.items():
                    self.add_edge(src, dest, weight)
    
    def add_node(self,node):
        # Adds a vertex to graph (based on key value)       
        self.edges[node] = dict()

    def add_edge(self,src,dest,weight):
        # Adds the (v,w) edge, making sure the two nodes exist
        if not self.has_node(src): 
            self.add_node(src)
        if not self.has_node(dest): 
            self.add_node(dest)
        if not self.has_edge(src, dest):
            self.num_edges += 1
            self.edges[src][dest] = weight
  
    def children_of(self, v):
        # Returns a node's children
        return self.edges[v].items()
    
    def get_nodes(self):
        # Returns a node's children
        return self.edges.keys()
        
    def has_node(self, v):
        # Checks if node exists
        return v in self.edges
        
    def has_edge(self, v, w):
        # Checks if edge exists
        return w in self.edges[v]

    def list_edges(self):
        # Creates list of edges
        ll = []
        for src,values in self.edges.items():
            for dest,weight in values.items():
                ll.append([src,dest,weight])
        return ll
    
    def __str__(self):
        # Returns a string representation of the graph
        result = ''
        for src in self.edges:
            for dest,weight in self.edges[src].items():
                result = result + src + '->'\
                         + dest + ', length ' + str(weight) + '\n'
        return result[:-1] # omit final newline
    
    def connected(self, start):
        visited = set()
        to_visit=[start]
        while len(to_visit)>0:
            current = to_visit.pop(0)
            visited.add(current)
            for node, weight in self.children_of(current):
                if not node in visited:
                    to_visit.append(node)
        return visited

    def warshall_floyd(self):
        nodes = self.get_nodes()
        dist={}
        #initialize
        for src in nodes:
            dist_src={}
            for dest in nodes:
                if self.has_edge(src, dest):
                    dist_src[dest] = self.edges[src][dest]
                elif src != dest:
                    dist_src[dest] = float('inf')
                else:
                    dist_src[dest] = 0
            dist[src]=dist_src
        #construct
        for via in nodes:
            for src in nodes:
                for dest in nodes:
                    dist[src][dest] = min(dist[src][dest], dist[src][via]+dist[via][dest])
        return dist
    
    def dijkstra(self, start):
        # Visited nodes X initially empty  
        X = set()
        X.add(start)
        # Previous nodes
        prev_nodes = {start:None}
        # Shortest distances to all nodes from s
        A = dict() 
        for node in self.get_nodes(): 
            A[node] = float('Inf') # initialize to "infinity"           
        A[start] = 0 # distance zero to itself
        # Main loop
        connected_nodes = self.connected(start)
        # Loop while we haven't visited all nodes
        while len(X) < len(connected_nodes):              
            # Store mininimum edge and distance when looping
            min_edge = [] # list [src, dest, weight]
            min_dist = float('inf')
            # Loop through all edges starting in X and not ending in X
            # Find minimum Dijksta score
            for src in X:
                for dest, weight in self.children_of(src): # edges starting from src
                    if dest not in X: # edge not ending in X
                        # Update minimum-Dijkstra-score edge if find one
                        if A[src] + weight < min_dist: 
                            min_edge = [src, dest, weight] 
                            min_dist = A[src] + weight
                            prev_nodes[dest] = src
            # Update A[min_e_dest] = A[min_e_source] + A[min_e_weight]        
            A[min_edge[1]] = A[min_edge[0]] + min_edge[2]
            # Add destination node from min edge to visited nodes
            X.add(min_edge[1])  
        return A, prev_nodes

class Graph(Digraph):
    """ 
    Undirected graph: two one-way edges for every edge
    """
    def add_edge(self, src, dest,weight):
        Digraph.add_edge(self, src, dest, weight)
        Digraph.add_edge(self, dest, src, weight)
        
N,M,L = map(int, input().split())
graph_1 = Graph()
for i in range(N):
    graph_1.add_node(i+1)
for i in range(M):
    src,dest,weight = map(int, input().split())
    graph_1.add_edge(src,dest,weight)
    
graph_2 = Graph()

dist = graph_1.warshall_floyd()

for src in range(1,N+1):
    connected = graph_1.connected(src)
    for dest in connected:
        if dest != src and dist[src][dest]<=L:
            graph_2.add_edge(src, dest, 1)
            
Q=int(input())
for i in range(Q):
    src, dest = map(int, input().split())
    connected_nodes = graph_1.connected(src)
    if dest in connected_nodes:
        short_dict, prev_nodes = graph_2.dijkstra(src)
        print(short_dict[dest]-1)
    else:
        print(-1)