Compute ETA between two map nodes

Problem

You are given a semantic road map represented as a weighted graph. Each node is an intersection/waypoint, and each edge represents a drivable road segment with an associated travel time (in seconds).

Given two nodes start and end, compute the ETA (minimum travel time) from start to end.

Clarifications to confirm with interviewer

• Is the graph directed (one-way roads) or undirected ? (Assume directed unless stated otherwise.)
• Are travel times non-negative ? (Assume yes.)
• What should be returned if end is unreachable from start ? (Return -1 .)
• Are there multiple queries or a single query? (Assume a single query unless specified.)

Input / Output (one possible interface)

• Input:
  • n : number of nodes labeled 0..n-1
  • edges : list of roads, each as (u, v, t) meaning an edge from u to v taking t seconds
  • start , end : node IDs
• Output:
  • Minimum travel time from start to end , or -1 if unreachable

Constraints

• 1 <= n <= 2e5
• 0 <= |edges| <= 5e5
• 0 <= t <= 1e9 (non-negative)

Example

• n = 5
• edges = [(0,1,5),(1,2,2),(0,2,20),(2,3,1),(3,4,3)]
• start = 0, end = 4

Shortest ETA path is 0->1->2->3->4 with total time 5+2+1+3 = 11, so return 11.