【Leetcode每日一题:882. 细分图中的可到达节点~~~单源最短路径Dijkstra算法】

题目描述

给你一个无向图（原始图），图中有 n 个节点，编号从 0 到 n - 1 。你决定将图中的每条边 细分 为一条节点链，每条边之间的新节点数各不相同。

图用由边组成的二维数组 edges 表示，其中 edges[i] = [ui, vi, cnti] 表示原始图中节点 ui 和 vi 之间存在一条边，cnti 是将边 细分 后的新节点总数。注意，cnti == 0 表示边不可细分。

要 细分 边 [ui, vi] ，需要将其替换为 (cnti + 1) 条新边，和 cnti 个新节点。新节点为 x1, x2, …, xcnti ，新边为 [ui, x1], [x1, x2], [x2, x3], …, [xcnti+1, xcnti], [xcnti, vi] 。

现在得到一个 新的细分图 ，请你计算从节点 0 出发，可以到达多少个节点？如果节点间距离是 maxMoves 或更少，则视为 可以到达 。

给你原始图和 maxMoves ，返回 新的细分图中从节点 0 出发 可到达的节点数 。

示例 1：

输入：edges = [[0,1,10],[0,2,1],[1,2,2]], maxMoves = 6, n = 3
输出：13
解释：边的细分情况如上图所示。
可以到达的节点已经用黄色标注出来。
示例 2：

输入：edges = [[0,1,4],[1,2,6],[0,2,8],[1,3,1]], maxMoves = 10, n = 4
输出：23
示例 3：

输入：edges = [[1,2,4],[1,4,5],[1,3,1],[2,3,4],[3,4,5]], maxMoves = 17, n = 5
输出：1
解释：节点 0 与图的其余部分没有连通，所以只有节点 0 可以到达。

提示：

0 <= edges.length <= min(n * (n - 1) / 2, 104)
edges[i].length == 3
0 <= ui < vi < n
图中 不存在平行边
0 <= cnti <= 104
0 <= maxMoves <= 109
1 <= n <= 3000

求解思路

1. 这是一道通过单元最短路径算法求解的问题
2. 先来使用集合赖存储节点->建图->最短路径算法求出从0位置开始，到其它位置的最短距离->遍历路径数组，如果遍历的点可以在 maxMoves 步内到达，那么加1，需要考虑一种特殊情况就是，0位置可以到u，0位置也可以到v，而且u也可以到v，那么我们就需要先计算出0到u还剩下多少步记为a，再计算0到v还剩下多少步标记为b，然后求a加b的和与u到v之间的最小值。循环遍历技术，返回最终的结果。

实现代码

class Solution {
    public int reachableNodes(int[][] edges, int maxMoves, int n) {
        //我们先来使用集合赖存储节点
        List<int[]>[] list=new ArrayList[n];
        for(int i=0;i<n;i++){
            list[i]=new ArrayList<>();
        }
        //接下来建图
        for(int[] edge:edges){
            int u=edge[0],v=edge[1],cnt=edge[2];
            list[u].add(new int[]{v,cnt+1});
            list[v].add(new int[]{u,cnt+1});
        }
        //最短路径算法
        int[] dist=new int[n];
        Arrays.fill(dist,Integer.MAX_VALUE);
        dist[0]=0;
        Queue<int[]> queue=new PriorityQueue<>((a,b)->a[1]-b[1]);
        queue.add(new int[]{0,0});
        while(!queue.isEmpty()){
            int[] temp=queue.poll();
            //条件特判
            int x = temp[0], d = temp[1];
            if (d > dist[x]) continue;
            // 从x出发还有哪些点与它相连
            for(int i=0;i<list[x].size();i++){
                int y=list[x].get(i)[0];
                int newD=list[x].get(i)[1]+d;
                if(newD<dist[y]){
                    dist[y]=newD;
                    queue.add(new int[]{y,newD});
                }
            }
        }
        //记录结果
        int ans = 0;
        //这个点可以在 maxMoves 步内到达
        for (int d : dist){
            if (d <= maxMoves) ans++;
        }
        for (int[] e : edges) {
            int u = e[0], v = e[1], cnt = e[2];
            //0 到 u 剩下多少步
            int a = Math.max(maxMoves - dist[u], 0);
            //同理， 0 到 v 节点剩下多少步
            int b = Math.max(maxMoves - dist[v], 0);
            //a和b结果的累加，如果大于整个节点数，就取cnt即可，否则，取a+b结果的值
            ans += Math.min(a + b, cnt); // 这条边上可以到达的节点数
        }
        return ans;
    }
}
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
41
42
43
44
45
46
47
48
49
50
51
52

运行结果