【LeetCode】882. 细分图中的可到达节点

题目描述

给你一个无向图（原始图），图中有 n 个节点，编号从 0 到 n - 1 。你决定将图中的每条边 细分 为一条节点链，每条边之间的新节点数各不相同。
图用由边组成的二维数组 edges 表示，其中 edges[i] = [u_i, v_i, cnt_i] 表示原始图中节点 u_i 和 v_i 之间存在一条边，cnt_i 是将边 细分 后的新节点总数。注意，cnt_i == 0 表示边不可细分。
要 细分 边 [u_i, v_i] ，需要将其替换为 (cnt_i + 1) 条新边，和 cnt_i 个新节点。新节点为 x₁, x₂, …, x_cnti ，新边为 [u_i, x₁], [x₁, x₂], [x₂, x₃], …, [x_cnti+1, x_cnti], [x_cnti, v_i] 。
现在得到一个 新的细分图 ，请你计算从节点 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 <= u_i < v_i < n
图中 不存在平行边
0 <= cnt_i <= 10⁴
0 <= maxMoves <= 10⁹
1 <= n <= 3000

方法一：Dijkstra

class Solution {
public:
    int encode(int u, int v, int n){
        return u * n + v;
    }
    int reachableNodes(vector<vector<int>>& edges, int maxMoves, int n) {
        // 将输入的edges转换成邻接表adList
        vector<vector<pair<int, int>>> adList(n);
        for (auto &edge : edges) {
            int u = edge[0], v = edge[1], nodes = edge[2];
            adList[u].emplace_back(v, nodes);
            adList[v].emplace_back(u, nodes);
        }

        unordered_map<int, int> used;
        //unordered_set:无序 set 容器
        unordered_set<int> visited;
        int res = 0; // 记录可达节点数

        // priority_queue 优先级队列,优先级最大的出队
        // priority_queue
        // Functional默认是less 降序，greater 升序队列
        // pair的比较，先比较第一个元素，第一个相等比较第二个
        // 因此这里的意思是，一个元素为pair的升序队列
        // 每次取出的都是值最小的键值对
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        // pair
        // 表示节点0到起点0的step = 0
        pq.emplace(0, 0); // emplace原地构造一个元素并插入队列

        // 当 pq 不为空 且 step <= maxMoves
        while(!pq.empty() && pq.top().first <= maxMoves){
            auto [step, u] = pq.top();
            pq.pop();
            // u 已经被访问过
            if(visited.count(u)){
                continue;
            }
            // u 没有被访问过
            visited.emplace(u);
            // 只考虑原始节点是不是可达节点
            // 不考虑细分节点是不是可达节点
            res ++; // 则u是可达节点

            // 遍历u的邻接节点，加入pq队列
            for (auto [v, nodes] : adList[u]){
                // nodes 是 u 和 v 之间的细分节点
                // step 指的是起点0到当前节点的距离
                // 如果noded + step + 1 < maxMoves ，说明是可达节点
                // !visited.count(v)，说明未被访问
                // 把节点 0 -> v 这一条路线加入考虑
                // 也就是说可以通过这个路线考虑多包含一个节点
                if(nodes + step + 1 <= maxMoves && !visited.count(v)){
                    pq.emplace(nodes + step + 1, v);
                    // 更新了step = nodes + step + 1 
                }
                // 记录各条边上的细分节点的可达情况
                // used key: u -> v 的边
                // 比如节点0 到其他节点的边标记为 0*3+1=1, 0*3+2=2
                // value: 这条边上的细分节点数
                // 也就是说 used存储了u->v 的细分节点数
                used[encode(u, v, n)] = min(nodes, maxMoves - step);
            }
        }

        for (auto &edge : edges){
            int u = edge[0], v = edge[1], nodes = edge[2];
            // 比较 u->v 和 v->u 的可达节点数
            // 因为这两条路线只可能计算一次，因此选择最小的
            res += min(nodes, used[encode(u, v, n)] + used[encode(v, u, n)]);
        }
        return res;
    }
};
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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

心得

• 看到是难度是 困难 + 图，直接看题解了。

方法：Dijsktra算法

• 当图中只存在原始节点而不存在细分节点时，此题可以用 Dijkstra算法 解决： 将输入的 edges 转换成邻接表 adList，维护一个小顶堆 pq 可以依次计算出图中的起点到各个点最短路径，从而计算出可到达节点。 pq 中的元素为节点以及起点到该节点的路径长度，并以路径长度为比较元素。每次取出未访问过的节点中的路径最短的节点，并访问其邻接点，若路径长度仍小于等于 maxMoves 且未访问过，可将其放入 pq，直到 pq 为空 或 pq 最短路径大于 maxMoves 。
• 但当每条边都加入细分节点后，需要考虑细分节点是否可达。用一个哈希表 used 记录各条边上的细分节点的可达情况，键为二元点对 （u，v），表示从点 u 到点 v 的边，值为这条边上的可达细分节点数。注意在计算细分节点时，考虑单向的情况，分别计算 used[(u，v)] 和 used[(v，u)]，并且这两个值不一定相等。计算 used 时，是要在访问路径最短的节点 u 的邻接节点 v 时计算。如果邻接节点的路径长度小于等于 maxMoves ，说明这条边上的细分节点都可达，否则只有一部分可达，并且这部分细分节点是靠近节点 u 的。
• 计算总的可达节点时，需要加上细分节点的部分。但是每条边上的细分节点可能会被计算过两次，即 used[(u，v)] 和 used[(v，u)] ，他们分别是靠近 u 开始计算的和靠近 v 开始计算的，需要去掉这两部分重叠的细分节点。

参考资料

1. Dijikstra算法详解
2. priority_queue用法详解