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: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, m, l = map(int, input().split())
    cost = [[f_inf] * n for _ in range(n)]
    for i in range(n):
        cost[i][i] = 0
    for _ in range(m):
        a, b, c = map(int, input().split())
        cost[a - 1][b - 1] = c
        cost[b - 1][a - 1] = c

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

    res = [[f_inf] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if cost[i][j] <= l:
                res[i][j] = 1

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

    q = int(input())
    for _ in range(q):
        s, t = map(int, input().split())
        print(-1 if cost[s - 1][t - 1] == f_inf else res[s - 1][t - 1] - 1)


if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, m, l = map(int, input().split())
    cost = [[f_inf] * n for _ in range(n)]
    for i in range(n):
        cost[i][i] = 0
    for _ in range(m):
        a, b, c = map(int, input().split())
        cost[a - 1][b - 1] = c
        cost[b - 1][a - 1] = c

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

    res = [[f_inf] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if i == j:
                res[i][j] = 0
            elif cost[i][j] <= l:
                res[i][j] = 1

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

    q = int(input())
    for _ in range(q):
        s, t = map(int, input().split())
        print(-1 if cost[s - 1][t - 1] == f_inf else res[s - 1][t - 1] - 1)


if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, m, l = map(int, input().split())
    cost = [[f_inf] * n for _ in range(n)]
    for i in range(n):
        cost[i][i] = 0
    for _ in range(m):
        a, b, c = map(int, input().split())
        cost[a - 1][b - 1] = c
        cost[b - 1][a - 1] = c

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

    for i in range(n):
        for j in range(i + 1, n):
            if cost[i][j] <= l:
                cost[i][j] = 1
                cost[j][i] = 1

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

    q = int(input())
    for _ in range(q):
        s, t = map(int, input().split())
        print(-1 if cost[s - 1][t - 1] == f_inf else cost[s - 1][t - 1] - 1)


if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

Solution code:
import sys
from heapq import heappush, heappop

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    def dijkstra_heap(v, start, edge):
        dist = [f_inf] * v
        dist[start] = 0
        edge_list = []
        for d, v in edge[start]:
            heappush(edge_list, [d, v, start])
        while edge_list:
            cost, node, prev_node = heappop(edge_list)
            if dist[node] == f_inf:
                if cost > l:
                    dp[start][node] = min(dp[start][node], dp[start][prev_node] + 1)
                    cost = cost - dist[prev_node]
                else:
                    dp[start][node] = min(dp[start][node], dp[start][prev_node])
                dist[node] = cost
                for next_cost, next_node in edge[node]:
                    if dist[next_node] == f_inf:
                        heappush(edge_list, [next_cost + cost, next_node, node])
        return dist

    n, m, l = map(int, input().split())
    edge = [[] for _ in range(n)]
    for _ in range(m):
        a, b, c = map(int, input().split())
        if c > l:
            continue
        edge[a - 1].append([c, b - 1])
        edge[b - 1].append([c, a - 1])

    dp = [[f_inf] * n for _ in range(n)]
    for i in range(n):
        dp[i][i] = 0
        dijkstra_heap(n, i, edge)

    q = int(input())
    for _ in range(q):
        s, t = map(int, input().split())
        print(-1 if dp[s - 1][t - 1] == f_inf else dp[s - 1][t - 1])


if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

Solution code:
from heapq import heapify, heappop, heappush
from collections import deque
import sys
input = sys.stdin.readline
N,M,L = map(int,input().split()); INF = float("inf")
G = [[] for _ in range(N)]
#P = [[] for _ in range(N)]
for i in range(M):
  a,b,c = map(int,input().split())
  a-=1;b-=1 #0index
  if c > L: #この道は通れない
    continue
  G[a].append((c,b));G[b].append((c,a))
base = 350
#print(G)
R = [] #L以下でいける道のリスト
for i in range(N):
  reach = [INF for _ in range(N)]
  reach[i] = 0
  Q = []
  heappush(Q,i) #始点iからのコスト*300+今いる点
  possible = []
  while Q:
    temp = heappop(Q)
    cost = temp//base
    v = temp%base
    if cost + reach[i] > L: #燃料Lを超えるならスキップ
      continue
    for x in G[v]:
      fuel, u = x
      if reach[u] != INF: #すでに到達済みならスキップ
        continue
      if cost + fuel > L: #燃料Lを超えるならスキップ
        continue
      reach[u] = cost + fuel
      pseudo = (cost+fuel)*base+u
      possible.append(u)
      heappush(Q,pseudo)
  R.append(possible)
#print(R)
Query = int(input())
for i in range(Query):
  start,goal = map(int,input().split())
  start-=1;goal-=1
  visit = [INF for _ in range(N)]
  visit[start] = -1 #最初は満タンで一回移動で0なので-1スタート
  HQ = deque([]); HQ.append(start)
  Flag = False
  while HQ and not Flag:
    now = HQ.popleft()
    for nxt in R[now]:
      if visit[nxt] == INF:
        visit[nxt] = visit[now]+1
        if nxt == goal:
          ans = visit[nxt];Flag = True
          break
        HQ.append(nxt)
  if visit[goal] == INF:
    ans = -1
  print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heapify, heappop, heappush
from collections import deque
import sys
input = sys.stdin.readline
N,M,L = map(int,input().split()); INF = float("inf")
G = [[] for _ in range(N)]
#P = [[] for _ in range(N)]
for i in range(M):
  a,b,c = map(int,input().split())
  a-=1;b-=1 #0index
  if c > L: #この道は通れない
    continue
  G[a].append((c,b));G[b].append((c,a))
base = 300
#print(G)
R = [] #L以下でいける道のリスト
for i in range(N):
  reach = [INF for _ in range(N)]
  reach[i] = 0
  Q = []
  heappush(Q,i) #始点iからのコスト*300+今いる点
  possible = []
  while Q:
    temp = heappop(Q)
    cost = temp//base
    v = temp%base
    if cost + reach[i] > L: #燃料Lを超えるならスキップ
      continue
    for x in G[v]:
      fuel, u = x
      if reach[u] != INF: #すでに到達済みならスキップ
        continue
      if cost + fuel > L: #燃料Lを超えるならスキップ
        continue
      reach[u] = cost + fuel
      pseudo = (cost+fuel)*base+u
      possible.append(u)
      heappush(Q,pseudo)
  R.append(possible)
#print(R)
Query = int(input())
for i in range(Query):
  start,goal = map(int,input().split())
  start-=1;goal-=1
  visit = [INF for _ in range(N)]
  visit[start] = -1 #最初は満タンで一回移動で0なので-1スタート
  HQ = deque([]); HQ.append(start)
  Flag = False
  while HQ and not Flag:
    now = HQ.popleft()
    for nxt in R[now]:
      if visit[nxt] == INF:
        visit[nxt] = visit[now]+1
        if nxt == goal:
          ans = visit[nxt];Flag = True
          break
        HQ.append(nxt)
  if visit[goal] == INF:
    ans = -1
  print(ans)

Submission status: Wrong Answer

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

n, m, l = map(int, input().split())

graph = defaultdict(list)

for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))
    graph[b].append((a, c))


def dfs(u):
    dist = [-1] * (n + 1)
    stack = [u]
    dist[u] = 0
    while stack:
        u = stack.pop()
        for v, d in graph[u]:
            nxt = dist[u] + d
            if dist[v] == -1 or dist[v] > nxt:
                dist[v] = nxt
                stack.append(v)
    return dist


dist = [[0] * n for _ in range(n)]
for i in range(1, n + 1):
    dist[i - 1] = dfs(i)[1:]

dist = np.array(dist)

graph2 = np.full((n, n), np.inf)
graph2[dist <= l] = 1
dist2 = floyd_warshall(graph2, directed=False)
dist2 = dist2.astype(int)

q = int(input())

ans = []
for _ in range(q):
    s, t = map(int, input().split())
    if dist[s - 1, t - 1] == -1:
        ans.append(-1)
    else:
        ans.append(dist2[s - 1, t - 1] - 1)

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

Submission status: Wrong Answer

Solution code:
from heapq import heapify, heappop, heappush
from collections import deque
import sys
input = sys.stdin.readline
N,M,L = map(int,input().split()); INF = float("inf")
G = [[] for _ in range(N)]
#P = [[] for _ in range(N)]
for i in range(M):
  a,b,c = map(int,input().split())
  a-=1;b-=1 #0index
  if c > L: #この道は通れない
    continue
  G[a].append((c,b));G[b].append((c,a))
  
#print(G)
R = [] #L以下でいける道のリスト
for i in range(N):
  reach = [INF for _ in range(N)]
  reach[i] = 0
  Q = []
  heappush(Q,i) #始点iからのコスト*300+今いる点
  possible = []
  while Q:
    temp = heappop(Q)
    cost = temp//300
    v = temp%300
    if cost + reach[i] > L: #燃料Lを超えるならスキップ
      continue
    for x in G[v]:
      fuel, u = x
      pseudo = fuel*300+u
      if reach[u] != INF: #すでに到達済みならスキップ
        continue
      if cost + fuel > L: #燃料Lを超えるならスキップ
        continue
      reach[u] = cost + fuel
      possible.append(u)
      heappush(Q,pseudo)
  R.append(possible)
#print(R)
Query = int(input())
for i in range(Query):
  start,goal = map(int,input().split())
  start-=1;goal-=1
  visit = [INF for _ in range(N)]
  visit[start] = -1 #最初は満タンで一回移動で0なので-1スタート
  HQ = deque([]); HQ.append(start)
  Flag = False
  while HQ and not Flag:
    now = HQ.popleft()
    for nxt in R[now]:
      if visit[nxt] == INF:
        visit[nxt] = visit[now]+1
        if nxt == goal:
          ans = visit[nxt];Flag = True
          break
        HQ.append(nxt)
  if visit[goal] == INF:
    ans = -1
  print(ans)

Submission status: Wrong Answer

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

n, m, l = map(int, input().split())

graph = defaultdict(list)

for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))
    graph[b].append((a, c))


def dfs(u):
    dist = [-1] * (n + 1)
    stack = [u]
    dist[u] = 0
    while stack:
        u = stack.pop()
        for v, d in graph[u]:
            nxt = dist[u] + d
            if dist[v] == -1 or dist[v] > nxt:
                dist[v] = nxt
                stack.append(v)
    return dist


dist = [[0] * n for _ in range(n)]
for i in range(1, n + 1):
    dist[i - 1] = dfs(i)[1:]

dist = np.array(dist)

graph2 = np.full((n, n), np.inf)
graph2[dist <= l] = 1
dist = floyd_warshall(graph2, directed=False)
dist = dist.astype(int)

q = int(input())

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

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

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import sys
sys.setrecursionlimit(10**7)

n, m, l = map(int, input().split())

graph = defaultdict(list)

for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))
    graph[b].append((a, c))


def dfs(u, l, rest):
    dist = [-1] * (n + 1)
    stack = [u]
    dist[u] = 0
    while stack:
        u = stack.pop()
        tmp_rest = rest
        for v, d in graph[u]:
            rest = tmp_rest
            rest -= d
            if rest < 0:
                nxt = dist[u] + 1
                rest = l
            else:
                nxt = dist[u]
            if dist[v] == -1 or dist[v] > nxt:
                dist[v] = nxt
                stack.append(v)
    return dist


q = int(input())

ans = []
for _ in range(q):
    s, t = map(int, input().split())
    ans.append(dfs(s, l, l)[t])

print(ans, sep="\n")

Submission status: Wrong Answer

Solution code:
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


def main():
    INF = 10**18
    n,m,l = map(int, input().split())
    d = [ [INF]*(n+1) for _ in range(n+1) ]
    for _ in range(m):
        a,b,c = map(int, input().split())
        d[a][b] = c
        d[b][a] = c

    d = warshall_floyd(d,n+1)
    new_d = [ [INF]*(n+1) for _ in range(n+1) ]
    for a in range(n+1):
        for b in range(n+1):
            if d[a][b] <= l:
                new_d[a][b] = 1
                new_d[b][a] = 1


    new_d = warshall_floyd(new_d,n+1)
    ansl = []
    q = int(input())
    for _ in range(q):
        s,t = map(int, input().split())
        ans = new_d[s][t]
        if ans >= INF: ans = -1
        ansl.append(ans-1)

    for a in ansl: print(a)



if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

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


  
N,M,L = IL()

class WarshallFloyd():
  def __init__(self, N):
    self.N = N
    self.d = [[float("inf") for i in range(N)] for i in range(N)]

  def add(self, u, v, c, directed=False):
    if directed is False:
      self.d[u][v] = c
      self.d[v][u] = c
    else:
      self.d[u][v] = c

  def WarshallFloyd_search(self):
    for k in range(self.N):
      for i in range(self.N):
        for j in range(self.N):
          if L-(self.d[i][k]%L) >= self.d[k][j]:
            self.d[i][j] = min(self.d[i][j], (-(-self.d[i][k]//L)*L + self.d[k][j]))
          else:
            self.d[i][j] = min(self.d[i][j], self.d[i][k] + self.d[k][j])
    hasNegativeCycle = False
    for i in range(self.N):
      if self.d[i][i] < 0:
        hasNegativeCycle = True
        break
    for i in range(self.N):
      self.d[i][i] = 0
    return hasNegativeCycle, self.d
  
W = WarshallFloyd(N)
for _ in range(M):
  u,v,c = IL()
  if c>L: continue
  W.add(u-1,v-1,c)

_,d = W.WarshallFloyd_search() 

#print(d)
Q = I()
for _ in range(Q):
  s,t = IL()
  if d[s-1][t-1] == INF:
    print(-1)
  else:
    print((d[s-1][t-1]-1)//L)

Submission status: Wrong Answer

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

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


  
N,M,L = IL()

class WarshallFloyd():
  def __init__(self, N):
    self.N = N
    self.d = [[float("inf") for i in range(N)] for i in range(N)]

  def add(self, u, v, c, directed=False):
    if directed is False:
      self.d[u][v] = c
      self.d[v][u] = c
    else:
      self.d[u][v] = c

  def WarshallFloyd_search(self):
    for k in range(self.N):
      for i in range(self.N):
        for j in range(self.N):
          self.d[i][j] = min(self.d[i][j], self.d[i][k] + self.d[k][j])
    hasNegativeCycle = False
    for i in range(self.N):
      if self.d[i][i] < 0:
        hasNegativeCycle = True
        break
    for i in range(self.N):
      self.d[i][i] = 0
    return hasNegativeCycle, self.d
  
W = WarshallFloyd(N)
for _ in range(M):
  u,v,c = IL()
  if c>L: continue
  W.add(u-1,v-1,c)

_,d = W.WarshallFloyd_search() 
"""
  if L-(d[u]%L) >= c:
          heapq.heappush(q, (c + d[u], v))
        else:
          heapq.heappush(q, (-(-d[u]//L)*L + c, v))
  return d

dd = []
for i in range(N):
  d = dijkstra(graph,i)
  dd.append(d)
"""
Q = I()
for _ in range(Q):
  s,t = IL()
  if d[s-1][t-1] == INF:
    print(-1)
  else:
    print((d[s-1][t-1]-1)//L)

Submission status: Wrong Answer

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

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


  
N,M,L = IL()
graph = [[] for i in range(N)]
for _ in range(M):
  u,v,c = IL()
  if c>L: continue
  graph[u-1].append((c,v-1))
  graph[v-1].append((c,u-1))

def dijkstra(graph, start):
  N = len(graph)
  d = [10**9*N] * N
  d[start] = 0
  f = [False] * N
  q = [(0, start)]
  while q:
    c,u = heapq.heappop(q)
    if f[u]: continue
    d[u] = c
    f[u] = True
    for c,v in graph[u]:
      if not f[v]:
        if L-(d[u]%L) >= c:
          heapq.heappush(q, (c + d[u], v))
        else:
          heapq.heappush(q, (-(-d[u]//L)*L + c, v))
  return d

dd = []
for i in range(N):
  d = dijkstra(graph,i)
  dd.append(d)

Q = I()
for _ in range(Q):
  s,t = IL()
  if dd[s-1][t-1] == INF:
    print(-1)
  else:
    print((dd[s-1][t-1]-1)//L)

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    INF = 10**18
    MX = 10**9
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N,M,L = LI()
    road = [[] for _ in range(N)]
    for _ in range(M):
        a,b,c = LI()
        if c <= L:
            road[a-1].append((b-1,c))
            road[b-1].append((a-1,c))

    town = [[-1 for _ in range(N)] for _ in range(N)]

    for s in range(N):

        q = [(0,s)]
        town[s][s] = 0
        heapq.heapify(q)
        while q:
            z,u = heapq.heappop(q)
            if town[s][u] < z: continue
            n = z // MX
            w = z % MX
            for v,c in road[u]:
                nn = n
                nw = w + c
                if nw > L:
                    nw = c
                    nn += 1

                nz = nn * MX + nw
                if town[s][v] < 0 or town[s][v] > nz:
                    town[s][v] = nz
                    heapq.heappush(q,(nz,v))

    Q = NI()
    for _ in range(Q):
        s,t = LI()
        if town[s-1][t-1] < 0:
            print(-1)
        else:
            print(town[s-1][t-1]//MX)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    INF = 10**18
    MX = 10**9
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N,M,L = LI()
    road = [[] for _ in range(N)]
    for _ in range(M):
        a,b,c = LI()
        if c <= L:
            road[a-1].append((b-1,c))
            road[b-1].append((a-1,c))

    town = [[-1 for _ in range(N)] for _ in range(N)]

    for s in range(N):

        q = [(0,s)]
        town[s][s] = 0
        heapq.heapify(q)
        while q:
            z,u = heapq.heappop(q)
            if town[s][u] < z: continue
            n = z // MX
            w = z % MX
            for v,c in road[u]:
                nn = n
                nw = w + c
                if nw > L:
                    nw = c
                    nn += 1

                nz = nn * MX + nw
                if town[s][v] < 0 or town[s][v] > nz:
                    town[s][v] = nz
                    heapq.heappush(q,(nz,v))

    Q = NI()
    for _ in range(Q):
        s,t = LI()
        if town[s-1][t-1] == INF:
            print(-1)
        else:
            print(town[s-1][t-1]//MX)


if __name__ == '__main__':
    main()