Problem: 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.

Submission attempts (in order):
from heapq import heapify, heappop, heappush, nlargest, nsmallest


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

G = [list(map(int, input().split())) for _ in range(M)]
Q = int(input())
Query = [list(map(int, input().split())) for _ in range(Q)]

nei_graph = [[float('inf')] * N for _ in range(N)]
for a, b, c in G:
    if c <= L:
        nei_graph[a - 1][b - 1] = c
        nei_graph[b - 1][a - 1] = c

for a, b, c in G:
    nei_graph[a - 1][a - 1] = 0


def dijkstra(start_node, end_node, nei_graph):
    visited = set()

    nodes = []
    heapify(nodes)
    heappush(nodes, [start_node, 0, L, 0])

    dist = [float('inf')] * N
    dist[start_node] = 0

    while nodes:
        node, d, remain, cnt = heappop(nodes)
        if node in visited:
            continue

        if node == end_node:
            return cnt

        visited.add(node)

        for i, edge in enumerate(nei_graph[node]):
            if edge == float('inf') or d + edge >= dist[i]:
                continue

            dist[i] = d + edge

            if remain < edge:
                new_remain = L - edge
                new_cnt = cnt + 1
            else:
                new_remain = remain - edge
                new_cnt = cnt

            heappush(nodes, [i, dist[i], new_remain, new_cnt])

        if end_node not in visited:
            return -1


for start, end in Query:
    print(dijkstra(start - 1, end - 1, nei_graph))

from heapq import heapify, heappop, heappush, nlargest, nsmallest


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

G = [list(map(int, input().split())) for _ in range(M)]
Q = int(input())
Query = [list(map(int, input().split())) for _ in range(Q)]

nei_graph = [[float('inf')] * N for _ in range(N)]
for a, b, c in G:
    
    if c <= L:
        nei_graph[a - 1][b - 1] = c
        nei_graph[b - 1][a - 1] = c

for a, b, c in G:
    nei_graph[a - 1][a - 1] = 0


def dijkstra(start_node, end_node, nei_graph):
    visited = set()

    nodes = []
    heapify(nodes)
    heappush(nodes, [start_node, 0, L, 0])

    dist = [float('inf')] * N
    dist[start_node] = 0

    while nodes:
        node, d, remain, cnt = heappop(nodes)
        if node in visited:
            continue

        
        if node == end_node:
            return cnt

        visited.add(node)

        for i, edge in enumerate(nei_graph[node]):
            if edge == float('inf') or d + edge > dist[i]:
                continue

            dist[i] = d + edge

            if remain < edge:
                new_remain = L - edge
                new_cnt = cnt + 1
            else:
                new_remain = remain - edge
                new_cnt = cnt

            heappush(nodes, [i, dist[i], new_remain, new_cnt])

    if end_node not in visited:
        return -1


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

from scipy.sparse.csgraph import floyd_warshall

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

G = [list(map(int, input().split())) for _ in range(M)]
Q = int(input())
Query = [list(map(int, input().split())) for _ in range(Q)]


nei_graph = [[0] * N for _ in range(N)]
for a, b, c in G:
    nei_graph[a - 1][b - 1] = c
    nei_graph[b - 1][a - 1] = c

# Warshall Floyd
nei_graph = floyd_warshall(nei_graph)

# 1 if distance is less than L
for i in range(N):
    for j in range(N):
        if nei_graph[i][j] <= L:
            nei_graph[i][j] = 1
        else:
            nei_graph[i][j] = 0

nei_graph = floyd_warshall(nei_graph)

for start, end in Query:
    if nei_graph[start - 1][end - 1] - 1 == float('inf'):
        print(-1)
    else:
        print(int(nei_graph[start - 1][end - 1] - 1))

Verdicts: Wrong Answer

Wrong Answer

Runtime Error

Accepted