有哪些网站制作公司,建筑培训网址,手机软件商城下载app,淘客那些网站怎么做的文章目录1. 题目2. 解题1. 题目
给你一张 无向 图#xff0c;图中有 n 个节点#xff0c;节点编号从 0 到 n - 1 #xff08;都包括#xff09;。 同时给你一个下标从 0 开始的整数数组 values #xff0c;其中 values[i] 是第 i 个节点的 价值 。同时给你一个下标从 0 开…
文章目录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 秒的一条路径。 你可以访问一个节点任意次。 一条合法路径的 价值 定义为路径中 不同节点 的价值 之和 每个节点的价值 至多 算入价值总和中一次。
请你返回一条合法路径的 最大 价值。
注意每个节点 至多 有 四条 边与之相连。
示例 1
输入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
输入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
输入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
输入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(vectorint values, vectorvectorint edges, int maxTime) {int n values.size();vectorunordered_mapint,int g(n);vectorint 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(vectorunordered_mapint,int g, vectorint values, int maxTime, vectorint vis, int idx, int time, int val){if(time maxTime) return; // 超时了if(idx0 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, timet, valvalues[nid]);vis[nid]--;}else // 访问过了不能再获得价值{vis[nid];dfs(g, values, maxTime, vis, nid, timet, val);vis[nid]--;}}}
};404 ms 23.6 MB C 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
