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:
INF = 10000000000
import math
def main():
    N, M, L = map(int, input().split())
    d = [[INF for i in range(N)] for j in range(N)]
    d[0][0] = 0
    ans_d = [[INF for i in range(N)] for j in range(N)]
    ans_d[0][0] = 0
    for i in range(M):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        if c > L:
            continue 
        d[a][b] = c
        d[b][a] = c
    for k in range(N):
        for i in range(N):
            for j in range(N):
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j])

    for i in range(N):
        for j in range(N):
            if d[i][j] <= L:
                ans_d[i][j] = 1
                ans_d[j][i] = 1

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

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



if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def warshall_floyd(d):
	for k in range(n):
		for i in range(n):
			for j in range(n):
				d[i][j]=min(d[i][j],d[i][k]+d[k][j])
	return d
n,m,l=map(int,input().split())
d=[[10**10 for _ in range(n)]for _ in range(n)]
for i in range(n):
	d[i][i]=0
for i in range(m):
	a,b,c=map(int,input().split())
	d[a-1][b-1]=c
	d[b-1][a-1]=c
p=[[10**5 for _ in range(n)]for _ in range(n)]
d=warshall_floyd(d)
for i in range(n):
	for j in range(n):
		if d[i][j]<=l:
			p[i][j]=1
p=warshall_floyd(p)
q=int(input())
for i in range(q):
	s,t=map(int,input().split())
	if p[s-1][t-1]==10**5:
		print(-1)
		continue
	print(p[s-1][t-1]-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.buffer.readline
from collections import deque
N, M, L = map(int, input().split())
D = [[1<<40] * N for _ in range(N)]
for i in range(N):
    D[i][i] = 0
for _ in range(M):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    D[a][b] = c
    D[b][a] = c

for k in range(N):
    for i in range(N):
        for j in range(N):
            D[i][j] = min(D[i][j], D[i][k] + D[k][j])
Y = [[] for _ in range(N)]
for i in range(N):
    for j in range(N):
        if i == j: continue
        if D[i][j] <= L:
            Y[i].append(j)
def BFS(n, E, i0=0):
    Q = deque([i0])
    D = [-1] * n
    D[i0] = 0
    while Q:
        x = Q.popleft()
        for c in E[x]:
            if D[c] == -1:
                D[c] = D[x] + 1
                Q.append(c)
    return D
D2 = []
for i in range(N):
    D2.append(BFS(N, Y, i))

ans = []
for _ in range(int(input())):
    s, t = map(int, input().split())
    a = D2[s-1][t-1]-1
    ans.append(str(a if a >= 0 else -1))
print("\n".join(ans))

Submission status: Time Limit Exceeded

Solution code:
INF = 10000000000
import math
def main():
    N, M, L = map(int, input().split())
    d = [[INF for i in range(N)] for j in range(N)]
    ans_d = [[INF for i in range(N)] for j in range(N)]
    for i in range(M):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        if c > L:
            continue 
        d[a][b] = c
        d[b][a] = c
    for k in range(N):
        for i in range(N):
            for j in range(N):
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j])
    for i in range(N):
        for j in range(N):
            if d[i][j] <= L:
                ans_d[i][j] = 1
    for k in range(N):
        for i in range(N):
            for j in range(N):
                    ans_d[i][j] = min(ans_d[i][j], ans_d[i][k] + ans_d[k][j])
    #print(pre)
    Q = int(input())
    for i in range(Q):
        s, t = map(int, input().split())
        s -= 1
        t -= 1
        if d[s][t] == INF:
            print(-1)
        else:
            print(ans_d[s][t] - 1)



if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N, M, L = map(int, input().split())
roads = [[float('inf')]*N for _ in [0]*N]
kyuyu = [[float('inf')]*N for _ in [0]*N]
for _ in range(M):
    a, b, c = map(int, input().split())
    if c <= L:  # 移動出来ない経路は消す
        roads[a-1][b-1] = c
        roads[b-1][a-1] = c

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

for i in range(N):
    for j in range(i+1, N):
        if roads[i][j] <= L:
            kyuyu[i][j] = 1
            kyuyu[j][i] = 1

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

Q = int(input())
for _ in range(Q):
    s, t = map(lambda x: int(x)-1, input().split())
    dist = kyuyu[s][t]
    if dist == float('inf'):
        print(-1)
    else:
        print(dist-1)

Submission status: Time Limit Exceeded

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

N,M,L=map(int, input().split())
graph=np.zeros((N,N),int)
g=np.zeros((N,N),int)
for _ in range(M):
    A,B,C=map(int, input().split())
    if C<=L:
      graph[A-1,B-1]=C
      graph[B-1,A-1]=C
        
graph = csr_matrix(graph)
dist_matrix, predecessors = dijkstra(csgraph=graph, directed=False, return_predecessors=True)
g[dist_matrix<=L]=1
graph=csr_matrix(g)
dist_matrix, predecessors2 = dijkstra(csgraph=graph, directed=False, return_predecessors=True)

Q=int(input())
for _ in range(Q):
  S,T=map(int, input().split()) 
  if predecessors[S-1,T-1]<0:
    l=0
  else:
    l=dist_matrix[S-1,T-1]

  print(int(l)-1)

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline

def main():
	N, M, L = list(map(int,input().split()))
	P = [list(map(int,input().split())) for i in range(M)]
	Q = int(input())
	st = [list(map(int,input().split())) for i in range(Q)]

	neighbor = [[] for i in range(N)]
	for s,e,d in P:
		if d<=L:
			neighbor[s-1].append((e-1,d))
			neighbor[e-1].append((s-1,d))

	fuellist = [0]*N
	def bfs(start, end):
		fuel = [[10000000,L+1] for i in range(N)]
		fuel[start][0] = 0
		fuel[start][1] = L
		queue = [start]
		while len(queue)>0:
			nq = []						# next target node
			nq_append = nq.append
			for i in queue:				# target node
				oc, om = fuel[i]
				for j, d in neighbor[i]:	# next node
					if om<d:
						nc = oc+1
						nm = L-d
					else:
						nc = oc
						nm = om-d

					# print(i,j,nc,nm)

					if (nc<fuel[j][0]) or (nc==fuel[j][0] and nm>fuel[j][1]):
						fuel[j][0], fuel[j][1] = nc, nm
						nq_append(j)

			queue = nq					# update target node

		ans = fuel[end][0]
		if fuel[end][0]==10000000: ans = -1

		fuellist[start] = fuel

		print(ans)

	for s, t in st:
		start, end = s-1, t-1
		if fuellist[start]==0:
			bfs(start,end)
		else:
			ans = fuellist[start][end][0]
			if ans==10000000: ans = -1
			print(ans)


if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N, M, L = map(int, input().split())
roads = [[float('inf')]*N for _ in range(N)]
kyuyu = [[float('inf')]*N for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    if c <= L:  # 移動出来ない経路は消す
        roads[a-1][b-1] = c
        roads[b-1][a-1] = c

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

for i in range(N):
    for j in range(i+1, N):
        if roads[i][j] <= L:
            kyuyu[i][j] = 1
            kyuyu[j][i] = 1

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

Q = int(input())
for _ in range(Q):
    s, t = map(lambda x: int(x)-1, input().split())
    dist = kyuyu[s][t]
    if dist == float('inf'):
        print(-1)
    else:
        print(dist-1)

Submission status: Time Limit Exceeded

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


def create_graph(N, edge_pairs, is_bi_dir=False):
    in_vs, out_vs, weights = [], [], []
    for s, t, w in edge_pairs:
        in_vs.append(s)
        out_vs.append(t)
        weights.append(w)
        if is_bi_dir:
            in_vs.append(t)
            out_vs.append(s)
            weights.append(w)
    return csr_matrix((weights, (in_vs, out_vs)), shape=(N, N), dtype=np.int64)


N, M, L = map(int, input().split())
edge_pairs = []
for _ in range(M):
    s, t, w = map(int, input().split())
    edge_pairs.append((s-1, t-1, w))
graph = create_graph(N, edge_pairs, True)
dist = floyd_warshall(graph)
edge_pairs = []
for i in range(N):
    for j in range(i+1, N):
        if dist[i][j] <= L:
            edge_pairs.append((i, j, 1))
graph = create_graph(N, edge_pairs, True)
dist = floyd_warshall(graph)

Q = int(input())
for _ in range(Q):
    s, t = map(int, input().split())
    ans = dist[s-1][t-1]
    if np.isinf(ans):
        print(-1)
    else:
        print(int(ans - 1))

Submission status: Time Limit Exceeded

Solution code:
INF = float('inf')
N,M,L = map(int,input().split())
cost = [[INF]*N for _ in range(N)]
for i 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):
            if cost[i][j] > cost[i][k]+cost[k][j]:
                cost[i][j] = cost[i][k]+cost[k][j]

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

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

for i in range(N):
    for j in range(N):
        if cost[i][j] == INF:
            cost[i][j] = -1
        else:
            cost[i][j] -= 1

Q = int(input())

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
N, M, L = map(int, input().split())
ABC = [list(map(int, input().split())) for _ in range(M)]
Q = int(input())
st = [list(map(int, input().split())) for _ in range(Q)]


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

d = [[float('inf') for _ in range(N)] for _ in range(N)]

for abc in ABC:
    d[abc[0]-1][abc[1]-1] = abc[2]
    d[abc[1]-1][abc[0]-1] = abc[2]
for i in range(N):
    d[i][i] = 0
wf(d)

for i in range(N):
    for j in range(N):
        if d[i][j] <= L:
            d[i][j] = 1
        else:
            d[i][j] = float('inf')

wf(d)

for sti in st:
    res = d[sti[0]-1][sti[1]-1]
    if res == float('inf'):
        print(-1)
    else:
        print(res-1)

Submission status: Time Limit Exceeded

Solution code:
import heapq as hq
import sys
input = sys.stdin.readline


def f():
    N, M, L = map(int, input().split())
    out_link = {i: set() for i in range(N)}
    min_length = {(i, j): -1 for i in range(N) for j in range(N)}


    for _ in range(M):
        A, B, C = map(int, input().split())
        if C > L:
            continue

        A -= 1
        B -= 1
        out_link[A].add((B, C))
        out_link[B].add((A, C))


    def should_supply(now_cost, next_cost):
        if now_cost % L == 0:
            return False

        return (now_cost - 1) // L != (next_cost - 1) // L


    def search(S):
        already = set()
        H = [(0, S)]
        while H:
            c, p = hq.heappop(H)
            if p in already:
                continue

            already.add(p)
            min_length[(S, p)] = (c - 1) // L
            min_length[(p, S)] = (c - 1) // L

            for q, add_cost in out_link[p]:
                if q in already:
                    continue
                next_cost = c + add_cost
                if should_supply(c, next_cost):
                    next_cost = (c // L + 1) * L + add_cost

                hq.heappush(H, (next_cost, q))


    calced_s = set()
    Q = int(input())
    ans = ""
    for _ in range(Q):
        s, t = map(int, input().split())
        s -= 1
        t -= 1
        if s not in calced_s:
            search(s)
            calced_s.add(s)
        res = min_length[(s, t)]
        ans += str(res) + "\n"

    print(ans)

if __name__ == '__main__':
   f()

Submission status: Time Limit Exceeded

Solution code:
import heapq
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N, M, L = map(int, input().split())
roads = [[float('inf')]*N for _ in range(N)]
kyuyu = [[float('inf')]*N for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    if c <= L:  # 移動出来ない経路は消す
        roads[a-1][b-1] = c
        roads[b-1][a-1] = c

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

for i in range(N):
    for j in range(N):
        if roads[i][j] <= L:
            kyuyu[i][j] = 1

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

Q = int(input())
for _ in range(Q):
    s, t = map(lambda x: int(x)-1, input().split())
    dist = kyuyu[s][t]
    if dist == float('inf'):
        print(-1)
    else:
        print(dist-1)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
import heapq
import functools
INF = float("inf")

# 無向グラフを仮定する。


class Graph(object):
    def __init__(self, N):
        self.N = N
        self.E = [[] for _ in range(N)]

    def add_edge(self, s, t, w=1):
        self.E[s].append((t, w))
        self.E[t].append((s, w))


@functools.lru_cache(maxsize=None)
def shortestPath(g: Graph, s: int, L: int):

    charge = [INF]*g.N
    charge[s] = 0

    rest = [INF]*g.N            # 現在の走行距離
    rest[s] = 0

    Q = []
    heapq.heappush(Q, s)

    while len(Q) > 0:
        u = heapq.heappop(Q)
        for v, w in g.E[u]:
            if rest[u]+w > L:
                c, r = (charge[u]+1, w)
            else:
                c, r = (charge[u], rest[u]+w)
            if charge[v] > c or (charge[v] == c and rest[v] > r):
                rest[v] = r
                charge[v] = c
                heapq.heappush(Q, v)

    return charge, rest


def solve(N: int,
          M: int,
          L: int,
          A: "List[int]",
          B: "List[int]",
          C: "List[int]",
          Q: int,
          s: "List[int]",
          t: "List[int]"):
    g = Graph(N)
    for i in range(M):
        if C[i] <= L:
            g.add_edge(A[i]-1, B[i]-1, C[i])

    for i in range(Q):
        charge, rest = shortestPath(g, s[i]-1, L)
        if charge[t[i]-1] == INF:
            print(-1)
        else:
            print(charge[t[i]-1])

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    L = int(next(tokens))  # type: int
    A = [int()] * (M)  # type: "List[int]"
    B = [int()] * (M)  # type: "List[int]"
    C = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
        C[i] = int(next(tokens))
    Q = int(next(tokens))  # type: int
    s = [int()] * (Q)  # type: "List[int]"
    t = [int()] * (Q)  # type: "List[int]"
    for i in range(Q):
        s[i] = int(next(tokens))
        t[i] = int(next(tokens))
    solve(N, M, L, A, B, C, Q, s, t)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
import heapq
from itertools import accumulate
INF = float("inf")

# 無向グラフを仮定する。


class Graph(object):
    def __init__(self, N):
        self.N = N
        self.E = [[] for _ in range(N)]

    def add_edge(self, s, t, w=1):
        self.E[s].append((t, w))
        self.E[t].append((s, w))


def shortestPath(g: Graph, s: int, L: int):

    charge = [INF]*g.N
    charge[s] = 0

    rest = [INF]*g.N            # 現在の走行距離
    rest[s] = 0

    Q = []
    heapq.heappush(Q, s)

    while len(Q) > 0:
        u = heapq.heappop(Q)
        for v, w in g.E[u]:
            if rest[u]+w > L:
                c, r = (charge[u]+1, w)
            else:
                c, r = (charge[u], rest[u]+w)
            if charge[v] > c or (charge[v] == c and rest[v] > r):
                rest[v] = r
                charge[v] = c
                heapq.heappush(Q, v)

    return charge, rest


def solve(N: int,
          M: int,
          L: int,
          A: "List[int]",
          B: "List[int]",
          C: "List[int]",
          Q: int,
          s: "List[int]",
          t: "List[int]"):
    g = Graph(N)
    for i in range(M):
        if C[i] <= L:
            g.add_edge(A[i]-1, B[i]-1, C[i])

    charges = []
    rests = []
    for i in range(N):
        charge, rest = shortestPath(g, i, L)
        charges.append(charge)
        rests.append(rest)

    for i in range(Q):
        charge, rest = charges[s[i]-1], rests[s[i]-1]
        if charge[t[i]-1] == INF:
            print(-1)
        else:
            print(charge[t[i]-1])

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    L = int(next(tokens))  # type: int
    A = [int()] * (M)  # type: "List[int]"
    B = [int()] * (M)  # type: "List[int]"
    C = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
        C[i] = int(next(tokens))
    Q = int(next(tokens))  # type: int
    s = [int()] * (Q)  # type: "List[int]"
    t = [int()] * (Q)  # type: "List[int]"
    for i in range(Q):
        s[i] = int(next(tokens))
        t[i] = int(next(tokens))
    solve(N, M, L, A, B, C, Q, s, t)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline

def main():
	N, M, L = list(map(int,input().split()))
	P = [list(map(int,input().split())) for i in range(M)]
	Q = int(input())
	st = [list(map(int,input().split())) for i in range(Q)]

	neighbor = [[] for i in range(N)]
	for s,e,d in P:
		if d<=L:
			neighbor[s-1].append((e-1,d))
			neighbor[e-1].append((s-1,d))

	fuellist = [0]*N
	def bfs(start, end):
		fuel = [[10000000,L+1] for i in range(N)]
		fuel[start][0] = 0
		fuel[start][1] = L
		queue = [start]
		while len(queue)>0:
			nq = []						# next target node
			for i in queue:				# target node
				oc, om = fuel[i]
				for j, d in neighbor[i]:	# next node
					if om<d:
						nc = oc+1
						nm = L-d
					else:
						nc = oc
						nm = om-d

					# print(i,j,nc,nm)

					if (nc<fuel[j][0]) or (nc==fuel[j][0] and nm>fuel[j][1]):
						fuel[j][0], fuel[j][1] = nc, nm
						nq.append(j)

			queue = nq					# update target node

		ans = fuel[end][0]
		if fuel[end][0]==10000000: ans = -1

		fuellist[start] = fuel

		print(ans)

	for s, t in st:
		start, end = s-1, t-1
		if fuellist[start]==0:
			bfs(start,end)
		else:
			ans = fuellist[start][end][0]
			if ans==10000000: ans = -1
			print(ans)


if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
import collections
def main():

    N, M, L = map(int, input().split())
    d = [[float("inf") for _ in range(N)] for _ in range(N)]
    for _ in range(M):
        a, b, c = map(int, input().split())
        if c <= L:
            d[a-1][b-1] = c
            d[b-1][a-1] = c

    # d = [[float("inf") for _ in range(N)] for _ in range(N)]
    for i in range(N): d[i][i] = 0

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

    # print(d)

    Q = int(input())
    gas = [[-1 for _ in range(N)] for _ in range(N)]
    for i in range(N):
        cur  = set([i])
        cnt = 0
        while cur:
            temp = set()
            for j in cur:
                for k in range(N):
                    if d[j][k] <= L and gas[i][k] == -1:
                        gas[i][k] = cnt
                        temp.add(k)
            # print(temp)
            # print(temp)
            cur = temp
            cnt += 1

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def WarshallFloyd(M):
    N = len(M)
    for k in range(N):
        for j in range(N):
            for i in range(N):
                M[i][j] = min(M[i][j], M[i][k] + M[k][j])
    return M

INF = float("inf")

N, M, L = map(int, input().split())
E = [[INF] * N for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    E[a - 1][b - 1] = E[b - 1][a - 1] = c


E = WarshallFloyd(E)

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

E = WarshallFloyd(E)

Q = int(input())
for _ in range(Q):
    s, t = map(int, input().split())
    a = E[s - 1][t - 1] - 1
    print(-1 if a == INF else a)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[]]*num
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

from collections import deque
import copy

N,M,L = II()
A,B,C = Line(M,3)
Q = I()
s,t = Line(Q,2)

from heapq import heappop, heappush
def dijkstra(E,s,n):
    inf=float('inf')
    d=[inf for _ in range(n)]
    d[s]=0
    prev = [None]*n
    q=[]
    heappush(q,(0,s))
    while q:
        du, u1 = heappop(q)
        if d[u1]<du: continue
        for v1,weight in E[u1].items():
            alt=du+weight
            if d[v1]>alt:
                d[v1]=alt
                prev[v1] = u1
                heappush(q, (alt,v1))
    return d,prev

E = [dict() for _ in range(N)]
for i in range(M):
    E[A[i]-1][B[i]-1] = C[i]
    E[B[i]-1][A[i]-1] = C[i]


pa = [[] for _ in range(N)]
for i in range(N):
    d,prev = dijkstra(E,i,N)
    pa[i] = prev

path = [[[] for _ in range(N)] for _ in range(N)]
for i in range(N):
    for j in range(N):
        k = j
        while pa[i][k]!=None:
            k = pa[i][k]
            path[i][j].append(k)
        path[i][j] = list(reversed(path[i][j]))

E2 = [[float('inf')]*N for _ in range(N)]
for i in range(N):
    E2[i][i] = 0
for i in range(M):
    E2[A[i]-1][B[i]-1] = C[i]
    E2[B[i]-1][A[i]-1] = C[i]

ans = [[0]*N for _ in range(N)]
for i in range(N):
    for j in range(N):
        l = L
        now = i
        p = 0
        if path[i][j]:
            ne = path[i][j][p]
        else:
            ne = j
        while now != j:
            if E2[now][ne]>L:
                ans[i][j] = -1
                break
            elif l < E2[now][ne]:
                ans[i][j] += 1
                l = L-E2[now][ne]
                now = ne
                if path[ne][j]:
                    ne = path[ne][j][0]
                else:
                    ne = j
            else:
                l -= E2[now][ne]
                now = ne
                if path[ne][j]:
                    ne = path[ne][j][0]
                else:
                    ne = j                 

for i in range(Q):
    print(ans[s[i]-1][t[i]-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
input = lambda: sys.stdin.readline().rstrip()
inpl = lambda: list(map(int,input().split()))
N, M, L = inpl()
road = [[] for _ in range(N)]
for i in range(M):
    A, B, C = inpl()
    if C <= L:
        road[A-1].append((B-1,C))
        road[B-1].append((A-1,C))
minimum = [ [(-1,0)]*N for _ in range(N)]
for i in range(N):
    minimum[i][i] = (0,0)

Q = int(input())
ST = [inpl() for _ in range(Q)]
starts = set([ s-1 for s,t in ST])
for start in starts:
    prev = {start}
    while prev:
        cur = set()
        for p in prev:
            for q, c in road[p]:
#                print(p,q)
                pn, pred = minimum[start][p]
                qn, qred = minimum[start][q]
                if pred + c > L:
                    qn2, qred2 = pn + 1, c
                else:
                    qn2, qred2 = pn, pred + c
                if qn < 0 or qn2 < qn or (qn2==qn and qred2 < qred):
                    minimum[start][q] = qn2, qred2
                    cur.add(q)
#                    print(start,q,qn2,qred2)
        prev = cur

#print(minimum)

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

Submission status: Time Limit Exceeded

Solution code:
N,M,L = map(int, input().strip().split(' '))
G = [[float('inf') for _ in range(N)] for _ in range(N)]
for _ in range(M):
  A,B,C = map(int, input().strip().split(' '))
  if C > L: continue
  A,B = A-1,B-1
  G[A][B] = C
  G[B][A] = C
  
def DFS(state, T, visited):  # 今の状態(町、残燃料、給油回数)、目的地、訪問済み
  now, now_fuel, now_ref = state
  if G[now][T] != float('inf'):  # １hopで行けるなら、その方が絶対良い
    if G[now][T] > now_fuel:
      return now_ref+1
    else:
      return now_ref
  
  next_set = set(range(N))-visited-{T}
  if len(next_set) == 0:
    return float('inf')
  res = float('inf')
  for next_ in next_set:
    if now_ref >= res: continue
    if G[now][next_] != float('inf'):
      if G[now][next_] > now_fuel:  # 給油する
        next_fuel = L-G[now][next_]
        next_ref = now_ref+1
      else:  # 給油しない
        next_fuel = now_fuel-G[now][next_]
        next_ref = now_ref
      if next_ref >= res: continue
      next_visited = visited|{next_}
      res = min(res, DFS((next_, next_fuel, next_ref), T, next_visited))
  return res

  
Q = int(input().strip())
for _ in range(Q):
  S,T = map(int, input().strip().split(' '))
  S,T = S-1,T-1
  ans = DFS((S, L, 0),T,{S})
  print(-1 if ans == float('inf') else ans)

Submission status: Time Limit Exceeded

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


def nCharge(s, t, nmax, fuel, n, costs, visit, L, lv):
    #print("  " * lv, s+1, fuel, n)
    if s == t:
        if nmax[0] > n:
            nmax[0] = n
        return
    if nmax[0] <= n:
        return

    visit[s] = True
    for (pos,cost) in costs[s]:
        if visit[pos]:
            continue
        if fuel >= cost:
            nCharge(pos, t, nmax, fuel-cost, n, costs, visit, L, lv+1)
        else:
            nCharge(pos, t, nmax, L-cost, n+1, costs, visit, L, lv+1)
    visit[s] = False


def solve(N, M, L, A, B, C, Q, S, T):
    costs = [[] for _ in range(N)]
    for i in range(M):
        c = C[i]
        if c <= L:
            a = A[i]-1
            b = B[i]-1
            costs[a].append((b,c))
            costs[b].append((a,c))
    visit = [False for _ in range(N)]
    #print(costs)

    ans = []
    for i in range(Q):
        s = S[i]-1
        t = T[i]-1
        nmax = [N]
        nCharge(s, t, nmax, L, 0, costs, visit, L, 0)
        if nmax[0] == N:
            ans.append(-1)
        else:
            ans.append(nmax[0])

    return ans


if __name__ == '__main__':
    N, M, L = map(int, input().split())
    A = [0] * M
    B = [0] * M
    C = [0] * M
    for idx in range(M):
        A[idx], B[idx], C[idx] = map(int, input().split())
    Q = int(input())
    S = [0] * Q
    T = [0] * Q
    for idx in range(Q):
        S[idx], T[idx] = map(int, input().split())

    ans = solve(N, M, L, A, B, C, Q, S, T)

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

Submission status: Time Limit Exceeded

Solution code:
import heapq
from collections import defaultdict


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 search(s, t, L):
    queue = [(0, -L, s)]
    while queue:
        cost, fuel, cur = heapq.heappop(queue)
        if cur == t:
            return cost
        for nxt, c in graph[cur]:
            if fuel + c <= 0:
                heapq.heappush(queue, (cost, fuel + c, nxt))
                heapq.heappush(queue, (cost + 1, -L,  nxt))
    return -1


Q = int(input())
for _ in range(Q):
    s, t = map(int, input().split())
    print(search(s, t, L))