3543. 最大权重的K边路径

Medium

题目描述

给你一个整数 n 和一个有向无环图 (DAG)，该图有 n 个节点，标号从 0 到 n - 1。图用二维数组 edges 表示，其中 edges[i] = [ui, vi, wi] 表示从节点 ui 到节点 vi 有一条权重为 wi 的有向边。

同时给你两个整数 k 和 t。

你的任务是确定图中任意路径的边权重的最大可能总和，使得：

路径恰好包含 k 条边。
路径中边权重的总和严格小于 t。

返回满足条件的路径的最大可能权重总和。如果不存在这样的路径，返回 -1。

示例 1：

输入：n = 3, edges = [[0,1,1],[1,2,2]], k = 2, t = 4
输出：3
解释：
唯一有 k = 2 条边的路径是 0 -> 1 -> 2，权重为 1 + 2 = 3 < t。
因此，小于 t 的最大可能权重总和是 3。

示例 2：

输入：n = 3, edges = [[0,1,2],[0,2,3]], k = 1, t = 3
输出：2
解释：
有两条 k = 1 条边的路径：
- 0 -> 1 权重为 2 < t。
- 0 -> 2 权重为 3 = t，不严格小于 t。
因此，小于 t 的最大可能权重总和是 2。

示例 3：

输入：n = 3, edges = [[0,1,6],[1,2,8]], k = 1, t = 6
输出：-1
解释：
有两条 k = 1 条边的路径：
- 0 -> 1 权重为 6 = t，不严格小于 t。
- 1 -> 2 权重为 8 > t，不严格小于 t。
由于没有权重总和严格小于 t 的路径，答案是 -1。

提示：

1 <= n <= 300
0 <= edges.length <= 300
edges[i] = [ui, vi, wi]
0 <= ui, vi < n
ui != vi
1 <= wi <= 10
0 <= k <= 300
1 <= t <= 600
输入的图保证是 DAG。
没有重复的边。

解题思路

这是一个典型的动态规划问题，需要在有向无环图中找到恰好包含 k 条边且权重和小于 t 的最大权重路径。

思路分析：

状态定义：使用 dp[i][j] 表示到达节点 i 且路径长度为 j 的所有可能权重集合。由于我们需要维护所有可能的权重值（而不是单一最优值），使用集合来存储。
状态转移：对于每个节点和每条边，我们从前一个状态转移到当前状态。具体地，对于边 (u, v, w)，如果 dp[u][j-1] 中有权重 weight，则可以转移到 dp[v][j] 中的权重 weight + w（前提是 weight + w < t）。
初始化：每个节点在路径长度为 0 时的权重为 0，即 dp[i][0] = {0}。
优化考虑：由于权重范围有限（每条边权重最多为 10，最多 300 条边），总权重不会超过 3000，可以使用位集或布尔数组优化集合操作。
答案计算：遍历所有节点的 dp[i][k] 集合，找到小于 t 的最大权重值。

算法复杂度：

时间复杂度：O(n × k × t × |edges|)
空间复杂度：O(n × k × t)

由于约束条件较小，这种方法是可行的。使用集合存储所有可能的权重值，确保我们不会遗漏任何可能的路径组合。

代码实现

class Solution {
public:
    int maxWeight(int n, vector<vector<int>>& edges, int k, int t) {
        vector<vector<set<int>>> dp(n, vector<set<int>>(k + 1));
        
        // 初始化：每个节点在路径长度为0时权重为0
        for (int i = 0; i < n; i++) {
            dp[i][0].insert(0);
        }
        
        // 构建邻接表
        vector<vector<pair<int, int>>> graph(n);
        for (auto& edge : edges) {
            graph[edge[0]].push_back({edge[1], edge[2]});
        }
        
        // 动态规划
        for (int len = 1; len <= k; len++) {
            for (int u = 0; u < n; u++) {
                for (auto& [v, w] : graph[u]) {
                    for (int weight : dp[u][len - 1]) {
                        if (weight + w < t) {
                            dp[v][len].insert(weight + w);
                        }
                    }
                }
            }
        }
        
        // 找到最大权重
        int maxW = -1;
        for (int i = 0; i < n; i++) {
            for (int weight : dp[i][k]) {
                maxW = max(maxW, weight);
            }
        }
        
        return maxW;
    }
};

class Solution:
    def maxWeight(self, n: int, edges: List[List[int]], k: int, t: int) -> int:
        # dp[i][j] 表示到达节点i且路径长度为j的所有可能权重集合
        dp = [[set() for _ in range(k + 1)] for _ in range(n)]
        
        # 初始化：每个节点在路径长度为0时权重为0
        for i in range(n):
            dp[i][0].add(0)
        
        # 构建邻接表
        graph = [[] for _ in range(n)]
        for u, v, w in edges:
            graph[u].append((v, w))
        
        # 动态规划
        for length in range(1, k + 1):
            for u in range(n):
                for v, w in graph[u]:
                    for weight in dp[u][length - 1]:
                        if weight + w < t:
                            dp[v][length].add(weight + w)
        
        # 找到最大权重
        max_weight = -1
        for i in range(n):
            for weight in dp[i][k]:
                max_weight = max(max_weight, weight)
        
        return max_weight

public class Solution {
    public int MaxWeight(int n, int[][] edges, int k, int t) {
        var dp = new HashSet<int>[n, k + 1];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= k; j++) {
                dp[i, j] = new HashSet<int>();
            }
        }
        
        // 初始化：每个节点在路径长度为0时权重为0
        for (int i = 0; i < n; i++) {
            dp[i, 0].Add(0);
        }
        
        // 构建邻接表
        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) {
            graph[edge[0]].Add((edge[1], edge[2]));
        }
        
        // 动态规划
        for (int len = 1; len <= k; len++) {
            for (int u = 0; u < n; u++) {
                foreach (var (v, w) in graph[u]) {
                    foreach (int weight in dp[u, len - 1]) {
                        if (weight + w < t) {
                            dp[v, len].Add(weight + w);
                        }
                    }
                }
            }
        }
        
        // 找到最大权重
        int maxWeight = -1;
        for (int i = 0; i < n; i++) {
            foreach (int weight in dp[i, k]) {
                maxWeight = Math.Max(maxWeight, weight);
            }
        }
        
        return maxWeight;
    }
}

var maxWeight = function(n, edges, k, t) {
    // dp[i][j] 表示到达节点i且路径长度为j的所有可能权重集合
    const dp = Array(n).fill(null).map(() => 
        Array(k + 1).fill(null).map(() => new Set())
    );
    
    // 初始化：每个节点在路径长度为0时权重为0
    for (let i = 0; i < n; i++) {
        dp[i][0].add(0);
    }
    
    // 构建邻接表
    const graph = Array(n).fill(null).map(() => []);
    for (const [u, v, w] of edges) {
        graph[u].push([v, w]);
    }
    
    // 动态规划
    for (let len = 1; len <= k; len++) {
        for (let u = 0; u < n; u++) {
            for (const [v, w] of graph[u]) {
                for (const weight of dp[u][len - 1]) {
                    if (weight + w < t) {
                        dp[v][len].add(weight + w);
                    }
                }
            }
        }
    }
    
    // 找到最大权重
    let maxWeight = -1;
    for (let i = 0; i < n; i++) {
        for (const weight of dp[i][k]) {
            maxWeight = Math.max(maxWeight, weight);
        }
    }
    
    return maxWeight;
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型	值
时间复杂度	O(n × k × t × \|edges\|)
空间复杂度	O(n × k × t)

题目描述#

解题思路#

代码实现#

复杂度分析#

题目描述

解题思路

代码实现

复杂度分析