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, List<int[]>[] 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發出的邊的集合List，List中的每個int[]，int[0]為終點，int[1]為距離List<int[]>[] map = new ArrayList[n];for(int i = 0 ; i < n; i ++){map[i] = new ArrayList<int[]>();}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;}
}
)
