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 出发，有多少个节点可达，其中如果从节点 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^4)
  • edges[i].length == 3
  • 0 <= ui < vi < n
  • 图中没有重复的边
  • 0 <= cnti <= 10^4
  • 0 <= maxMoves <= 10^9
  • 1 <= n <= 3000

解题思路

这道题的核心是理解图的细分过程和最短路径计算。

思路分析：

  1. 图的建模：原始图的每条边 [u, v, cnt] 在细分后变成了 cnt+1 条边，相当于从 u 到 v 需要 cnt+1 步。

  2. 两部分节点：

    • 原始节点（0 到 n-1）
    • 新增的细分节点

  3. 解题策略：

    • 使用 Dijkstra 算法计算从节点 0 到所有原始节点的最短距离
    • 统计可达的原始节点数量
    • 对于每条边上的细分节点，计算从两端能够到达的节点数量

  4. 具体实现：

    • 构建邻接表，边权重为 cnt+1
    • 用 Dijkstra 求最短路径
    • 对每条边，计算从两端点出发能到达该边上多少个细分节点
    • 避免重复计数

关键点：

  • 细分节点的计算需要考虑从两端点出发的剩余步数
  • 使用优先队列优化 Dijkstra 算法
  • 正确处理边界情况和重复计数

代码实现

class Solution {
public:
    int reachableNodes(vector<vector<int>>& edges, int maxMoves, int n) {
        vector<vector<pair<int, int>>> graph(n);
        for (auto& edge : edges) {
            int u = edge[0], v = edge[1], cnt = edge[2];
            graph[u].push_back({v, cnt + 1});
            graph[v].push_back({u, cnt + 1});
        }
        
        vector<int> dist(n, INT_MAX);
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        
        dist[0] = 0;
        pq.push({0, 0});
        
        while (!pq.empty()) {
            auto [d, u] = pq.top();
            pq.pop();
            
            if (d > dist[u]) continue;
            
            for (auto [v, w] : graph[u]) {
                if (dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    pq.push({dist[v], v});
                }
            }
        }
        
        int result = 0;
        for (int i = 0; i < n; i++) {
            if (dist[i] <= maxMoves) {
                result++;
            }
        }
        
        for (auto& edge : edges) {
            int u = edge[0], v = edge[1], cnt = edge[2];
            int fromU = max(0, maxMoves - dist[u]);
            int fromV = max(0, maxMoves - dist[v]);
            result += min(cnt, fromU + fromV);
        }
        
        return result;
    }
};

class Solution:
    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:
        import heapq
        
        graph = [[] for _ in range(n)]
        for u, v, cnt in edges:
            graph[u].append((v, cnt + 1))
            graph[v].append((u, cnt + 1))
        
        dist = [float('inf')] * n
        dist[0] = 0
        pq = [(0, 0)]
        
        while pq:
            d, u = heapq.heappop(pq)
            if d > dist[u]:
                continue
            
            for v, w in graph[u]:
                if dist[u] + w < dist[v]:
                    dist[v] = dist[u] + w
                    heapq.heappush(pq, (dist[v], v))
        
        result = 0
        for i in range(n):
            if dist[i] <= maxMoves:
                result += 1
        
        for u, v, cnt in edges:
            from_u = max(0, maxMoves - dist[u])
            from_v = max(0, maxMoves - dist[v])
            result += min(cnt, from_u + from_v)
        
        return result

public class Solution {
    public int ReachableNodes(int[][] edges, int maxMoves, int n) {
        var graph = new List<(int, int)>[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new List<(int, int)>();
        }
        
        foreach (var edge in edges) {
            int u = edge[0], v = edge[1], cnt = edge[2];
            graph[u].Add((v, cnt + 1));
            graph[v].Add((u, cnt + 1));
        }
        
        var dist = new int[n];
        Array.Fill(dist, int.MaxValue);
        var pq = new SortedSet<(int, int)>();
        
        dist[0] = 0;
        pq.Add((0, 0));
        
        while (pq.Count > 0) {
            var (d, u) = pq.Min;
            pq.Remove(pq.Min);
            
            if (d > dist[u]) continue;
            
            foreach (var (v, w) in graph[u]) {
                if (dist[u] + w < dist[v]) {
                    pq.Remove((dist[v], v));
                    dist[v] = dist[u] + w;
                    pq.Add((dist[v], v));
                }
            }
        }
        
        int result = 0;
        for (int i = 0; i < n; i++) {
            if (dist[i] <= maxMoves) {
                result++;
            }
        }
        
        foreach (var edge in edges) {
            int u = edge[0], v = edge[1], cnt = edge[2];
            int fromU = Math.Max(0, maxMoves - dist[u]);
            int fromV = Math.Max(0, maxMoves - dist[v]);
            result += Math.Min(cnt, fromU + fromV);
        }
        
        return result;
    }
}

var reachableNodes = function(edges, maxMoves, n) {
    const graph = Array(n).fill().map(() => []);
    for (const [u, v, cnt] of edges) {
        graph[u].push([v, cnt + 1]);
        graph[v].push([u, cnt + 1]);
    }
    
    const dist = Array(n).fill(Infinity);
    const pq = [[0, 0]];
    dist[0] = 0;
    
    while (pq.length > 0) {
        pq.sort((a, b) => a[0] - b[0]);
        const [d, u] = pq.shift();
        
        if (d > dist[u]) continue;
        
        for (const [v, w] of graph[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push([dist[v], v]);
            }
        }
    }
    
    let result = 0;
    for (let i = 0; i < n; i++) {
        if (dist[i] <= maxMoves) {
            result++;
        }
    }
    
    for (const [u, v, cnt] of edges) {
        const fromU = Math.max(0, maxMoves - dist[u]);
        const fromV = Math.max(0, maxMoves - dist[v]);
        result += Math.min(cnt, fromU + fromV);
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O((n + m) log n)
空间复杂度O(n + m)

其中 n 为节点数，m 为边数。时间复杂度主要来自 Dijkstra 算法，空间复杂度用于存储图的邻接表和距离数组。

相关题目