Compute ETA between two map nodes

Problem Statement

You are given a map represented as a directed graph where nodes are intersections and edges are road segments. Each edge has an associated travel_time representing the number of minutes required to traverse that segment. Given a starting node start_node, an ending node end_node, and an adjacency list graph where graph[u] contains a list of tuples (v, travel_time), implement a function to calculate the minimum travel time from start_node to end_node.

If the destination is unreachable, return -1.

Function Signature

def compute_eta(graph, start_node, end_node) -> int:

Constraints

• The graph contains N nodes (0 to N-1) and E edges.
• N is up to 10,000; E is up to 100,000.
• travel_time is always non-negative (>= 0).

Example 1

Input:

graph = {0: [(1, 5), (2, 1)], 1: [(3, 2)], 2: [(1, 1), (3, 7)], 3: []}
start_node = 0
end_node = 3

Output: 4 Explanation: The path 0 -> 2 -> 1 -> 3 has a total time of 1 + 1 + 2 = 4.

Edge Cases

• Start node equals end node (time should be 0).
• No path exists between nodes.
• Disconnected graph components.