[LeetCode] 743. Network Delay Time

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:

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

网络延迟时间。

有 N 个网络节点，标记为 1 到 N。

给定一个列表 times，表示信号经过有向边的传递时间。 times[i] = (u, v, w)，其中 u 是源节点，v 是目标节点， w 是一个信号从源节点传递到目标节点的时间。

现在，我们从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/network-delay-time
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题意是从节点K出发，问需要多久才能让所有节点都接收到信号。很显然这是个图论graph的题，那么我们首先要做的就是把图建立起来。这里因为input里给了三个参数，u，v和w，表示的是每条边的起点，终点和权重。所以我这里创建一个hashmap<u, hashmap<v, weight>>。同时既然是问需要多少时间才能让信号传给所有节点，那么这里我们自然会选择代价最小的结果。这一题也是涉及到了 Dijkstra 的概念，有权图的单源最短路径问题。所以我们应该是需要一个priority queue来存放每两个点之间的weight的。最后我们需要一个boolean数组记录每个节点是否访问过。把图创建好之后，我们把起始点K和他的权重0放入pq（因为从K点出发到K点，是没有花费的）。

当pq不为空的时候，我们从pq中poll一个元素出来，并把它标记为visited，此时我们还需要用for loop遍历这个节点所有的邻居节点next，并把走到下一个节点next的代价累加到当前的代价curDistance上，再放回pq继续循环。停止循环的条件是pq为空或者所有节点都遍历完了。此时判断节点是否都遍历到了，若是则返回代价res；否则返回-1，说明有节点是怎么样都无法从K出发访问到的。

时间O(V + E)

空间O(V + E)

Java实现

 1 class Solution {
 2     public int networkDelayTime(int[][] times, int N, int K) {
 3         HashMap<Integer, HashMap<Integer, Integer>> g = new HashMap<>();
 4         // times中的数组 a, a[0]代表源，a[1]代表目标，a[2]代表权值，单向的
 5         for (int[] t : times) {
 6             g.putIfAbsent(t[0], new HashMap<>());
 7             g.get(t[0]).put(t[1], t[2]);
 8         }
 9 
10         // 距离, 目标
11         PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
12         pq.offer(new int[] { 0, K });
13         boolean[] visited = new boolean[N + 1];
14         int res = 0;
15         while (!pq.isEmpty()) {
16             int[] cur = pq.poll();
17             int curDistance = cur[0];
18             int curNode = cur[1];
19             if (visited[curNode] == true) {
20                 continue;
21             }
22             visited[curNode] = true;
23             res = curDistance;
24             N--;
25             if (N == 0) {
26                 break;
27             }
28             if (g.containsKey(curNode)) {
29                 for (int next : g.get(curNode).keySet()) {
30                     pq.offer(new int[] { curDistance + g.get(curNode).get(next), next });
31                 }
32             }
33         }
34         return N == 0 ? res : -1;
35     }
36 }

LeetCode 题目总结