leetExpert
Practice

Network Delay Time

Module 23 · Graphs

Problem

n network nodes labeled 1 to n. times[i] = [u, v, w] means a directed edge from u to v taking w time units to travel. A signal is sent from node k. Return the minimum time for the signal to reach ALL n nodes, or -1 if some node is unreachable. (LeetCode 743.)

Examples

Example 1

Inputtimes = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2Output2

Example 2

Inputtimes = [[1,2,1]], n = 2, k = 1Output1

Example 3

Inputtimes = [[1,2,1]], n = 2, k = 2Output-1

Constraints

1 ≤ k ≤ n ≤ 100, up to 6000 edges, positive weights.

Attempt it first

This is a direct, unmodified application of the Shortest Paths concept lesson's Dijkstra's algorithm — the exercise is recognizing the mapping: "minimum time for the signal to reach every node" is exactly "the maximum, over all nodes, of the shortest path distance from the source k" (the whole network is "done" only once its SLOWEST-to-reach node has been reached). Before opening anything, work out why taking the MAXIMUM (not the sum, not the minimum) of all the shortest distances is the right combination for this specific question.