Leetcode2065-最大化一张图中的路径价值

暴搜+回溯

注意到：每个节点 至多 有 四条 边与之相连。

因此考虑暴搜所有路径，每进入一个点，就把它的价值添加到当前状态中，同时把它的价值置为0，回溯的时候再还原现场；当进入点0时，更新答案；

class Solution {
public:
    int maximalPathQuality(vector<int>& values, vectorint>>& edges, int maxTime) {
        int n=values.size(),ans=0;
        vectorint,int>>> g(n);
        for(auto p:edges){
            g[p[0]].push_back({p[1],p[2]});
            g[p[1]].push_back({p[0],p[2]});
        }
        function<void(int,int,int)> dfs=[&](int x,int t,int v){
            int sv=values[x];
            values[x]=0;
            v+=sv;
            if(!x) ans=max(ans,v);
            for(auto [y,st]:g[x]){
                if(t+st>maxTime) continue;
                dfs(y,t+st,v);
            }
            values[x]=sv;
        };
        dfs(0,0,0);
        return ans;
    }
};

时间复杂度为指数级别

空间复杂度：O（n）