文章目录
1. 题目
2. 解题
1. 题目
给你一张 无向 图，图中有 n 个节点，节点编号从 0 到 n - 1 （都包括）。
同时给你一个下标从 0 开始的整数数组 values ，其中 values[i] 是第 i 个节点的 价值 。同时给你一个下标从 0 开始的二维整数数组 edges ，其中 edges[j] = [uj, vj, timej] 表示节点 uj 和 vj 之间有一条需要 timej 秒才能通过的无向边。最后，给你一个整数 maxTime 。
合法路径 指的是图中任意一条从节点 0 开始，最终回到节点 0 ，且花费的总时间 不超过 maxTime 秒的一条路径。
你可以访问一个节点任意次。
一条合法路径的 价值 定义为路径中 不同节点 的价值 之和 （每个节点的价值 至多 算入价值总和中一次）。
请你返回一条合法路径的 最大 价值。
注意：每个节点 至多 有 四条 边与之相连。
输入：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 。
输入：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 。
输入：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 。
输入：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] 所有节点对 互不相同 。 每个节点 至多有四条 边。 图可能不连通。
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++
