Problem:


Score : 500 points

Problem Statement

There are N towns numbered 1 to N and M roads. The i-th road connects Town A_i and Town B_i bidirectionally and has a length of C_i.

Takahashi will travel between these towns by car, passing through these roads. The fuel tank of his car can contain at most L liters of fuel, and one liter of fuel is consumed for each unit distance traveled. When visiting a town while traveling, he can full the tank (or choose not to do so). Travel that results in the tank becoming empty halfway on the road cannot be done.

Process the following Q queries:

The tank is now full. Find the minimum number of times he needs to full his tank while traveling from Town s_i to Town t_i. If Town t_i is unreachable, print -1.

Constraints

All values in input are integers.

2 \leq N \leq 300

0 \leq M \leq \frac{N(N-1)}{2}

1 \leq L \leq 10^9

1 \leq A_i, B_i \leq N

A_i \neq B_i

\left(A_i, B_i\right) \neq \left(A_j, B_j\right) (if i \neq j)

\left(A_i, B_i\right) \neq \left(B_j, A_j\right) (if i \neq j)

1 \leq C_i \leq 10^9

1 \leq Q \leq N\left(N-1\right)

1 \leq s_i, t_i \leq N

s_i \neq t_i

\left(s_i, t_i\right) \neq \left(s_j, t_j\right) (if i \neq j)

Input

Input is given from Standard Input in the following format:

N M L
A_1 B_1 C_1
:
A_M B_M C_M
Q
s_1 t_1
:
s_Q t_Q

Output

Print Q lines.

The i-th line should contain the minimum number of times the tank needs to be fulled while traveling from Town s_i to Town t_i. If Town t_i is unreachable, the line should contain -1 instead.

Sample Input 1

3 2 5
1 2 3
2 3 3
2
3 2
1 3

Sample Output 1

0
1

To travel from Town 3 to Town 2, we can use the second road to reach Town 2 without fueling the tank on the way.

To travel from Town 1 to Town 3, we can first use the first road to get to Town 2, full the tank, and use the second road to reach Town 3.

Sample Input 2

4 0 1
1
2 1

Sample Output 2

-1

There may be no road at all.

Sample Input 3

5 4 4
1 2 2
2 3 2
3 4 3
4 5 2
20
2 1
3 1
4 1
5 1
1 2
3 2
4 2
5 2
1 3
2 3
4 3
5 3
1 4
2 4
3 4
5 4
1 5
2 5
3 5
4 5

Sample Output 3

0
0
1
2
0
0
1
2
0
0
0
1
1
1
0
0
2
2
1
0



Sample input:
3 2 5
1 2 3
2 3 3
2
3 2
1 3


Sample output:
0
1

Submission status: Time Limit Exceeded

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

N, M, L = map(int, input().split())
adj = [set() for _ in range(N)]
roads = [[-1]*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
        adj[a-1].add(b-1)
        adj[b-1].add(a-1)


def calc_ans(start, end):
    dist = [[-1]*(N+1) for _ in range(N)]  # dist[i][j] iまで給油j会で行った時の残りの最大値
    dist[start][0] = L
    Q = [[0, start]]  # (給油回数、current node)
    while Q:
        kyuyu, cur_node = heapq.heappop(Q)
        if cur_node == end:
            continue
        remain = dist[cur_node][kyuyu]
        assert remain != -1
        for next in adj[cur_node]:
            # 給油せずにいく
            to_next = roads[cur_node][next]
            if dist[next][kyuyu] == -1:
                if to_next <= remain:  # 給油なしでいける
                    dist[next][kyuyu] = remain-to_next
                    heapq.heappush(Q, [kyuyu, next])
            else:
                cur_cost = dist[next][kyuyu]
                if to_next-remain > cur_cost:
                    dist[next][kyuyu] = to_next-cur_cost
                    Q.append([kyuyu, next])
                    heapq.heappush(Q, [kyuyu, next])
            #　給油していく
            if kyuyu+1 <= N and dist[next][kyuyu+1] == -1:
                dist[next][kyuyu+1] = L-to_next
                heapq.heappush(Q, [kyuyu+1, next])
            elif kyuyu+1 <= N:
                cur_cost = dist[next][kyuyu+1]
                if L-to_next > cur_cost:
                    dist[next][kyuyu] = L-to_next
                    heapq.heappush(Q, [kyuyu+1, next])

    for i in range(N):
        if dist[end][i] >= 0:
            return i
    return -1


Q = int(input())
query = [list(map(lambda x:int(x)-1, input().split())) for _ in range(Q)]

for s, t in query:
    print(calc_ans(s, t))

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,m,l = LI()
    v = [[] for i in range(n)]
    for i in range(m):
        a,b,c = LI()
        a -= 1
        b -= 1
        v[a].append((b,c))
        v[b].append((a,c))
    ans = [[float("inf")]*n for i in range(n)]
    q = []
    for s in range(n):
        d = [float("inf")]*n
        ans[s][s] = 0
        d[s] = 0
        heappush(q,(0,0,s))
        while q:
            da,dx,x = heappop(q)
            for y,w in v[x]:
                if w > l:
                    continue
                nd = dx+w
                if nd <= l:
                    na = da
                    nd_ = nd
                else:
                    na = da+1
                    nd_ = w
                if (na,nd_) < (ans[s][y],d[y]) :
                    ans[s][y] = na
                    d[y] = nd_
                    heappush(q,(na,nd_,y))
    q = I()
    for _ in range(q):
        s,t = LI()
        s -= 1
        t -= 1
        ds = ans[s][t]
        if ds == float("inf"):
            print(-1)
        else:
            print(ds)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
def dijkstra(s,n,w,cost):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        #まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True
               
        for j in range(n):
               d[j] = min(d[j],d[v]+cost[v][j])
    return d

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

n,m,l = map(int,input().split()) #n:頂点数　w:辺の数

cost = [[float("inf") for i in range(n)] for i in range(n)] 
#cost[u][v] : 辺uvのコスト(存在しないときはinf この場合は10**10)
for i in range(m):
    x,y,z = map(int,input().split())
    x-=1
    y-=1
    cost[x][y] = z
    cost[y][x] = z

kyolist=[]
for i in range(n):
    kyolist.append(dijkstra(i,n,m,cost))
"""
for kyl in kyolist:
    print(kyl)
"""
zerolist=[]

for i in range(n):
    nowzero=[]
    for j in range(n):
        if kyolist[i][j]>=1 and kyolist[i][j]<=l:
            nowzero.append(j)
    zerolist.append(nowzero)

#print(zerolist)

llist=[]
for i in range(n):
    nowlist=[1000]*n
    nowlist[i]=0
    next=[i]
    kaisu=1
    now=0
    while next!=[]:
        newnext=[]
        for nx in next:
            for j in range(len(zerolist[nx])):
                ima=zerolist[nx][j]
                if nowlist[ima]==1000:
                    nowlist[ima]=now
                    newnext.append(ima)
            """
            for j in range(n):
                if kyolist[j][nx]<=l and nowlist[j]==1000:
                    nowlist[j]=now
                    newnext.append(j)
            """
        next=newnext
        now+=1
    llist.append(nowlist)

#print(llist)
q=int(input())
for i in range(q):
    s, t = (int(i) for i in input().split())
    kotae=llist[s-1][t-1]
    if kotae==1000:
        print(-1)
    else:
        print(kotae)

Submission status: Time Limit Exceeded

Solution code:
import heapq as hq

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

out_link = {i: set() for i in range(N)}
cost = {}

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

    A -= 1
    B -= 1
    out_link[A].add(B)
    out_link[B].add(A)
    cost[(min(A, B), max(A, B))] = 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, G):
    already = set()
    H = [(0, S)]
    while H:
        c, p = hq.heappop(H)
        if p in already:
            continue

        already.add(p)
        if p == G:
            return (c - 1) // L

        for q in out_link[p]:
            add_cost = cost[min(p, q), max(p, q)]
            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))

    return -1


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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
import heapq
input = sys.stdin.readline


n, m, l = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]
graph = [[] for i in range(n)]

for i in range(m):
    a, b, cost = info[i]
    if cost > l:
        continue
    a -= 1
    b -= 1
    graph[a].append((b, cost))
    graph[b].append((a, cost))

    
def dfs(start):
    INF = float("inf")
    visited_t = [INF]*n # 回数, 残り燃料
    visited_l = [0]*n
    visited_t[start] = 0
    q = deque([(0, start)]) # cost, 位置
    while q:
        _, pos = heapq.heappop(q)
        for next_pos, cost in graph[pos]:
            tmp = cost + visited_l[pos]
            times = visited_t[pos]
            next_times = visited_t[next_pos]
            if tmp <= l:
                if next_times > times:
                    heapq.heappush(q, (times,next_pos))
                    visited_t[next_pos] = times
                    visited_l[next_pos] = tmp
                elif next_times == times:
                    if visited_l[next_pos] > tmp:
                        heapq.heappush(q, (times,next_pos))
                        visited_t[next_pos] = times
                        visited_l[next_pos] = tmp
                else:
                    continue
            else:
                tmp = cost
                if next_times > times + 1:
                    heapq.heappush(q, (times,next_pos))
                    visited_t[next_pos] = times + 1
                    visited_l[next_pos] = tmp
                elif next_times == times + 1:
                    if visited_l[next_pos] > tmp:
                        heapq.heappush(q, (times,next_pos))
                        visited_t[next_pos] = times + 1
                        visited_l[next_pos] = tmp
                else:
                    continue
    return visited_t

ans = [None]*n
for i in range(n):
    ans[i] = dfs(i)

INF = float("inf")
q = int(input())
query = [list(map(int, input().split())) for i in range(q)]
for i in range(q):
    a, b = query[i]
    a -= 1
    b -= 1
    tmp = ans[a][b]
    if tmp == INF:
        print(-1)
    else:
        print(tmp)

Submission status: Time Limit Exceeded

Solution code:
n,m,l = map(int,input().split())
road = [[] for _ in range(n)]
for _ in range(m):
  a,b,c = map(int,input().split())
  a -= 1
  b -= 1
  road[a].append([b,c])
  road[b].append([a,c])
cango = []
for i in range(n):
  tmp = [l+1 for _ in range(n)]
  tmp[i] = 0
  now = [[i,0]]
  while now:
    last = now
    now = []
    for x in last:
      for yz in road[x[0]]:
        y,z = yz
        if x[1] + z < tmp[y]:
          tmp[y] = x[1] + z
          now.append([y,tmp[y]])
  add = []
  for i in range(n):
    if 0 < tmp[i] <= l:
      add.append(i)
  cango.append(add)
q = int(input())
for _ in range(q):
  s,t = map(int,input().split())
  s -= 1
  t -= 1
  tmp = [-1 for _ in range(n)]
  tmp[s] = 0
  time = 0
  now = [s]
  while now:
    time += 1
    last = now
    now = []
    for x in last:
      for y in cango[x]:
        if tmp[y] == -1:
          tmp[y] = time - 1
          now.append(y)
    if tmp[t] != -1:
      print(tmp[t])
      break
  else:
    print(tmp[t])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
N,M,L = map(int,input().split())
load = [[]for i in range(N)]
for _ in range(M):
    a,b,c = map(int,input().split())
    if c > L:
        continue
    load[a-1].append([b-1,c])
    load[b-1].append([a-1,c])
cost =[[float('inf')]*N for i in range(N)]
for i in range(N):
    queue = deque([i])
    cost[i][i] = 0
    while(queue):
        q = queue.popleft()
        gas = cost[i][q]
        for t,c in load[q]:
            if gas//L < (gas+c-1)//L :
                if (gas//L+1)*L+c < cost[i][t]:
                    cost[i][t] = (gas//L+1)*L+c
                    queue.append(t)
            else:
                if gas+c < cost[i][t]:
                    cost[i][t] = gas+c
                    queue.append(t)
Q = int(input())
for _ in range(Q):
    s,t = map(int,input().split())
    ans = cost[s-1][t-1]
    if ans == float('inf'):
        print(-1)
    else:
        print((ans-1)//L)

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline

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 pi in P:
	if pi[2]<=L:
		neighbor[pi[0]-1].append((pi[1]-1,pi[2]))
		neighbor[pi[1]-1].append((pi[0]-1,pi[2]))

start = 0
end = 2

def main(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

	print(ans)

for s, t in st:
	start, end = s-1, t-1
	main(start,end)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from collections import deque
from heapq import heapify, heappush as hpush, heappop as hpop
N, M, L = map(int, input().split())
X = [[] for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    X[a-1].append([b-1, c])
    X[b-1].append([a-1, c])

def dijkstra(n, E, i0=0):
    h = [i0]
    D = [1 << 100] * n
    done = [0] * n
    D[i0] = 0
    
    while h:
        x = hpop(h)
        d, i = x >> 10, x & 1023
        done[i] = 1
        for j, w in E[i]:
            nd = d + w
            if nd > L: continue
            if D[j] < 0 or D[j] >= nd:
                if done[j] == 0:
                    x = nd * (1<<10) + j
                    hpush(h, x)
                    D[j] = nd
    return D
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

Y = [[] for _ in range(N)]
for i in range(N):
    D1 = dijkstra(N, X, i)
    for j in range(N):
        if i == j: continue
        if 0 <= D1[j] <= L:
            Y[i].append(j)

# print("X =", X)
# print("Y =", Y)
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:
import sys
input = sys.stdin.readline
from collections import deque
from heapq import heapify, heappush as hpush, heappop as hpop
N, M, L = map(int, input().split())
X = [[] for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    X[a-1].append([b-1, c])
    X[b-1].append([a-1, c])

def dijkstra(n, E, i0=0):
    h = [[0, i0]]
    D = [-1] * n
    done = [0] * n
    D[i0] = 0
    
    while h:
        d, i = hpop(h)
        done[i] = 1
        for j, w in E[i]:
            nd = d + w
            if nd > L: continue
            if D[j] < 0 or D[j] >= nd:
                if done[j] == 0:
                    hpush(h, [nd, j])
                    D[j] = nd
    return D
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

Y = [[] for _ in range(N)]
for i in range(N):
    D1 = dijkstra(N, X, i)
    for j in range(N):
        if i == j: continue
        if 0 <= D1[j] <= L:
            Y[i].append(j)

# print("X =", X)
# print("Y =", Y)
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:
def dijkstra(s,n,w,cost):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        #まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True
               
        for j in range(n):
               d[j] = min(d[j],d[v]+cost[v][j])
    return d

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

n,m,l = map(int,input().split()) #n:頂点数　w:辺の数

cost = [[float("inf") for i in range(n)] for i in range(n)] 
#cost[u][v] : 辺uvのコスト(存在しないときはinf この場合は10**10)
for i in range(m):
    x,y,z = map(int,input().split())
    x-=1
    y-=1
    cost[x][y] = z
    cost[y][x] = z

kyolist=[]
for i in range(n):
    kyolist.append(dijkstra(i,n,m,cost))
"""
for kyl in kyolist:
    print(kyl)
"""
llist=[]
for i in range(n):
    nowlist=[1000]*n
    nowlist[i]=0
    next=[i]
    kaisu=1
    now=0
    while next!=[]:
        newnext=[]
        for nx in next:
            for j in range(n):
                if kyolist[j][nx]<=l and nowlist[j]==1000:
                    nowlist[j]=now
                    newnext.append(j)
        next=newnext
        now+=1
    llist.append(nowlist)

#print(llist)
q=int(input())
for i in range(q):
    s, t = (int(i) for i in input().split())
    kotae=llist[s-1][t-1]
    if kotae==1000:
        print(-1)
    else:
        print(kotae)

Submission status: Time Limit Exceeded

Solution code:
import sys
from heapq import heappush, heappop
input = sys.stdin.readline
def inpl(): return list(map(int, input().split()))

N, M, L = inpl()
G = [[] for _ in range(N)]
G2 = [[999]*(N) for _ in range(N)]

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

for i in range(N):
    supply = [999]*N
    remain = [0]*N
    supply[i] = 1
    remain[i] = L
    Q = [(1, -L, i)]
    while Q:
        s, r, p = heappop(Q)
        r = -r
        if s > supply[p]:
            continue
        if (s == supply[p]) and (r < remain[p]):
            continue
        for q, c in G[p]:
            if r >= c:
                if supply[q] > s:
                    supply[q] = s
                    remain[q] = r - c
                    heappush(Q, (s, c-r, q))
                elif (supply[q] == s) & (remain[q] < r - c):
                    remain[q] = r-c
                    heappush(Q, (s, c-r, q))
            else:
                if supply[q] > s:
                    supply[q] = s + 1
                    remain[q] = L - c
                    heappush(Q, (s+1, c-L, q))
                elif (supply[q] == (s+1)) & (remain[q] < L - c):
                    supply[q] = s+1
                    remain[q] = L-c
                    heappush(Q, (s+1, c-L, q))
    for j in range(N):
        G2[i][j] = supply[j]


for _ in range(int(input())):
    s, t = inpl()
    if G2[s-1][t-1] == 999:
        print(-1)
    else:
        print(G2[s-1][t-1]-1)

Submission status: Time Limit Exceeded

Solution code:
import heapq as hq

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

out_link = {i: set() for i in range(N)}
cost = {}

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

    A -= 1
    B -= 1
    out_link[A].add(B)
    out_link[B].add(A)
    cost[(min(A, B), max(A, B))] = 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, G):
    already = set()
    H = [(0, S)]
    while H:
        c, p = hq.heappop(H)
        if p in already:
            continue

        already.add(p)
        if p == G:
            return (c - 1) // L

        for q in out_link[p]:
            add_cost = cost[min(p, q), max(p, q)]
            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))

    return -1


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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
N,M,L = map(int,input().split())
load = [[]for i in range(N)]
for i in range(M):
    a,b,c = map(int,input().split())
    if c > L:
        continue
    load[a-1].append([b-1,c])
    load[b-1].append([a-1,c])
cost =[[float('inf')]*N for i in range(N)]
for i in range(N):
    queue = deque([i])
    cost[i][i] = 0
    while(queue):
        q = queue.popleft()
        gas = cost[i][q]
        for t,c in load[q]:
            if gas//L < (gas+c-1)//L :
                if (gas//L+1)*L+c < cost[i][t]:
                    cost[i][t] = (gas//L+1)*L+c
                    queue.append(t)
            else:
                if gas+c < cost[i][t]:
                    cost[i][t] = gas+c
                    queue.append(t)
Q = int(input())
for i in range(Q):
    s,t = map(int,input().split())
    ans = cost[s-1][t-1]
    if ans == float('inf'):
        print(-1)
    else:
        print((ans-1)//L)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools

import queue
from collections import deque



def main():
    node_num, edge_num, max_tank = map(int, input().split())
    data = [list(map(int, input().split())) for i in range(edge_num)]
    q_num = int(input())
    query = [list(map(int, input().split())) for i in range(q_num)]

    graph_data = defaultdict(set)
    dist_data = defaultdict(int)

    # ans_list = [[-1 for i in range(node_num + 1)] for j in range(node_num + 1)]
    for i in range(edge_num):
        a, b, c = data[i]
        graph_data[a].add(b)
        graph_data[b].add(a)
        dist_data[(a, b)] = c
        dist_data[(b, a)] = c

        # if c <= max_tank:
        #     ans_list[a][b] = (0, max_tank - c)
        #     ans_list[b][a] = (0, max_tank - c)

    # print(graph_data)
    # print(dist_data)

    ans_list = [[-1 for i in range(node_num + 1)] for j in range(node_num + 1)]
    for i in range(1, node_num + 1):
        # print('start', i)
        ans_list[i][i] = 0
        aaa = []

        for next_ele in graph_data[i]:
            dist = dist_data[(i, next_ele)]
            if dist <= max_tank:
                heapq.heappush(aaa, (0, - (max_tank - dist), next_ele))

        # print(aaa)

        while len(aaa):
            count, nokori, now_ele = heapq.heappop(aaa)
            if ans_list[i][now_ele] != -1:
                continue

            nokori = -1 * nokori
            ans_list[i][now_ele] = count

            for next_ele in graph_data[now_ele]:
                if ans_list[i][next_ele] != -1:
                    continue
                dist = dist_data[(now_ele, next_ele)]
                if dist > max_tank:
                    continue
                if nokori < dist:
                    heapq.heappush(aaa, (count + 1, - (max_tank - dist), next_ele))
                else:
                    heapq.heappush(aaa, (count, - (nokori - dist), next_ele))

            # print(aaa)



    # for i in range(1, node_num + 1):
    #     print(ans_list[i])

    for i in range(q_num):
        s, t = query[i]
        ans = ans_list[s][t]
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from collections import deque
from heapq import heapify, heappush as hpush, heappop as hpop
N, M, L = map(int, input().split())
X = [[] for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    X[a-1].append([b-1, c])
    X[b-1].append([a-1, c])

def dijkstra(n, E, i0=0):
    h = [[0, i0]]
    D = [-1] * n
    done = [0] * n
    D[i0] = 0
    
    while h:
        d, i = hpop(h)
        done[i] = 1
        for j, w in E[i]:
            nd = d + w
            if D[j] < 0 or D[j] >= nd:
                if done[j] == 0:
                    hpush(h, [nd, j])
                    D[j] = nd
    return D
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

Y = [[] for _ in range(N)]
for i in range(N):
    D1 = dijkstra(N, X, i)
    for j in range(N):
        if i == j: continue
        if 0 <= D1[j] <= L:
            Y[i].append(j)

# print("X =", X)
# print("Y =", Y)
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:
import sys
input = sys.stdin.readline
import heapq
from collections import defaultdict
def main():
    N, M, L = map( int, input().split())
    d = defaultdict( int)
    E = [[] for _ in range(N)]
    for _ in range(M):
        a, b, c = map( int, input().split())
        if c > L:
            continue
        a, b = a-1, b-1
        d[(a,b)] = c
        d[(b,a)] = c
        E[a].append(b)
        E[b].append(a)
    Q = int( input())
    G = [ tuple( map( int, input().split())) for _ in range(Q)]

    V = []
    for i in range(N):
        W = [-1]*N
        h = [(0,-L,i)]
        while h:
            t, g, v = heapq.heappop(h)
            if W[v] == -1:
                W[v] = t
                for w in E[v]:
                    if W[w] == -1:
                        if d[(v,w)] <= -g:
                            heapq.heappush(h, (t, g+d[(v,w)], w))
                        else:
                            heapq.heappush(h, (t+1, -L+d[(v,w)], w))
        V.append(W)

    for s, t in G:
        print( V[s-1][t-1])
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n,m,l = map(int,input().split())
road = [[] for _ in range(n)]
for _ in range(m):
  a,b,c = map(int,input().split())
  a -= 1
  b -= 1
  road[a].append([b,c])
  road[b].append([a,c])
cango = []
for i in range(n):
  tmp = [l+1 for _ in range(n)]
  tmp[i] = 0
  now = [[i,0]]
  while now:
    last = now
    now = []
    for x in last:
      for yz in road[x[0]]:
        y,z = yz
        if x[1] + z < tmp[y]:
          tmp[y] = x[1] + z
          now.append([y,tmp[y]])
  add = []
  for i in range(n):
    if tmp[i] == 0:
      add.append(0)
    elif tmp[i] <= l:
      add.append(1)
    else:
      add.append(1000)
  cango.append(add)
#print(cango)
for k in range(n):
  for i in range(n):
    for j in range(n):
      if cango[i][k] + cango[k][j] < cango[i][j]:
        cango[i][j] = cango[i][k] + cango[k][j]
#print(cango)
q = int(input())
for _ in range(q):
  s,t = map(int,input().split())
  ans = cango[s-1][t-1]-1
  if ans > 500:
    print(-1)
  else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input = sys.stdin.readline


n, m, l = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]
graph = [[] for i in range(n)]

for i in range(m):
    a, b, cost = info[i]
    if cost > l:
        continue
    a -= 1
    b -= 1
    graph[a].append((b, cost))
    graph[b].append((a, cost))

for i in range(n):
    graph[i] = sorted(graph[i], reverse = True)

def dfs(start):
    INF = float("inf")
    visited_t = [INF]*n # 回数, 残り燃料
    visited_l = [0]*n
    visited_t[start] = 0
    prev = -1
    q = deque([(start, prev)])
    while q:
        pos, prev = q.popleft()
        for next_pos, cost in graph[pos]:
            if prev == next_pos:
                continue
            tmp = cost + visited_l[pos]
            times = visited_t[pos]
            next_times = visited_t[next_pos]
            if tmp <= l:
                if next_times > times:
                    q.append((next_pos, pos))
                    visited_t[next_pos] = times
                    visited_l[next_pos] = tmp
                elif next_times == times:
                    if visited_l[next_pos] > tmp:
                        q.append((next_pos, pos))
                        visited_t[next_pos] = times
                        visited_l[next_pos] = tmp
                else:
                    continue
            else:
                tmp = cost
                if next_times > times + 1:
                    q.append((next_pos, pos))
                    visited_t[next_pos] = times + 1
                    visited_l[next_pos] = tmp
                elif next_times == times + 1:
                    if visited_l[next_pos] > tmp:
                        q.append((next_pos, pos))
                        visited_t[next_pos] = times + 1
                        visited_l[next_pos] = tmp
                else:
                    continue
    return visited_t

ans = [None]*n
for i in range(n):
    ans[i] = dfs(i)

INF = float("inf")
q = int(input())
query = [list(map(int, input().split())) for i in range(q)]
for i in range(q):
    a, b = query[i]
    a -= 1
    b -= 1
    tmp = ans[a][b]
    if tmp == INF:
        print(-1)
    else:
        print(tmp)