Review

  • 743 Network Delay Time

743 Network Delay Time

GeeksForGeesk 上是无向图，然后直接用那种方法做的，结果就错了，后来看了看dijkstra有向图和无向图都可以处理。翻开了算法导论，重新看了下，发现用优先级队列做比较好。

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
31
32
33
34
35
36
37
38
39
40
public int networkDelayTime(int[][] times, int N, int K) {
        Map<Integer,List<Integer>>map=new HashMap<>();
        int [][]adj = new int[N+1][N+1];
        for(int[]time:times){
            adj[time[0]][time[1]]=time[2];
            if(!map.containsKey(time[0])){
                map.put(time[0],new ArrayList<>());
            }
            map.get(time[0]).add(time[1]);
        }
        int []dist = new int[N+1];
        Arrays.fill(dist,Integer.MAX_VALUE);
        dist[K]=0;
        PriorityQueue<Integer>pq = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return dist[o1]-dist[o2];
            }
        });
        pq.offer(K);
        int ans = 0;
        while(!pq.isEmpty()){
            int u = pq.poll();
            ans = Math.max(ans,dist[u]);
            List<Integer>neighbors = map.getOrDefault(u,new ArrayList<>());
            for(int neighbor:neighbors){
                if(dist[neighbor]>dist[u]+adj[u][neighbor]){
                    pq.remove(neighbor);
                    dist[neighbor] = dist[u]+adj[u][neighbor];
                    pq.offer(neighbor);
                }
            }
        }
        for(int i=1;i<=N;++i){
            ans = Math.max(ans,dist[i]);
        }
        return ans== Integer.MAX_VALUE?-1:ans;
    }