ETA Between Two Nodes in a Semantic Map Graph

Problem You are given a directed (or undirected) graph representing a semantic map. Each node is a semantic location, and each edge represents a traversable connection. Each edge has a non-negative travel time cost w (e.g., seconds). Given a source node s and a target node t, compute the ETA (Estimated Time of Arrival) from s to t, defined as the minimum possible sum of edge travel times along any path from s to t. If t is not reachable from s, output -1. Input (stdin) First line: two integers n m for number of nodes and edges (nodes are 0..n-1). Next m lines: u v w describing a directed edge u -> v with travel time w (w >= 0). Last line: s t. Output (stdout) Print the minimum ETA; print -1 if unreachable. Constraints 1 <= n <= 2*10^5 0 <= m <= 3*10^5 0 <= w <= 10^9 Example Input: 5 6 0 1 2 0 2 5 1 2 1 1 3 2 2 3 1 3 4 3 0 4 Output: 7 Example Input 5 6 0 1 2 0 2 5 1 2 1 1 3 2 2 3 1 3 4 3 0 4 Output 7