LeetCode 题解工作台
最大化一张图中的路径价值
给你一张 无向 图，图中有 n 个节点，节点编号从 0 到 n - 1 （ 都包括 ）。同时给你一个下标从 0 开始的整数数组 values ，其中 values[i] 是第 i 个节点的 价值 。同时给你一个下标从 0 开始的二维整数数组 edges ，其中 edges[j] = [u j , v…
3
题型
5
代码语言
3
相关题
当前训练重点
困难 · 回溯·pruning
答案摘要
我们观察题目的数据范围，可以发现从 开始的每条合法路径的边数不超过 $\frac{\textit{maxTime}}{\min(time_j)} = \frac{100}{10} = 10$ 条，并且每个节点至多有四条边，所以我们可以直接使用朴素的 DFS 暴力搜索所有合法路径。 我们先将图的边存储在邻接表表 中，然后我们设计一个函数 $\textit{dfs}(u, \textit{cost…
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 回溯·pruning 题型思路
题目描述
给你一张 无向 图，图中有 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 。
示例 3：
输入：values = [1,2,3,4], edges = [[0,1,10],[1,2,11],[2,3,12],[1,3,13]], maxTime = 50 输出：7 解释： 一条可能的路径为：0 -> 1 -> 3 -> 1 -> 0 。总花费时间为 10 + 13 + 13 + 10 = 46 <= 50 。 访问过的节点为 0 ，1 和 3 ，最大路径价值为 1 + 2 + 4 = 7 。
示例 4：
输入：values = [0,1,2], edges = [[1,2,10]], maxTime = 10 输出：0 解释： 唯一一条路径为 0 。总花费时间为 0 。 唯一访问过的节点为 0 ，最大路径价值为 0 。
提示：
n == values.length1 <= n <= 10000 <= values[i] <= 1080 <= edges.length <= 2000edges[j].length == 30 <= uj < vj <= n - 110 <= timej, maxTime <= 100[uj, vj]所有节点对 互不相同 。- 每个节点 至多有四条 边。
- 图可能不连通。
解题思路
方法一：DFS
我们观察题目的数据范围，可以发现从 开始的每条合法路径的边数不超过 条，并且每个节点至多有四条边，所以我们可以直接使用朴素的 DFS 暴力搜索所有合法路径。
我们先将图的边存储在邻接表表 中，然后我们设计一个函数 ，其中 表示当前节点编号，而 和 分别表示当前路径的花费时间和价值。另外，使用一个长度为 的数组 记录每个节点是否被访问过。初始时，我们将节点 标记为已访问。
函数 的逻辑如下：
- 如果当前节点编号 等于 ，表示我们已经回到了起点，那么我们更新答案为 ；
- 遍历当前节点 的所有邻居节点 ，如果当前路径的花费时间加上边 的时间 不超过 ，那么我们可以选择继续访问节点 ；
- 如果节点 已经被访问过，那么我们直接递归调用 ；
- 如果节点 没有被访问过，我们标记节点 为已访问，然后递归调用 ，最后恢复节点 的访问状态。
在主函数中，我们调用 ，并返回答案 即可。
时间复杂度 ，空间复杂度 。其中 和 分别表示节点数和边数。
class Solution:
def maximalPathQuality(
self, values: List[int], edges: List[List[int]], maxTime: int
) -> int:
def dfs(u: int, cost: int, value: int):
if u == 0:
nonlocal ans
ans = max(ans, value)
for v, t in g[u]:
if cost + t <= maxTime:
if vis[v]:
dfs(v, cost + t, value)
else:
vis[v] = True
dfs(v, cost + t, value + values[v])
vis[v] = False
n = len(values)
g = [[] for _ in range(n)]
for u, v, t in edges:
g[u].append((v, t))
g[v].append((u, t))
vis = [False] * n
vis[0] = True
ans = 0
dfs(0, 0, values[0])
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity can be exponential in the number of nodes due to backtracking, but pruning reduces unnecessary paths. Space complexity is O(n) for visited tracking and recursion stack. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Emphasize pruning paths exceeding maxTime.
- question_mark
Ask how revisiting nodes affects path quality calculation.
- question_mark
Probe optimization strategies for handling high node counts.
常见陷阱
外企场景- error
Forgetting to count each node's value only once despite multiple visits.
- error
Not pruning paths early, leading to TLE on dense graphs.
- error
Assuming the graph is connected or all nodes are reachable from node 0.
进阶变体
外企场景- arrow_right_alt
Limit the path to visit each node at most once for stricter constraints.
- arrow_right_alt
Change maxTime dynamically and recalculate maximum path quality.
- arrow_right_alt
Consider directed edges or weighted node values instead of uniform traversal rules.