细分图中的可到达节点

标签: 图 最短路 堆（优先队列）

难度: Hard

给你一个无向图（原始图），图中有 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

Submission

运行时间: 117 ms

内存: 21.6 MB

def dijkstra(g, start):
    dist = [inf] * len(g)
    dist[start] = 0
    h = [(0, start)]
    while h:
        d, x = heappop(h)
        if d > dist[x]:
            continue
        for y, wt in g[x]:
            new_d = dist[x] + wt
            if new_d < dist[y]:
                dist[y] = new_d
                heappush(h, (new_d, y))
    return dist
class Solution:
    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:
        g=[[] for _ in range(n)]
        for u,v,c in edges:
            g[u].append((v,c+1))
            g[v].append((u,c+1))
        dis=dijkstra(g,0)
        res=0
        for i in range(n):
            if dis[i]<=maxMoves:
                res+=1
        for u,v,c in edges:
            if min(dis[u],dis[v])+c<=maxMoves:
                res+=c
            else:
                t=0
                if dis[u]<maxMoves:
                    t+=maxMoves-dis[u]
                if dis[v]<maxMoves:
                    t+=maxMoves-dis[v]
                if t>=c:
                    res+=c
                else:
                    res+=t
        return res

Explain

本题解采用 Dijkstra 算法来计算从起始节点0到其他所有节点的最短路径。首先构建图，将原图的每条边细分成新的节点和边，然后使用 Dijkstra 算法找出从节点0到任何其他节点的最短距离。对每个节点，如果它可以在 maxMoves 或更少的移动中到达，则增加可到达的节点数。对于每条边，根据两端节点的最短路径和中间节点的数量，计算额外可以访问的中间节点数。综合考虑这些因素，最终得出所有可以访问的节点总数。

时间复杂度: O(E log V)

空间复杂度: O(V + E)

def dijkstra(g, start):
    # 初始化距离数组，所有节点距离为无穷大
    dist = [inf] * len(g)
    dist[start] = 0
    # 使用最小堆优化的优先队列
    h = [(0, start)]
    while h:
        d, x = heappop(h)
        if d > dist[x]:
            continue
        # 更新邻接节点的最短距离
        for y, wt in g[x]:
            new_d = dist[x] + wt
            if new_d < dist[y]:
                dist[y] = new_d
                heappush(h, (new_d, y))
    return dist
class Solution:
    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:
        # 构建图的邻接表
        g=[[] for _ in range(n)]
        for u,v,c in edges:
            g[u].append((v,c+1))
            g[v].append((u,c+1))
        # 获取从节点0到其他所有节点的最短路径
        dis=dijkstra(g,0)
        res=0
        # 计算可以直接到达的节点数量
        for i in range(n):
            if dis[i]<=maxMoves:
                res+=1
        # 计算通过边细分可到达的额外节点数
        for u,v,c in edges:
            if min(dis[u],dis[v])+c<=maxMoves:
                res+=c
            else:
                t=0
                if dis[u]<maxMoves:
                    t+=maxMoves-dis[u]
                if dis[v]<maxMoves:
                    t+=maxMoves-dis[v]
                if t>=c:
                    res+=c
                else:
                    res+=t
        return res

Explore

在题解中，细分节点并没有作为独立的节点显式地加入到图的数据结构中。相反，通过增加原有边的权重来间接表示这些细分节点。例如，如果原边的长度是c，将其细分为c+1条单位长度的边，实际上是通过设置边的权重为c+1来处理。这样做的好处是简化了图的表示和路径计算，避免了复杂的图结构操作，但牺牲了对细分节点个数的直接控制。

在题解中，每条边由两个节点u和v以及中间的c个额外节点组成。因此，从u到v的总距离为c+1（包括起始点和终点）。在构建图时，原始边u到v的距离用c+1来表示，意味着从u到v需要走过c个中间节点加上v节点本身。这种表示方法简化了计算，因为它直接使用边的总长度而不是单独考虑每个细分节点。

在Dijkstra算法中，最小堆（或优先队列）用于高效地选择下一个要处理的节点，即具有当前最小估计距离的节点。每次从堆中取出一个节点，这个节点是未被最终确定距离的节点中距离起点最近的。使用最小堆来存储和更新节点距离可以确保每次都能以对数时间复杂度获取最小距离节点，显著提高算法的效率，特别是在边和节点数量较多的图中。

在计算额外节点时，考虑的是两个节点u和v之间的边，以及这条边上的c个细分节点。首先检查从起点到u和v的最短路径之和加上细分节点数c是否小于等于maxMoves。如果是，可以到达u和v之间的所有c个细分节点。如果不是，需要计算从u和v出发，在移动限制内可以额外到达多少细分节点。具体来说，如果u或v中任一节点的最短路径加上其到边的另一端的距离小于maxMoves，那么可以根据剩余的移动额度计算可以到达的细分节点数量。这个计算方式确保了在移动限制内最大化访问边细分的节点数。