[每日一题] 2065.最大化一张图中的路径价值

博主： Richard
发布时间：2024 年 07 月 01 日
72 次浏览
暂无评论
1597字数
分类： LeetCode

> https://leetcode.cn/problems/maximum-path-quality-of-a-graph/description/?envType=daily-question&envId=2024-05-06

观察题目可以发现 $10 \leq time_j, maxTime \leq 100$ ，意味着最多走 10 步。每个节点至多有四条边，因此暴力搜索的复杂度最高为 $4^{10} = 2^{20}$ ，可以在规定的时间内算完。

直接进行一个回溯：

```c++
class Solution {
public:
    int maximalPathQuality(std::vector<int>& values, std::vector<std::vector<int>>& edges, int maxTime) {
        const int n = values.size();

std::vector<std::vector<std::pair<int, int>>> graph(n);
        for (auto &edge : edges) {
            graph[edge[0]].emplace_back(edge[1], edge[2]);
            graph[edge[1]].emplace_back(edge[0], edge[2]);
        }

int res = 0;
        std::vector<bool> visited(n);
        visited[0] = true;

std::function<void(int, int, int)> dfs = [&] (int curNode, int cost, int value) {
            if (curNode == 0)
                res = std::max(res, value);

for (auto &[node, time] : graph[curNode]) {
                if (cost + time > maxTime)
                    continue;

if (visited[node]) {
                    dfs(node, cost + time, value);
                } else {
                    visited[node] = true;
                    dfs(node, cost + time, value + values[node]);
                    visited[node] = false;
                }
            }
        };

dfs(0, 0, values[0]);
        return res;
    }
};
```

- 时间复杂度：$O(m + n + d^k)$ ，其中 $m$ 为 `edges` 数组的长度，$n$ 为节点数，$d$ 为图中度的最大值，$k$ 为最长路径的边数。本题中 $d = 4, k = 10$ 。
- 空间复杂度：$O(m + n + k)$ 。存储邻接表需要 $O(m + n)$ 的空间，记录方问过的数组需要 $O(n)$ 的空间，DFS 遍历需要 $O(k)$ 的栈开销。

这道题目还有一种使用 Dijkstra 算法的解法，待填坑 ...

最后修改：2024 年 07 月 01 日