LeetCode 5921. 最大化一张图中的路径价值(DFS)

文章目录

1. 题目

给你一张 无向 图,图中有 n 个节点,节点编号从 0 到 n - 1 (都包括)。
同时给你一个下标从 0 开始的整数数组 values ,其中 values[i] 是第 i 个节点的 价值 。同时给你一个下标从 0 开始的二维整数数组 edges ,其中 edges[j] = [uj, vj, timej] 表示节点 uj 和 vj 之间有一条需要 timej 秒才能通过的无向边。最后,给你一个整数 maxTime 。

合法路径 指的是图中任意一条从节点 0 开始,最终回到节点 0 ,且花费的总时间 不超过 maxTime 秒的一条路径。
你可以访问一个节点任意次
一条合法路径的 价值 定义为路径中 不同节点 的价值 之和 (每个节点的价值 至多 算入价值总和中一次)。

请你返回一条合法路径的 最大 价值。

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

示例 1:
LeetCode 5921. 最大化一张图中的路径价值(DFS)

输入: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:
LeetCode 5921. 最大化一张图中的路径价值(DFS)

输入: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:
LeetCode 5921. 最大化一张图中的路径价值(DFS)

输入: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:
LeetCode 5921. 最大化一张图中的路径价值(DFS)

输入:values = [0,1,2], 
edges = [[1,2,10]], maxTime = 10
输出:0
解释:
唯一一条路径为 0 。总花费时间为 0 。
唯一访问过的节点为 0 ,最大路径价值为 0 。
 
提示:
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] 所有节点对 互不相同 。
每个节点 至多有四条 边。
图可能不连通。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/maximum-path-quality-of-a-graph
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

2. 解题

  • 看见条件 10 <= timej, maxTime <= 100,最多 dfs 10 层就完事了
  • 建图,暴力搜索就是了
class Solution {
    int maxVal = 0;
public:
    int maximalPathQuality(vector<int>& values, vector<vector<int>>& edges, int maxTime) {
        int n = values.size();
        vector<unordered_map<int,int>> g(n);
        vector<int> vis(n);
        for(auto& e : edges)
        { // 建图
            g[e[0]][e[1]] = e[2];
            g[e[1]][e[0]] = e[2];
        }
        vis[0] = 1; // 访问节点次数
        dfs(g, values, maxTime, vis, 0, 0, values[0]);
        return maxVal;
    }
    void dfs(vector<unordered_map<int,int>>& g, vector<int>& values, int maxTime, vector<int>& vis, int idx, int time, int val)
    {
        if(time > maxTime) return; // 超时了
        if(idx==0 && val > maxVal)
        {
            maxVal = val;
        }
        for(auto& nid_t : g[idx])
        { //遍历相邻节点
            int nid = nid_t.first; // 相邻节点编号
            int t = nid_t.second; // 需要花费时间
            if(vis[nid] == 0) // 没有访问这个节点,可以获得价值
            {
                vis[nid]++;
                dfs(g, values, maxTime, vis, nid, time+t, val+values[nid]);
                vis[nid]--;
            }
            else // 访问过了,不能再获得价值
            {
                vis[nid]++;
                dfs(g, values, maxTime, vis, nid, time+t, val);
                vis[nid]--;
            }
        }
    }
};

404 ms 23.6 MB C++


我的CSDN博客地址 https://michael.blog.csdn.net/

长按或扫码关注我的公众号(Michael阿明),一起加油、一起学习进步!
LeetCode 5921. 最大化一张图中的路径价值(DFS)

上一篇:2021.9.21 乘法


下一篇:斯坦纳树