BFS finds shortest paths only when every edge costs the same. With weighted edges you need Dijkstra: always expand the closest not-yet-settled node, which a heap hands you in O(log V).
You are given a network of n nodes labelled 1 .. n and a list times of directed edges [u, v, w] meaning a signal takes w time units to travel from u to v. A signal is sent from node k. Return the time it takes for all nodes to receive it. If some node can never receive the signal, return -1.
Examples
Input: times = [[2, 1, 1], [2, 3, 1], [3, 4, 1]], n = 4, k = 2
Output: 2
Explanation: node 4 is reached last, via 2 -> 3 -> 4
Input: times = [[1, 2, 1]], n = 2, k = 2
Output: -1
Constraints
1 <= n <= 100,1 <= k <= n,1 <= w <= 100- All edge weights are positive (Dijkstra requires this)
- Target: O(E log V) time
Goals
- Implement Dijkstra's algorithm with a min-heap of (distance, node) pairs
- Skip stale heap entries instead of trying to decrease keys
- Handle unreachable nodes in a shortest-path computation