743. Network latency

Title Description

You are given a network of n nodes, labeled from 1 to n. You are also given times, a list of travel times as directed edges times[i] = (ui, vi, wi), where ui is the source node, vi is the target node, and wi is the time it takes for a signal to travel from source to target.

We will send a signal from a given node k. Return the time it takes for all the n nodes to receive the signal. If it is impossible for all the n nodes to receive the signal, return -1.

 

Example 1:

,1,1 Input: times = [[2], [2,3,1], [3,4,1]], n = 4, k = 2 Output: 2 Example 2: Input: Example 3: Input: times = [1,2,1]], n = 2, k = 2 Output: 1 Example 3: Input: times = [1,2,1]], n = 2, k = 2 Output: -1Copy the code

 

Constraints:

  • 1 <= k <= n <= 100
  • 1 <= times.length <= 6000
  • times[i].length == 3
  • 1 <= ui, vi <= n
  • ui ! = vi
  • 0 <= wi <= 100
  • All the pairs (ui, vi) are unique. (i.e., no multiple edges.)

Topic describes

There are n network nodes, labeled 1 through N.

I’ll give you a list times, which is how long it takes for a signal to pass through a directed edge. Times [I] = (UI, vi, wi), where UI is the source node, vi is the target node, and WI is the time when a signal is transmitted from the source node to the target node.

Now, we send a signal from some node K. How long will it take for all nodes to receive signals? If all nodes cannot receive signals, -1 is returned.

 

Example 1:

Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2 Output: 2 Example 2: Input: times = [[1,2,1]], n = 2, k = 1 Output: 1 Example 3: Input: Times = [1,2,1]], n = 2, k = 2Copy the code

Tip:

  • 1 <= k <= n <= 100
  • 1 <= times.length <= 6000
  • times[i].length == 3
  • 1 <= ui, vi <= n
  • ui ! = vi
  • 0 <= wi <= 100
  • All (UI, vi) pairs are different (i.e., without repeating edges)

Their thinking

Dijkstra algorithm

  • Dijkstra’s algorithm is generally expressed in two ways, one is permanent and temporary labeling, the other is OPEN,  CLOSE table, here are permanent and temporary label. Note that this algorithm requires no negative edge weights in the graph.
  • Find the shortest path between node Kk and all other points, where the maximum is the answer.
  • If there is an unreachable point from kk, -1−1 is returned.

Code (today’s still a little bit did not understand, I borrowed the official big, hee hee)

var networkDelayTime = function(times, n, k) { const INF = Number.MAX_SAFE_INTEGER; const g = new Array(n).fill(INF).map(() => new Array(n).fill(INF)); for (const t of times) { const x = t[0] - 1, y = t[1] - 1; g[x][y] = t[2]; } const dist = new Array(n).fill(INF); dist[k - 1] = 0; const used = new Array(n).fill(false); for (let i = 0; i < n; ++i) { let x = -1; for (let y = 0; y < n; ++y) { if (! used[y] && (x === -1 || dist[y] < dist[x])) { x = y; } } used[x] = true; for (let y = 0; y < n; ++y) { dist[y] = Math.min(dist[y], dist[x] + g[x][y]); } } let ans = Math.max(... dist); return ans === INF ? -1 : ans; };Copy the code