LeetCode 2024/7 每日一题 合集

2024/7/1 2065. 最大化一张图中的路径价值

分析

注意观察到至多走十条边，因此直接爆搜即可。

代码实现

class Solution {
public:
    int maximalPathQuality(vector<int>& values, vector<vector<int>>& edges, int maxTime) {
        int n = size(values), m = size(edges);
        std::vector<std::vector<std::pair<int, int>>> g(n);
        for (auto &edge : edges) {
            int u = edge[0], v = edge[1], w = edge[2];
            g[u].emplace_back(v, w);
            g[v].emplace_back(u, w);
        }
        std::vector<bool> vis(n);
        vis[0] = true;
        int ans = 0;
        auto dfs = [&](auto &&self, int u, int times, int cost)->void {
            if (u == 0) {
                ans = std::max(ans, cost);
            }
            for (auto [v, w] : g[u]) if (times + w <= maxTime) {
                if (!vis[v]) {
                    vis[v] = true;
                    self(self, v, times + w, cost + values[v]);
                    vis[v] = false;
                } else {
                    self(self, v, times + w, cost);
                }
            }
        };
        dfs(dfs, 0, 0, values[0]);
        return ans;
    }
};

戳这里前往原题(╹▽╹)