做网站怎样使图片自由移动,高端网站建设公司报价,建设网站的建议,站长统计网站统计Leetcode 2065. 最大化一张图中的路径价值
暴力DFS
容易想到#xff0c;从0点出发DFS#xff0c;期间维护已经走过的距离#xff08;时间#xff09;和途径点的权值之和#xff0c;若访问到0点则更新答案#xff0c;若下一步的距离与已走过的距离和超出了maxTime#…Leetcode 2065. 最大化一张图中的路径价值
暴力DFS
容易想到从0点出发DFS期间维护已经走过的距离时间和途径点的权值之和若访问到0点则更新答案若下一步的距离与已走过的距离和超出了maxTime则不能向下继续DFS
注意的是每个点的权值只会计算一次可以使用一个boolean数组 vis[ ] 来记录该点的权值是否已经计算过 另一种方法是每当第一次到达一个点并获得权值后将它的权值修改为0若后续又一次访问到该点加0不会影响最终结果省去vis数组的操作
超时通过样例59 / 62
class Solution {int res;public void dfs(int x, int[] values, int[][] map, int maxTime, int time, int sum){if(x 0){res Math.max(res, sum);}int n values.length;for(int i 0 ; i n; i ){if(map[x][i] ! 0 time map[x][i] maxTime){int val values[i];values[i] 0;dfs(i, values, map, maxTime, time map[x][i], sum val);values[i] val;}}return ;}public int maximalPathQuality(int[] values, int[][] edges, int maxTime) {int n values.length;int [][] map new int [n][n];for(int[] e: edges){int a e[0];int b e[1];int t e[2];map[a][b] t;map[b][a] t;}res 0;int val values[0];values[0] 0;dfs(0, values, map, maxTime, 0, val);return res;}
}最短路 优化剪枝
注意到当判断一个点是否可以继续深入时可以考虑的一种剪枝方式是向该点前进后若剩余的时间不足以返回0点则不必向该点DFS 该问题转换为判断x点回到0点的距离是否超过maxTime - time即为0点出发的最短路问题使用Dijstra算法实现
另一方面当图中的点较稀疏时使用邻接矩阵遍历找边会导致时间的浪费因此选择使用邻接表实现图的存储
class Solution {int res;public void dfs(int x, int[] values, Listint[][] map, int maxTime, int time, int sum, int[] dis){if(x 0){res Math.max(res, sum);}int n values.length;for(int arr[] : map[x]){int y arr[0];int t arr[1];// 求和时增加dis若不足返回0点则不必DFSif(time t dis[y] maxTime){int val values[y];values[y] 0;dfs(y, values, map, maxTime, time t, sum val, dis);values[y] val;}}return ;}public int maximalPathQuality(int[] values, int[][] edges, int maxTime) {int n values.length;// 邻接表 map[x]为x发出的边的集合ListList中的每个int[]int[0]为终点int[1]为距离Listint[][] map new ArrayList[n];for(int i 0 ; i n; i ){map[i] new ArrayListint[]();}for(int[] e: edges){int a e[0];int b e[1];int t e[2];map[a].add(new int[]{b, t});map[b].add(new int[]{a, t});}// dijstraint inf Integer.MAX_VALUE;int dis[] new int [n];Arrays.fill(dis, inf);for(int [] arr: map[0]){int y arr[0];int t arr[1];dis[y] t;}boolean vis[] new boolean[n];vis[0] true;while(true){int min Integer.MAX_VALUE;int index -1;for(int i 0 ; i n; i ){if(!vis[i] dis[i] min){min dis[i];index i;}}if(index -1)break;vis[index] true;// 遍历index点发出的边for (int[] arr : map[index]) {int v arr[0];int t arr[1];if (!vis[v] dis[index] t dis[v]) {dis[v] dis[index] t;}}}// DFSres 0;int val values[0];values[0] 0;dfs(0, values, map, maxTime, 0, val, dis);return res;}
}
