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:
# -*- 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 = [INF] * 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: Time Limit Exceeded

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

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

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

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

    for s in range(N):

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

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

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

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

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

    N,M,L = LI()
    road = [[0] * N for _ in range(N)]
    for _ in range(M):
        a,b,c = LI()
        if c <= L:
            road[a-1][b-1] = c
            road[b-1][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 in range(N):
                c = road[u][v]
                if c == 0: continue
                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: Time Limit Exceeded

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

def main():
    INF = 10**18
    MX = 10**10
    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: Time Limit Exceeded

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

def main():
    INF = float('inf')
    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,0] for _ in range(N)] for _ in range(N)]

    for s in range(N):

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

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

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

def main():
    INF = float('inf')
    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,0] for _ in range(N)] for _ in range(N)]

    for s in range(N):

        q = [(0,-L,s)]
        heapq.heapify(q)
        while q:
            n,w,u = heapq.heappop(q)
            for v,c in road[u]:
                nn = n
                nw = w + c
                if nw > 0:
                    nw = c - L
                    nn += 1

                if town[s][v][0] < 0 or town[s][v][0] > nn or \
                        town[s][v][0] == nn and town[s][v][1] > nw:
                    town[s][v][0] = nn
                    town[s][v][1] = nw
                    heapq.heappush(q,(nn,nw,v))

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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


def solve(N,L,edges,queries):

    graph = np.zeros((N,N),dtype=int)
    for a,b,c in edges:
        graph[a-1,b-1] = c
        graph[b-1,a-1] = c

    dist = bellman_ford(graph, directed=False)
    dist[dist<=L] = 1
    dist[dist>L] = 0

    dist = bellman_ford(dist, directed=False)
    res = []
    for a,b in queries:
        d = dist[a-1,b-1]
        res.append(int(d-1) if d != float('inf') else -1)
    return res

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

if __name__ == '__main__':

    t = read().split()

    N,M,L = map(int,t[:3])

    m = map(int,t[3:M*3+3])
    edges = zip(m,m,m)

    Q = int(t[M*3+3])
    m = map(int, t[M*3+4:])
    queries = zip(m,m)

    print(*solve(N,L,edges,queries), sep='\n')

Submission status: Time Limit Exceeded

Solution code:
class Graph:
    class Edge:
        def __init__(self, to, cost):
            """
            :param to:  終点ノード
            :param cost: 辺の重み
            """
            self.to, self.cost = to, cost

    def __init__(self, n, directed=False, decrement=True, edges=[]):
        self.n = n
        self.directed = directed
        self.decrement = decrement
        self.edges = [[] for _ in range(self.n)]
        self.edges2 = []                            # ワーシャルフロイド用
        self.parent = [-1]*self.n
        self.info = [-1]*self.n
        for x, y, cost in edges:
            self.add_edge(x, y, cost)

    def add_edge(self, x, y, cost):
        if self.decrement:
            x -= 1
            y -= 1
        self.edges[x].append(self.Edge(y, cost))
        self.edges2.append((x, y, cost))
        if self.directed == False:
            self.edges[y].append(self.Edge(x, cost))
            self.edges2.append((y, x, cost))     # ワーシャルフロイド用

    def warshall_folyd(self, INF=1<<30):
        """
        :param INF: INF = 10**18 にすると、負のコストがある場合に少し面倒になる
        :return: 頂点 i, j 間の距離を行列として返す
        """
        dist = [[INF] * self.n for _ in range(self.n)]

        for i, j, cost in self.edges2:
            dist[i][j] = cost
        for i in range(self.n):
            dist[i][i] = 0  # 自身のところに行くコストは０

        for k in range(self.n):
            for i in range(self.n):
                for j in range(self.n):
                    if dist[i][j] > dist[i][k] + dist[k][j]:
                        dist[i][j] = dist[i][k] + dist[k][j]
        return dist

    def warshall_folyd2(self, INF=1<<30):
        """
        :param INF: INF = 10**18 にすると、負のコストがある場合に少し面倒になる
        :return: 頂点 i, j 間の距離を行列として返す
        """
        dist = [[INF] * self.n for _ in range(self.n)]

        for i, j, cost in self.edges2:
            dist[i][j] = cost
            if dist[i][j] <= L:
                data.append((i, j))
        for i in range(self.n):
            dist[i][i] = 0

        for k in range(self.n):
            for i in range(self.n):
                for j in range(self.n):
                    if dist[i][j] > dist[i][k] + dist[k][j]:
                        dist[i][j] = dist[i][k] + dist[k][j]
                        if dist[i][j] <= L:
                            data.append((i, j))
        return dist

def max2(x,y):
    return x if x > y else y

N, M, L = map(int, input().split())
graph = Graph(N, directed=False, decrement=True)
for _ in range(M):
    x, y, cost = map(int, input().split())
    graph.add_edge(x, y, cost)

data = []
graph.warshall_folyd2()

graph2 = Graph(N, directed=False, decrement=False)
for x, y in data:
    graph2.add_edge(x, y, 1)

d = graph2.warshall_folyd()

for _ in range(int(input())):
    s, t, = map(int, input().split())
    s, t = s-1, t-1
    print(d[s][t]-1 if d[s][t] < 1<<20 else -1)

Submission status: Time Limit Exceeded

Solution code:
class Graph:
    class Edge:
        def __init__(self, to, cost):
            """
            :param to:  終点ノード
            :param cost: 辺の重み
            """
            self.to, self.cost = to, cost

    def __init__(self, n, directed=False, decrement=True, edges=[]):
        self.n = n
        self.directed = directed
        self.decrement = decrement
        self.edges = [[] for _ in range(self.n)]
        self.edges2 = []                            # ワーシャルフロイド用
        self.parent = [-1]*self.n
        self.info = [-1]*self.n
        for x, y, cost in edges:
            self.add_edge(x, y, cost)

    def add_edge(self, x, y, cost):
        if self.decrement:
            x -= 1
            y -= 1
        self.edges[x].append(self.Edge(y, cost))
        self.edges2.append((x, y, cost))
        if self.directed == False:
            self.edges[y].append(self.Edge(x, cost))
            self.edges2.append((y, x, cost))     # ワーシャルフロイド用

    def warshall_folyd(self, INF=float("inf")):
        """
        :param INF: INF = 10**18 にすると、負のコストがある場合に少し面倒になる
        :return: 頂点 i, j 間の距離を行列として返す
        """
        dist = [[INF] * self.n for _ in range(self.n)]

        for i, j, cost in self.edges2:
            dist[i][j] = cost
        for i in range(self.n):
            dist[i][i] = 0  # 自身のところに行くコストは０

        for k in range(self.n):
            for i in range(self.n):
                for j in range(self.n):
                    if dist[i][j] > dist[i][k] + dist[k][j]:
                        dist[i][j] = dist[i][k] + dist[k][j]
        return dist

    def warshall_folyd2(self, INF=float("inf")):
        """
        :param INF: INF = 10**18 にすると、負のコストがある場合に少し面倒になる
        :return: 頂点 i, j 間の距離を行列として返す
        """
        dist = [[INF] * self.n for _ in range(self.n)]

        for i, j, cost in self.edges2:
            dist[i][j] = cost
            if dist[i][j] <= L:
                data.append((i, j))
        for i in range(self.n):
            dist[i][i] = 0

        for k in range(self.n):
            for i in range(self.n):
                for j in range(self.n):
                    if dist[i][j] > dist[i][k] + dist[k][j]:
                        dist[i][j] = dist[i][k] + dist[k][j]
                        if dist[i][j] <= L:
                            data.append((i, j))
        return dist

def max2(x,y):
    return x if x > y else y

N, M, L = map(int, input().split())
graph = Graph(N, directed=False, decrement=True)
for _ in range(M):
    x, y, cost = map(int, input().split())
    graph.add_edge(x, y, cost)

data = []
graph.warshall_folyd2()

graph2 = Graph(N, directed=False, decrement=False)
for x, y in data:
    graph2.add_edge(x, y, 1)

d = graph2.warshall_folyd()

for _ in range(int(input())):
    s, t, = map(int, input().split())
    s, t = s-1, t-1
    print(d[s][t]-1 if d[s][t] != float("inf") 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

d=[[float("inf")]*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 #自身のところに行くコストは０
D=warshall_floyd(d)
E=[[float("inf")]*N for i in range(N)] 
for i in range(N):
  for j in range(N):
    if D[i][j]==0:
      E[i][j]=0
    elif D[i][j]<=L:
      E[i][j]=1
F=warshall_floyd(E)
N=int(input())
for i in range(N):
  x,y=map(int,input().split())
  if F[x-1][y-1]==float("inf"):
    print(-1)
  else:
    print(F[x-1][y-1]-1)

Submission status: Time Limit Exceeded

Solution code:
import heapq
N,M,L=map(int,input().split())
ABC=[list(map(int,input().split()))for i in range(M)]
Q=int(input())
ST=[list(map(int,input().split()))for i in range(Q)]

ans=[[-1]*N for _ in range(N)]
  
ways=[[] for _ in range(N)]
for a,b,c in ABC:
  ways[a-1].append([b-1,c])
  ways[b-1].append([a-1,c])
  
import heapq
  
for i in range(N):
  #dp[i] 町iに到達する時の使用量=(L*補給回数+現在使用済みの燃料)の最小値
  dp=[float("inf")]*N
  start=i
  dp[start]=0
  #データ型は(使用量、町)
  #q=heapq.heapify([(0,start)])
  #q=heapq.heapify([])
  q=[]
  heapq.heappush(q,(0,start))
  #print(q)
  while q:
    #print("called")
    tmp=heapq.heappop(q)
    energy,town=tmp
    if dp[town] < energy:
      continue
    remain=L-(energy%L)
    for to,dist in ways[town]:
      #補給が不要なら向かう。
      #必要なら補給してから向かう。
      if dist<=remain:
        if dp[to]>energy+dist:
          dp[to]=energy+dist
          heapq.heappush(q,(energy+dist,to))
        continue
      else:
        if dist>L:
          continue
        if dp[to]>energy+remain+dist:
          dp[to]=energy+remain+dist
          heapq.heappush(q,(energy+remain+dist,to))
        continue
  for goal in range(N):  
    if dp[goal]==float("inf"):
      ans[i][goal]=-1
    else:
      ans[i][goal]=dp[goal]//L - (dp[goal]%L==0)

for s,t in ST:
  print(ans[s-1][t-1])

Submission status: Time Limit Exceeded

Solution code:
N,M,L=map(int,input().split())
ABC=[list(map(int,input().split()))for i in range(M)]
Q=int(input())
ST=[list(map(int,input().split()))for i in range(Q)]

ways=[[] for _ in range(N)]
for a,b,c in ABC:
  ways[a-1].append([b-1,c])
  ways[b-1].append([a-1,c])
  
import heapq
  
for i in range(Q):
  #dp[i] 町iに到達する時の使用量=(L*補給回数+現在使用済みの燃料)の最小値
  dp=[float("inf")]*N
  start=ST[i][0]-1
  dp[start]=0
  goal=ST[i][1]-1
  #データ型は(使用量、町)
  #q=heapq.heapify([(0,start)])
  #q=heapq.heapify([])
  q=[]
  heapq.heappush(q,(0,start))
  #print(q)
  while q:
    #print("called")
    tmp=heapq.heappop(q)
    energy,town=tmp
    if dp[town] < energy:
      continue
    remain=L-(energy%L)
    for to,dist in ways[town]:
      #補給が不要なら向かう。
      #必要なら補給してから向かう。
      if dist<=remain:
        if dp[to]>energy+dist:
          dp[to]=energy+dist
          heapq.heappush(q,(energy+dist,to))
        continue
      else:
        if dist>L:
          continue
        if dp[to]>energy+remain+dist:
          dp[to]=energy+remain+dist
          heapq.heappush(q,(energy+remain+dist,to))
        continue
  if dp[goal]==float("inf"):
    print(-1)
  else:
    print(dp[goal]//L - (dp[goal]%L==0) )

Submission status: Time Limit Exceeded

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

INF = float('inf')
d1 = [[INF]*N for _ in range(N)]


for _ in range(M):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    d1[a][b] = c
    d1[b][a] = c
for i in range(N):
    d1[i][i] = 0
for k in range(N):
    for i in range(N):
        for j in range(N):
            d1[i][j] = min(d1[i][k] + d1[k][j], d1[i][j])

d2 = [[INF]*N for _ in range(N)]

for i in range(N):
    for j in range(N):
        if i == j:
            d2[i][j] = 0
        if d1[i][j] <= L and i != j:
            d2[i][j] = 1
for k in range(N):
    for i in range(N):
        for j in range(N):
            d2[i][j] = min(d2[i][k] + d2[k][j], d2[i][j])
Q = int(input())
for _ in range(Q):
    s, t = map(int, input().split())
    s -= 1
    t -= 1
    if d2[s][t] == INF:
        print(-1)
    else:
        print(d2[s][t]-1)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import heapq
    import sys
    input = sys.stdin.buffer.readline
    N, M, L = map(int, input().split())

    G = [set() for i in range(N)]
    for i in range(M):
        A, B, C = map(int, input().split())
        A -= 1
        B -= 1
        G[A].add((B, C))
        G[B].add((A, C))

    # ある地点からそこまでにL以下の道があるか、０でいける地点からそのときの残量以下で行ける地点が0で行ける地点
    # ある地点からL以下ではいけるが、その地点に行くまでの残量ではいけない場合には、+1

    D = [[[-1, -1]for j in range(N)] for i in range(N)]
    for i in range(N):
        D[i][i] = [0, L]
    #q = collections.deque()
    hq = []
    count = 0
    for i in range(N):
        r = set([i])
        # q.append(i)
        hq = [(0, i)]
        DD = D[i]
        while(hq):
            count += 1
            #x = q.popleft()
            d, x = heapq.heappop(hq)
            for y, c in G[x]:
                if c > L:
                    continue
                elif c > DD[x][1]:
                    if DD[y][0] == -1 or DD[y][0] > DD[x][0]+1:
                        DD[y][0] = DD[x][0] + 1
                        DD[y][1] = L - c
                        heapq.heappush(hq, (DD[y][0], y))
                    elif DD[y][0] == DD[x][0]+1 and DD[y][1] < L - c:
                        DD[y][1] = L - c
                        heapq.heappush(hq, (DD[y][0], y))
                else:
                    if DD[y][0] == -1 or DD[y][0] > DD[x][0]:
                        DD[y][0] = DD[x][0]
                        DD[y][1] = DD[x][1] - c
                        heapq.heappush(hq, (DD[y][0], y))
                    elif DD[y][0] == DD[x][0] and DD[y][1] < DD[x][1] - c:
                        DD[y][1] = DD[x][1] - c
                        heapq.heappush(hq, (DD[y][0], y))
    # print(D)

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


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import heapq
    import sys
    input = sys.stdin.buffer.readline
    N, M, L = map(int, input().split())

    G = [[-1]*N for i in range(N)]
    for i in range(M):
        A, B, C = map(int, input().split())
        A -= 1
        B -= 1
        G[A][B] = C
        G[B][A] = C

    # ある地点からそこまでにL以下の道があるか、０でいける地点からそのときの残量以下で行ける地点が0で行ける地点
    # ある地点からL以下ではいけるが、その地点に行くまでの残量ではいけない場合には、+1

    D = [[[-1, -1]for j in range(N)] for i in range(N)]
    for i in range(N):
        D[i][i] = [0, L]
    #q = collections.deque()
    hq = []
    count = 0
    for i in range(N):
        r = set([i])
        # q.append(i)
        hq = [(0, i)]
        while(hq):
            count += 1
            #x = q.popleft()
            d, x = heapq.heappop(hq)
            for y in range(N):
                if y not in r and G[x][y] >= 0:
                    if G[x][y] > L:
                        continue
                    elif G[x][y] > D[i][x][1]:
                        if D[i][y][0] == -1 or D[i][y][0] > D[i][x][0]+1:
                            D[i][y][0] = D[i][x][0] + 1
                            D[i][y][1] = L - G[x][y]
                            heapq.heappush(hq, (D[i][y][0], y))
                        elif D[i][y][0] == D[i][x][0]+1 and D[i][y][1] < L - G[x][y]:
                            D[i][y][1] = L - G[x][y]
                            heapq.heappush(hq, (D[i][y][0], y))
                    else:
                        if D[i][y][0] == -1 or D[i][y][0] > D[i][x][0]:
                            D[i][y][0] = D[i][x][0]
                            D[i][y][1] = D[i][x][1] - G[x][y]
                            heapq.heappush(hq, (D[i][y][0], y))
                        elif D[i][y][0] == D[i][x][0] and D[i][y][1] < D[i][x][1] - G[x][y]:
                            D[i][y][1] = D[i][x][1] - G[x][y]
                            heapq.heappush(hq, (D[i][y][0], y))
    # print(D)

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


main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python

import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**6)
INF = float("inf")

def main():
    N,M,L = map(int,input().split())
    ABC = [tuple(map(int,input().split())) for _ in range(M)]
    Q = int(input())
    ST = [tuple(map(int,input().split())) for _ in range(Q)]

    # 町の最短距離を求める
    A = [[INF for _ in range(N)] for _ in range(N)]
    for a,b,c in ABC:
        A[a-1][b-1] = c
        A[b-1][a-1] = c
    for k in range(N):
        for i in range(N):
            for j in range(N):
                A[i][j] = min(A[i][j], A[i][k]+A[k][j])
    
    # 求めた町の距離が L以下 に 1の辺をはる (給油なしでたどり着ける)
    B = [[INF for _ in range(N)] for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if A[i][j] <= L:
                B[i][j] = 1
    # 最短距離を求める
    for k in range(N):
        for i in range(N):
            for j in range(N):
                B[i][j] = min(B[i][j], B[i][k]+B[k][j])
    
    for s,t in ST:
        if B[s-1][t-1] == INF:
            print(-1)
        else:
            print(B[s-1][t-1] - 1)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import networkx as nx

INF = float('inf')

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

    G = nx.Graph()
    G.add_nodes_from([i for i in range(1, N+1)])

    edges = []

    for i in range(M):
        a, b, c = map(int, input().split())
        edges.append((a, b, c))
    G.add_weighted_edges_from(edges)
    Q = int(input())
    Queries = []
    for i in range(Q):
        s, t = map(int, input().split())
        Queries.append((s, t))

    
    # ワーシャルフロイド法で、全点間の距離を求める
    cost = nx.floyd_warshall(G)
    # print(cost)
    # 全点間の距離のうち、移動距離がL以内でおさまる頂点同士は、給油せずにすむ
    # そこで、全点間の距離のうち、移動距離がL以内でおさまる頂点同士を距離1で結んだグラフを作成し、
    # そのグラフに対してワーシャルフロイド法で最短距離を計算することで、
    # refuel[x][y] =「xからyへ移動するときの給油回数+1」というグラフを作成できる
    no_refuel_edges = []
    for i in range(1, N+1):
        for j in range(i, N+1):
            if cost[i][j] <= L:
                no_refuel_edges.append((i, j, 1))
    no_refuel = nx.Graph()
    no_refuel.add_nodes_from([i for i in range(1, N+1)])
    no_refuel.add_weighted_edges_from(no_refuel_edges)
    refuel_count = nx.floyd_warshall(no_refuel)
    # print(refuel_count)
    ans = []
    for s, t in Queries:
        d = refuel_count[s][t]
        ans.append(int(d-1) if d != INF else -1)
    
    print(*ans, sep='\n')

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
INF = float('inf')

def warshall_floyd(G):
    # ワーシャルフロイド法で移動距離を求める
    # G[x][y]: xからyへ直接移動するときの距離。直接移動できない場合はINF
    # 
    cost = [g[:] for g in G]
    N = len(G)
    # cost[i][j]: 頂点v_iから頂点v_jへ到達するための辺コストの和
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if cost[i][k] != INF and cost[k][j] != INF:
                    cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j])
    return cost

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

    # G[x][y]: xからyへ直接移動するときのコスト。移動できない場合はINF
    G = [[INF] * (N+1) for n in range(N+1)]

    for i in range(M):
        a, b, c = map(int, input().split())
        G[a][b] = c
        G[b][a] = c

    Q = int(input())
    Queries = []
    for i in range(Q):
        s, t = map(int, input().split())
        Queries.append((s, t))

    # ワーシャルフロイド法で、全点間の距離を求める
    cost = warshall_floyd(G)

    # 全点間の距離のうち、移動距離がL以内でおさまる頂点同士は、給油せずにすむ
    # そこで、全点間の距離のうち、移動距離がL以内でおさまる頂点同士を距離1で結んだグラフを作成し、
    # そのグラフに対してワーシャルフロイド法で最短距離を計算することで、
    # refuel[x][y] =「xからyへ移動するときの給油回数+1」というグラフを作成できる
    no_refuel = [[1 if x <= L else INF for x in c] for c in cost]

    refuel_count = warshall_floyd(no_refuel)

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

if __name__ == '__main__':
    main()