Hard

题目描述

有一个由 n 个节点组成的无向图，节点编号从 0 到 n - 1（包含）。给你一个下标从 0 开始的整数数组 values，其中 values[i] 是第 i 个节点的值。同时给你一个下标从 0 开始的二维整数数组 edges，其中每个 edges[j] = [uj, vj, timej] 表示在节点 uj 和 vj 之间有一条无向边，在这两个节点之间移动需要 timej 秒。最后，给你一个整数 maxTime。

图中的有效路径是指从节点 0 开始，在节点 0 结束，且总时间不超过 maxTime 秒的任意路径。你可以多次访问同一个节点。有效路径的质量是路径中访问的唯一节点的值之和（每个节点的值最多在总和中加一次）。

返回有效路径的最大质量。

注意：每个节点最多连接四条边。

示例 1：

输入：values = [0,32,10,43], edges = [[0,1,10],[1,2,15],[0,3,10]], maxTime = 49
输出：75
解释：
一个可能的路径是 0 -> 1 -> 0 -> 3 -> 0。总时间为 10 + 10 + 10 + 10 = 40 <= 49。
访问的节点是 0、1 和 3，给出最大路径质量 0 + 32 + 43 = 75。

示例 2：

输入：values = [5,10,15,20], edges = [[0,1,10],[1,2,10],[0,3,10]], maxTime = 30
输出：25
解释：
一个可能的路径是 0 -> 3 -> 0。总时间为 10 + 10 = 20 <= 30。
访问的节点是 0 和 3，给出最大路径质量 5 + 20 = 25。

提示：

  • n == values.length
  • 1 <= n <= 1000
  • 0 <= values[i] <= 10^8
  • 0 <= edges.length <= 2000
  • edges[j].length == 3
  • 0 <= uj < vj <= n - 1
  • 10 <= timej, maxTime <= 100
  • 所有的对 [uj, vj] 都是唯一的
  • 每个节点最多连接四条边
  • 图可能不连通

解题思路

解题思路

这是一个经典的回溯搜索问题。我们需要从节点0开始探索所有可能的路径，并且最终回到节点0。

核心思路：

  1. 图的建立：首先需要将边的信息转换成邻接表，方便遍历每个节点的邻居。

  2. 回溯搜索：使用DFS进行回溯搜索，在搜索过程中：

    • 记录当前已使用的时间
    • 记录已访问的节点（用于计算质量）
    • 当回到节点0且时间允许时，更新最大质量

  3. 剪枝优化：

    • 时间剪枝：如果当前时间已经超过maxTime，直接返回
    • 由于每个节点最多连接4条边，搜索空间相对有限

  4. 质量计算：使用访问计数数组来跟踪每个节点是否被访问过，只有第一次访问时才将节点值加入质量计算。

算法步骤：

  1. 构建邻接表表示图
  2. 从节点0开始DFS搜索
  3. 对于每个相邻节点，如果时间允许则递归访问
  4. 当再次到达节点0时，计算并更新最大质量
  5. 回溯时恢复状态

这个问题的关键在于状态的正确维护和及时的剪枝，由于约束条件限制了每个节点的度数，所以暴力搜索是可行的。

代码实现

class Solution {
public:
    int maximalPathQuality(vector<int>& values, vector<vector<int>>& edges, int maxTime) {
        int n = values.size();
        vector<vector<pair<int, int>>> graph(n);
        
        // 构建邻接表
        for (auto& edge : edges) {
            int u = edge[0], v = edge[1], time = edge[2];
            graph[u].push_back({v, time});
            graph[v].push_back({u, time});
        }
        
        vector<int> visited(n, 0);
        int maxQuality = 0;
        
        function<void(int, int, int)> dfs = [&](int node, int time, int quality) {
            if (time > maxTime) return;
            
            // 第一次访问该节点，增加质量
            if (visited[node] == 0) {
                quality += values[node];
            }
            visited[node]++;
            
            // 如果回到起点，更新最大质量
            if (node == 0) {
                maxQuality = max(maxQuality, quality);
            }
            
            // 继续搜索相邻节点
            for (auto& [neighbor, travelTime] : graph[node]) {
                if (time + travelTime <= maxTime) {
                    dfs(neighbor, time + travelTime, quality);
                }
            }
            
            // 回溯
            visited[node]--;
        };
        
        dfs(0, 0, 0);
        return maxQuality;
    }
};

class Solution:
    def maximalPathQuality(self, values: List[int], edges: List[List[int]], maxTime: int) -> int:
        n = len(values)
        graph = [[] for _ in range(n)]
        
        # 构建邻接表
        for u, v, time in edges:
            graph[u].append((v, time))
            graph[v].append((u, time))
        
        visited = [0] * n
        max_quality = 0
        
        def dfs(node, time, quality):
            nonlocal max_quality
            
            if time > maxTime:
                return
            
            # 第一次访问该节点，增加质量
            if visited[node] == 0:
                quality += values[node]
            visited[node] += 1
            
            # 如果回到起点，更新最大质量
            if node == 0:
                max_quality = max(max_quality, quality)
            
            # 继续搜索相邻节点
            for neighbor, travel_time in graph[node]:
                if time + travel_time <= maxTime:
                    dfs(neighbor, time + travel_time, quality)
            
            # 回溯
            visited[node] -= 1
        
        dfs(0, 0, 0)
        return max_quality

public class Solution {
    public int MaximalPathQuality(int[] values, int[][] edges, int maxTime) {
        int n = values.Length;
        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], time = edge[2];
            graph[u].Add((v, time));
            graph[v].Add((u, time));
        }
        
        var visited = new int[n];
        int maxQuality = 0;
        
        void Dfs(int node, int time, int quality) {
            if (time > maxTime) return;
            
            // 第一次访问该节点，增加质量
            if (visited[node] == 0) {
                quality += values[node];
            }
            visited[node]++;
            
            // 如果回到起点，更新最大质量
            if (node == 0) {
                maxQuality = Math.Max(maxQuality, quality);
            }
            
            // 继续搜索相邻节点
            foreach (var (neighbor, travelTime) in graph[node]) {
                if (time + travelTime <= maxTime) {
                    Dfs(neighbor, time + travelTime, quality);
                }
            }
            
            // 回溯
            visited[node]--;
        }
        
        Dfs(0, 0, 0);
        return maxQuality;
    }
}

var maximalPathQuality = function(values, edges, maxTime) {
    const n = values.length;
    const graph = Array(n).fill().map(() => []);
    
    // 构建邻接表
    for (const [u, v, time] of edges) {
        graph[u].push([v, time]);
        graph[v].push([u, time]);
    }
    
    const visited = new Array(n).fill(0);
    let maxQuality = 0;
    
    function dfs(node, time, quality) {
        if (time > maxTime) return;
        
        // 第一次访问该节点，增加质量
        if (visited[node]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(4^(maxTime/10))，其中每个节点最多连接4条边，最少边权为10，所以最多能访问maxTime/10步，每步最多4个选择
空间复杂度O(n + m)，其中n为节点数，m为边数，主要用于存储图的邻接表和递归栈空间

相关题目