1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| class Solution {
public int networkDelayTime(int[][] times, int n, int k) {
Map<Integer, List<List<Integer>>> neighborMap = new HashMap<>();
for (int[] time : times) {
neighborMap.putIfAbsent(time[0], new ArrayList<>());
neighborMap.get(time[0]).add(new ArrayList<>(Arrays.asList(time[1], time[2])));
}
PriorityQueue<Pair<Integer, Integer>> q = new PriorityQueue<>((a, b) -> a.getValue() - b.getValue());
q.offer(new Pair<>(k, 0));
Set<Integer> visited = new HashSet<>();
int ans = -1;
while (!q.isEmpty()) {
Pair<Integer, Integer> currPair = q.poll();
if (visited.contains(currPair.getKey())) {
continue;
}
visited.add(currPair.getKey());
ans = Math.max(ans, currPair.getValue());
if (visited.size() == n) {
return ans;
}
if (neighborMap.containsKey(currPair.getKey())) {
for (List<Integer> neighbor : neighborMap.get(currPair.getKey())) {
q.offer(new Pair<>(neighbor.get(0), neighbor.get(1) + currPair.getValue()));
}
}
}
return -1;
}
}
|
Dijkstra’s Algo的应用. 只不过是PQ版本. 这个版本就是把neighors一股脑的都压进queue中. 由于PQ可以把最短的距离移动到头部, 我们每次去的地方都是按照距离start远近的order来的. 如果一个地方被visit过了, 后续PQ中还有表示这个地方的node, 我们就要跳过, 因为这说明其他地方到这个visit的地方距离更远, 否则我们就会先从它那里到这个被visit的地方了. 这点儿和用数组不太一样. 我们是一边走一边更新那个minDistance数组. 然后找下一个地点的时候, 我们遍历数组. 遍历的时候就会判断某个地点是否被visit过. 但是在PQ中, 及时我们在添加的时候判断某个地方有没有被visit过, PQ中还是无法避免同一个地方被添加多次. 因为可能在我们去这个地点前, 有多个其他地点距离start更近, 于是我们会先visit它们, 然而它们都能到达这个同一地点, 于是此时该同一地点就被添加了多次. 因此我们要做的是在node poll出来之后判断是否visit过, 如果有就continue, 没有就说明这个node装的信息就是到达该地点的最近距离.
时间复杂度: O(ElogN) E是edges的个数, N是nodes的个数. PQ size最大就是E, 比如start是中心, 其他nodes只和start相连. 那么push和pop就是O(logE). 由于E最大是n * (n - 1), 因此是O(logn^2)也就是O(2logn)也就是O(logn). 每个node, 我们只会走一遍.也就是我们会把所有的edge都走遍. 于是是O(ElogN)
空间复杂度: O(N^2) 我们用了map存每个node的neighbor信息, 一个node存E个neighors, 一共最多是n * (n - 1)个总edges, 因此是O(N^2), 用set存visit过的node一共是O(N)以及PQ存等待被visit的nodes, 一共是O(E)也就是O(N^2), 加在一起就是O(N^2).
