0882. Reachable Nodes In Subdivided Graph ======================================================================================================================== 题目信息 -------- :题号: 0882 :难度: Hard :主题: 加权图、边细分、可达节点计数 :原题: `LeetCode 0882 `_ :重点: 每条原边被替换为包含 cnt 个全新节点的链,经过每个小边消耗一步;从节点 0 出发统计步数上限内可达的原节点和新节点 题目重述 -------- 给定一个有 ``n`` 个原节点的无向图,节点编号为 ``0`` 至 ``n - 1``。每条边 ``[u, v, cnt]`` 会被细分:删除原来的 ``u-v`` 边,在两端之间插入 ``cnt`` 个只属于这条边的新节点,形成一条包含 ``cnt + 1`` 条小边的链。 从原节点 ``0`` 出发,每经过一条小边消耗一步,最多可以走 ``maxMoves`` 步。可以选择任意路线,节点只要存在一条不超过步数上限的路径即可视为可达。请返回细分后图中所有可达节点的总数,包括原节点和每条边上新增的节点。 ``1 <= n <= 3000``,边数不超过 ``10^4``;每条边满足 ``0 <= u < v < n``、``0 <= cnt <= 10^4``,任意原节点对之间至多一条边,``0 <= maxMoves <= 10^9``。 自建示例 -------- 只能走到细分边的一部分: .. code-block:: text 输入:edges = [[0,1,3]], maxMoves = 2, n = 2 输出:3 解释:原边被三个新节点细分为 0-a-b-c-1。从节点 0 最多走两步,可到达 0、a、b,共三个节点,无法到达 c 和原节点 1。 没有移动步数且图只有起点: .. code-block:: text 输入:edges = [], maxMoves = 0, n = 1 输出:1 解释:步数上限为 0 时不能经过任何边,但起点节点 0 本身已经可达。图中没有其他原节点或细分节点,因此总数为 1。