Network Delay Time

Description

There are N network nodes, labelled 1 to N.

Given times, a list of travel times as directed edges times[i] = (u, v, w), where u is the source node, v is the target node, and w is the time it takes for a signal to travel from source to target.

Now, we send a signal from a certain node K. How long will it take for all nodes to receive the signal? If it is impossible, return -1.

 

Example 1:

Input: times = [[2,1,1],[2,3,1],[3,4,1]], N = 4, K = 2
Output: 2

 

Note:

1. N will be in the range [1, 100].
2. K will be in the range [1, N].
3. The length of times will be in the range [1, 6000].
4. All edges times[i] = (u, v, w) will have 1 <= u, v <= N and 0 <= w <= 100.

Solution(javascript)

/** Dijkstra
 * @param {number[][]} times
 * @param {number} N
 * @param {number} K
 * @return {number}
 */
const networkDelayTime = function (times, N, K) {
  const distance = new Array(N).fill(Infinity)
    .reduce((acc, v, index) => {
      acc[index + 1] = Infinity
      return acc
    }, {})
  distance[K] = 0

  const adj = times.reduce((acc, [u, v, w]) => {
    acc[u] = acc[u] || []
    acc[u].push([v, w])
    return acc
  }, {})
  let count = N
  let max = 0
  while (count > 0) {
    const [minNode, minWeight] = Object.keys(distance).reduce((acc, node) => {
      const w = distance[node]
      if (w < acc[1]) {
        return [node, w]
      }
      return acc
    }, [0, Infinity])
    if (minWeight === Infinity) {
      return -1
    }
    max = Math.max(max, distance[minNode]);
    (adj[minNode] || []).forEach(([nextNode, nextWeight]) => {
      distance[nextNode] = Math.min(distance[nextNode], distance[minNode] + nextWeight)
    })
    delete distance[minNode] // 删掉已经处理过的节点
    count -= 1
  }
  return max
}