What is the key pattern in the Reachable Nodes In Subdivided Graph problem?

The key pattern involves graph transformations combined with a heap-based priority queue to efficiently solve the shortest path problem within a given number of moves.

How do I handle edge subdivisions in this problem?

You must transform each edge into a chain of new nodes, creating additional edges between them. The number of new nodes depends on the 'cnti' value for each edge.

What is the best way to manage move limits in this problem?

Use a priority queue to efficiently track the shortest path to each node, ensuring that the number of moves does not exceed the given limit.

How does a priority queue help solve this problem?

A priority queue helps by efficiently finding the shortest available path from the starting node to other nodes, minimizing the number of moves used to reach each node.

Can I use BFS or DFS for this problem instead of a priority queue?

While BFS or DFS can be used in simpler cases, a priority queue is more efficient for handling the shortest path problem within a move constraint, especially with graph transformations.

#882

Hard

auto_awesome堆

LeetCode 题解工作台

细分图中的可到达节点

给你一个无向图（原始图），图中有 n 个节点，编号从 0 到 n - 1 。你决定将图中的每条边细分为一条节点链，每条边之间的新节点数各不相同。图用由边组成的二维数组 edges 表示，其中 edges[i] = [u i , v i , cnt i ] 表示原始图中节点 u i 和 v …

图堆（优先队列）最短路径

题目描述

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

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

要细分边 [ui, vi] ，需要将其替换为 (cnt_i + 1) 条新边，和 cnt_i 个新节点。新节点为 x₁, x₂, ..., x_{cnt_i} ，新边为 [u_i, x₁], [x₁, x₂], [x₂, x₃], ..., [x_{cnt_i-1}, x_{cnt_i}], [x_{cnt_i}, 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, 10⁴)
edges[i].length == 3
0 <= u_i < v_i < n
图中 不存在平行边
0 <= cnt_i <= 10⁴
0 <= maxMoves <= 10⁹
1 <= n <= 3000

lightbulb

解题思路

方法一：Dijkstra 算法

这道题本质是求从节点 $0$ 出发，最多经过 $maxMoves$ 步，可以到达多少个节点。单源最短路，且边权非负，我们可以考虑使用 Dijkstra 算法。

根据题目描述，节点 $u_i$ 到节点 $v_i$ 之间存在 $cnt_i$ 个新节点，那么节点 $u_i$ 到节点 $v_i$ 的距离为 $cnt_i + 1$ 。

我们举个简单的例子，以下节点 $1$ 和节点 $2$ 之间存在 $3$ 个新节点，那么节点 $1$ 到节点 $2$ 之间有 $4$ 条边，也即距离为 $4$ 。

1 -- o -- o -- o -- 2

因此，我们可以将原图中两点之间新节点的个数 $cnt_i$ 加 $1$ ，得到两点之间的距离。然后构建一个邻接表 $g$ ，用于存储每个节点的邻接节点以及到达邻接节点的距离。

接下来，我们使用 Dijkstra 算法求出从节点 $0$ 到原始图其余所有节点的最短距离，存储在数组 $dist$ 中。

然后，我们遍历数组 $dist$ ，统计其中小于等于 $maxMoves$ 的节点个数，也就是我们可以到达的节点数。不过，这并不是最终答案，我们还需要加上新节点中符合条件的节点个数。

我们可以发现，如果我们能在 $dist[u]$ 步到达节点 $u$ （其中 $dist[u] \leq maxMoves$ ），并且节点 $u$ 到节点 $v$ 之间有 $cnt$ 个新节点，那么我们能通过节点 $u$ 到达的新节点个数 $a=\min(cnt, maxMoves - dist[u])$ 。同理，我们能通过节点 $v$ 到达的新节点个数 $b=\min(cnt, maxMoves - dist[v])$ 。那么，我们能到达节点 $u$ 和节点 $v$ 之间的新节点个数为 $\min(cnt, a + b)$ 。

因此，我们再遍历所有的边，统计其中能到达的新节点个数，累加到答案中即可。

时间复杂度 $O(n + m \times \log n)$ ，其中 $m$ 和 $n$ 分别为边数和节点数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

class Solution:
    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:
        g = defaultdict(list)
        for u, v, cnt in edges:
            g[u].append((v, cnt + 1))
            g[v].append((u, cnt + 1))
        q = [(0, 0)]
        dist = [0] + [inf] * n
        while q:
            d, u = heappop(q)
            for v, cnt in g[u]:
                if (t := d + cnt) < dist[v]:
                    dist[v] = t
                    q.append((t, v))
        ans = sum(d <= maxMoves for d in dist)
        for u, v, cnt in edges:
            a = min(cnt, max(0, maxMoves - dist[u]))
            b = min(cnt, max(0, maxMoves - dist[v]))
            ans += min(cnt, a + b)
        return ans

speed

复杂度分析

指标	值
时间	O(E \log N)
空间	O(E)

psychology

面试官常问的追问

外企场景

question_mark
Understanding graph traversal techniques and shortest path algorithms is key to solving this problem effectively.
question_mark
Look for familiarity with heaps or priority queues, as they are essential for managing the node traversal efficiently.
question_mark
The ability to handle edge transformations and correctly manage graph subdivisions will signal strong problem-solving skills.

warning

常见陷阱

外企场景

error
Mismanaging edge subdivisions can lead to incorrect graph representations, making it hard to track reachable nodes.
error
Overcomplicating the algorithm or using inefficient traversal techniques can result in suboptimal performance, especially with larger graphs.
error
Failure to properly account for the move limit and correctly implementing the priority queue could lead to incorrect answers.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Increase the size of the graph and test how well the algorithm scales for larger input sizes.
arrow_right_alt
Add restrictions on the maximum number of new nodes that can be added for each edge, impacting the complexity of the transformation.
arrow_right_alt
Change the traversal rule to consider different starting nodes, altering the reachability calculation.

help

常见问题

外企场景

继续练习

#787 K 站中转内最便宜的航班 #743 网络延迟时间 #1368 使网格图至少有一条有效路径的最小代价