Hints — p63 Network Delay Time

Hint 1. This is single-source shortest path. The answer is the time for the slowest node to be reached — i.e., max(dist[v]) for all v. Return -1 if any node is unreachable.

Hint 2. All weights non-negative → Dijkstra is the right algorithm. (If any weight were negative, you’d need Bellman-Ford.)

Hint 3. Use heapq (min-heap). Push (dist, node). Pop, skip if popped dist > known dist[node] (stale entry). Else relax outgoing edges.

Hint 4. Python’s heapq doesn’t support decrease-key. You push a new entry every time you find a shorter path; older entries become “stale” and you skip them via if d > dist[u]: continue.

Hint 5. Time O((V+E) log V). After the loop, return -1 if any dist[v] == INF; else return max(dist[1:]). Watch the 1-indexed-vs-0-indexed nodes — LC 743 is 1-indexed.

If stuck: see solution.py.