Network Delay Time
MediumThe problem
A network has nodes numbered 1 to n. Each entry [u, v, w] in times is a one-way link: a signal sent from u reaches v after w time. A signal starts at node k. Return how long it takes until every node has received it, or -1 if some node never does.
- Example 1Input: times = [[2, 1, 1], [2, 3, 1], [3, 4, 1]], n = 4, k = 2Output: 2
Nodes 1 and 3 get it at time 1, and node 4 at time 2.
- Example 2Input: times = [[1, 2, 1]], n = 2, k = 1Output: 1
- Example 3Input: times = [[1, 2, 1]], n = 2, k = 2Output: -1
The link only goes from 1 to 2, so node 1 never gets the signal.
- 1 ≤ k ≤ n ≤ 100
- 1 ≤ len(times) ≤ 6,000
- 0 ≤ w ≤ 100
- There is at most one link from u to v
Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.
Try it here
Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.
Hints, one at a time
Nudge
The time for the signal to reach a node is the shortest weighted path from the source.
The idea
Dijkstra with a min-heap of (distance, node); answer is the largest shortest distance, or −1 if some node is unreachable.
Target: O(E log V) time
Go function shape
func networkDelayTime(times [][]int, n int, k int) intReference solution
Tested with go test. Try it yourself first, then compare.
// NetworkDelayTime: times[i] = {from, to, weight}, nodes are 1..n.
// The signal reaches everyone when it reaches the farthest node.
func NetworkDelayTime(times [][]int, n, k int) int {
graph := make([][]Edge, n+1)
for _, t := range times {
graph[t[0]] = append(graph[t[0]], Edge{t[1], t[2]})
}
dist := Dijkstra(graph, k)
worst := 0
for node := 1; node <= n; node++ {
if dist[node] == math.MaxInt {
return -1
}
worst = max(worst, dist[node])
}
return worst
}