遂宁网站建设哪家好,深圳做响应式网站设计,狠狠做网站改成什么了,哪家公司建站的力扣每日一题 题目#xff1a;2646. 最小化旅行的价格总和 日期#xff1a;2023-12-06 用时#xff1a;30 m 14 s 时间#xff1a;8ms 内存#xff1a;42.98MB 思路#xff1a;先统计旅行中每个节点路过的次数#xff08;dfs方法#xff09;#xff0c;再计算减半后的…力扣每日一题 题目2646. 最小化旅行的价格总和 日期2023-12-06 用时30 m 14 s 时间8ms 内存42.98MB 思路先统计旅行中每个节点路过的次数dfs方法再计算减半后的价格之和的最小值dp方法最后比较下减半和未减半的价格。dp方法中对于相邻的父子节点有两种情况
如果父节点价格不变那么子节点的价格取减半和不变两种情况的最小值如果父节点价格减半那么子节点的价格只能不变
代码每条路上通过的城市数量实际就是图中每个节点的子节点数量。
class Solution {public int minimumTotalPrice(int n, int[][] edges, int[] price, int[][] trips) {list new ArrayList[n];for(int i0;in;i){list[i] new ArrayList();}for(int[] edge:edges){list[edge[0]].add(edge[1]);list[edge[1]].add(edge[0]);}cnt new int[n];for(int[] trip:trips){end trip[1];dfs(trip[0],-1);}int[] res dp(0,-1,price);return Math.min(res[0],res[1]);}ListInteger[] list;int end;int[] cnt;boolean dfs(int x, int fa) {if (x end) {cnt[x];return true;}for (int y : list[x]) {if (y ! fa dfs(y, x)) {cnt[x];return true;}}return false;}int[] dp(int index,int target,int[] price){int prices price[index]*cnt[index];int halfPrices prices/2;for(int num:list[index]){if(num!target){int[] res dp(num,index,price);prices Math.min(res[0],res[1]);halfPrices res[0];}}return new int[]{prices,halfPrices};}
}
