Network Shortest Path

Problem

You are given a network of n cities connected by directed roads. Each road has a travel time (weight). Your task is to find the shortest travel time between a given source city and a destination city.

If no path exists between the source and destination, return -1.

Input Format

• n — number of cities (nodes), labeled 1 to n
• edges — a list of directed edges, where each edge is [u, v, w] meaning there is a road from city u to city v with travel time w
• src — the source city
• dst — the destination city

Output Format

Return an integer representing the shortest travel time from src to dst, or -1 if no path exists.

Examples

Example 1

Input: n = 5, edges = [[1,2,2],[1,3,4],[2,3,1],[2,4,7],[3,5,3],[4,5,1]], src = 1, dst = 5
Output: 6
Explanation: The shortest path is 1 → 2 → 3 → 5 with cost 2 + 1 + 3 = 6. The path 1 → 3 → 5 costs 4 + 3 = 7, and 1 → 2 → 4 → 5 costs 2 + 7 + 1 = 10.

Example 2

Input: n = 3, edges = [[1,2,5],[2,3,3]], src = 1, dst = 3
Output: 8
Explanation: There is only one path: 1 → 2 → 3 with cost 5 + 3 = 8.

Example 3

Input: n = 4, edges = [[1,2,1],[3,4,1]], src = 1, dst = 4
Output: -1
Explanation: There is no path connecting city 1 to city 4.

Approach Hints

• Think about: Which algorithm is designed specifically for shortest paths in weighted graphs with non-negative edge weights?
• Data structure: A min-heap (priority queue) can help you always process the city with the currently smallest known distance first.
• Key idea: Maintain a distances array initialized to infinity. Relax edges greedily by visiting nodes in order of their current shortest distance.
• Time Complexity: Aim for O((V + E) log V) where V is the number of nodes and E is the number of edges.
• Watch out for: Cycles — make sure you don't revisit already-settled nodes.