## 题目描述：

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`.

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 `1 <= w <= 100`.

## Java代码：

``````class Solution {
class Pair implements Comparable<Pair>{
public int node;
public int time;
public Pair(int node, int time) {
this.node = node;
this.time = time;
}
public int compareTo(Pair p) {
return time - p.time;
}
}
public int networkDelayTime(int[][] times, int N, int K) {
PriorityQueue<Pair> queue = new PriorityQueue<>();
HashSet<Integer> visits = new HashSet<>();
HashMap<Integer, HashMap<Integer, Integer>> edges = new HashMap<>();
for (int[] t : times) {
HashMap<Integer, Integer> edge = edges.get(t[0]);
if (edge == null) {
edge = new HashMap<>();
edges.put(t[0], edge);
}
edge.put(t[1], t[2]);
}
int ans = 0;
while (!queue.isEmpty()) {
Pair front = queue.poll();
if (visits.contains(front.node)) continue;
ans = front.time;
HashMap<Integer, Integer> edge = edges.get(front.node);
if (edge == null) continue;
for (Map.Entry<Integer, Integer> entry : edge.entrySet()) {
}
}
return visits.size() < N ? -1 : ans;
}
}
``````

Pingbacks已关闭。