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。

自建示例

只能走到细分边的一部分:

输入:edges = [[0,1,3]], maxMoves = 2, n = 2
输出:3
解释:原边被三个新节点细分为 0-a-b-c-1。从节点 0 最多走两步,可到达 0、a、b,共三个节点,无法到达 c 和原节点 1。

没有移动步数且图只有起点:

输入:edges = [], maxMoves = 0, n = 1
输出:1
解释:步数上限为 0 时不能经过任何边,但起点节点 0 本身已经可达。图中没有其他原节点或细分节点,因此总数为 1。