博客

6255. 两个城市间路径的最小分数

https://leetcode.cn/problems/minimum-score-of-a-path-between-two-cities/

Solution

结合标红框的提示，可以知道该题就是找 城市 1 到 城市 n 连通图中最小权值的边。

1. 先建立图
2. 定义一个 vis 数组，记录访问过的数组
3. 深搜即可

class Solution {
    int ans = Integer.MAX_VALUE;

    public int minScore(int n, int[][] roads) {
        List<ArrayList<int[]>> g = new ArrayList<>();
        for (int i = 0; i < n + 1; i++) {
            g.add(new ArrayList<>());
        }

        for (int[] road : roads) {
            g.get(road[0]).add(new int[] {road[1], road[2]});
            g.get(road[1]).add(new int[] {road[0], road[2]});
        }
        
        boolean[] vis = new boolean[n + 1];
        
        dfs(g, vis, 1);
        
        return ans;
    }

    void dfs(List<ArrayList<int[]>> g, boolean[] vis, int x) {
        vis[x] = true;
        for (int[] arr : g.get(x)) {
            ans = Math.min(ans, arr[1]);
            if (!vis[arr[0]]) {
                dfs(g, vis, arr[0]);
            }
        }
    }
}