Re: [閒聊] 每日LeetCode

看板Marginalman作者Rushia (みけねこ的鼻屎)時間1年前 (2023/03/23 01:43)推噓1(1推 0噓 0→)

留言1則, 1人參與討論串269/719 (看更多)

2492. Minimum Score of a Path Between Two Cities 給定一個正整數n，代表從1到n有n個城市。同時給定一個二維陣列roads，其中roads[i] = [ai, bi, distancei]表示城市ai和bi之間有一條雙向道路，距離為distancei。城市間不一定是連通的(可能無法到達)。兩個城市之間的"路徑分數"定義為此路徑上道路的最小距離，返回從城市1到城市n間所有路徑的"最小路徑分數"。 Constraints： 1.一條路徑是兩個城市之間的一系列道路。 2.路徑允許包含同一條道路多次，並且您可以在路徑上多次訪問城市1和城市n。 3.至少存在一條從城市1到城市n的路徑。 4.不存在重邊 Example： https://assets.leetcode.com/uploads/2022/10/12/graph11.png

Input: n = 4, roads = [[1,2,9],[2,3,6],[2,4,5],[1,4,7]] Output: 5 Explanation: 城市1到4之間的所有path長度為[9,6,5,7]，最小為5。 https://assets.leetcode.com/uploads/2022/10/12/graph22.png

Input: n = 4, roads = [[1,2,2],[1,3,4],[3,4,7]] Output: 2 Explanation: 城市1到4之間的所有path長度為[2,4,7]，最小為2。思路： 1.先把roads轉換成一個無向圖，途中紀錄每個點往外的最小分數路徑。 2.dfs城市1或n（題目保證連通），走訪過的城市不走訪，途中利用最小分數　來更新答案，直到沒有沒走過的點可以走訪。 3.返回ans。 JavaCode： --------------------------------------------------------------- class Solution { private int ans; public int minScore(int n, int[][] roads) { List<List<Integer>> graph = new ArrayList<>(); int[] mineScores = new int[n + 1]; Arrays.fill(mineScores, Integer.MAX_VALUE); for (int i = 0; i <= n; i++) { graph.add(new ArrayList<>()); } for (int[] road : roads) { mineScores[road[0]] = Math.min(mineScores[road[0]], road[2]); mineScores[road[1]] = Math.min(mineScores[road[1]], road[2]); graph.get(road[0]).add(road[1]); graph.get(road[1]).add(road[0]); } ans = Integer.MAX_VALUE; dfs(graph, new boolean[n + 1], mineScores, 1); return ans; } private void dfs(List<List<Integer>> graph, boolean[] visited, int[] mineScores, int i) { if (!visited[i]) { visited[i] = true; ans = Math.min(ans, mineScores[i]); for (int next : graph.get(i)) { dfs(graph, visited, mineScores, next); } } } } --------------------------------------------------------------- -- https://i.imgur.com/fHpKflu.jpg