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

题目描述

给你一个正整数 n ，表示总共有 n 个城市，城市从 1 到 n 编号。给你一个二维数组 roads ，其中 roads[i] = [a_i, b_i, distance_i] 表示城市 a_i 和 b_i 之间有一条双向道路，道路距离为 distance_i 。城市构成的图不一定是连通的。

两个城市之间一条路径的分数定义为这条路径中道路的最小距离。

返回城市 1 和城市 n 之间的所有路径的最小分数。

注意：

一条路径指的是两个城市之间的道路序列。
一条路径可以多次包含同一条道路，你也可以沿着路径多次到达城市 1 和城市 n 。
测试数据保证城市 1 和城市n 之间至少有一条路径。

示例 1：

输入：n = 4, roads = [[1,2,9],[2,3,6],[2,4,5],[1,4,7]]
输出：5
解释：城市 1 到城市 4 的路径中，分数最小的一条为：1 -> 2 -> 4 。这条路径的分数是 min(9,5) = 5 。
不存在分数更小的路径。

示例 2：

输入：n = 4, roads = [[1,2,2],[1,3,4],[3,4,7]]
输出：2
解释：城市 1 到城市 4 分数最小的路径是：1 -> 2 -> 1 -> 3 -> 4 。这条路径的分数是 min(2,2,4,7) = 2 。

提示：

2 <= n <= 10⁵
1 <= roads.length <= 10⁵
roads[i].length == 3
1 <= a_i, b_i <= n
a_i != b_i
1 <= distance_i <= 10⁴
不会有重复的边。
城市 1 和城市 n 之间至少有一条路径。

解法

方法一：DFS

根据题目描述，每条边可以经过多次，并且保证节点 \(1\) 和节点 \(n\) 在同一个连通块中。因此，题目实际上求的是节点 \(1\) 所在连通块中的最小边权。

我们首先根据 \(\textit{roads}\) 构建无向图 \(g\)，然后从节点 \(1\) 开始 DFS。在遍历连通块的过程中，对每条经过的边用 \(\textit{ans} = \min(\textit{ans}, w)\) 更新答案。

时间复杂度 \(O(n + m)\)，空间复杂度 \(O(n + m)\)。其中 \(n\) 和 \(m\) 分别是节点数和边数。

Python3JavaC++GoTypeScriptRustJavaScript

class Solution:
    def minScore(self, n: int, roads: List[List[int]]) -> int:
        def dfs(a: int):
            vis[a] = True
            nonlocal ans
            for b, w in g[a]:
                ans = min(ans, w)
                if not vis[b]:
                    dfs(b)

        g = [[] for _ in range(n + 1)]
        for a, b, w in roads:
            g[a].append((b, w))
            g[b].append((a, w))
        ans = inf
        vis = [False] * (n + 1)
        dfs(1)
        return ans

class Solution {
    private int ans;
    private boolean[] vis;
    private List<int[]>[] g;

    public int minScore(int n, int[][] roads) {
        g = new ArrayList[n + 1];
        Arrays.setAll(g, k -> new ArrayList<>());

        for (int[] e : roads) {
            int a = e[0], b = e[1], w = e[2];
            g[a].add(new int[]{b, w});
            g[b].add(new int[]{a, w});
        }

        ans = Integer.MAX_VALUE;
        vis = new boolean[n + 1];

        dfs(1);
        return ans;
    }

    private void dfs(int a) {
        vis[a] = true;
        for (int[] nb : g[a]) {
            int b = nb[0], w = nb[1];
            ans = Math.min(ans, w);
            if (!vis[b]) {
                dfs(b);
            }
        }
    }
}

class Solution {
public:
    int minScore(int n, vector<vector<int>>& roads) {
        vector<vector<pair<int,int>>> g(n + 1);
        for (auto &e : roads) {
            int a = e[0], b = e[1], w = e[2];
            g[a].push_back({b, w});
            g[b].push_back({a, w});
        }

        vector<bool> vis(n + 1, false);
        int ans = INT_MAX;

        auto dfs = [&](this auto&& dfs, int a) -> void {
            vis[a] = true;
            for (auto &[b, w] : g[a]) {
                ans = min(ans, w);
                if (!vis[b]) {
                    dfs(b);
                }
            }
        };

        dfs(1);
        return ans;
    }
};

func minScore(n int, roads [][]int) int {
    g := make([][][2]int, n+1)
    for _, e := range roads {
        a, b, w := e[0], e[1], e[2]
        g[a] = append(g[a], [2]int{b, w})
        g[b] = append(g[b], [2]int{a, w})
    }

    vis := make([]bool, n+1)
    ans := int(1e9)

    var dfs func(int)
    dfs = func(a int) {
        vis[a] = true
        for _, nb := range g[a] {
            b, w := nb[0], nb[1]
            ans = min(ans, w)
            if !vis[b] {
                dfs(b)
            }
        }
    }

    dfs(1)
    return ans
}

function minScore(n: number, roads: number[][]): number {
    const g: [number, number][][] = Array.from({ length: n + 1 }, () => []);
    for (const [a, b, w] of roads) {
        g[a].push([b, w]);
        g[b].push([a, w]);
    }

    const vis = new Array(n + 1).fill(false);
    let ans = Infinity;

    const dfs = (a: number): void => {
        vis[a] = true;
        for (const [b, w] of g[a]) {
            ans = Math.min(ans, w);
            if (!vis[b]) {
                dfs(b);
            }
        }
    };

    dfs(1);
    return ans;
}

impl Solution {
    pub fn min_score(n: i32, roads: Vec<Vec<i32>>) -> i32 {
        let n = n as usize;
        let mut g: Vec<Vec<(usize, i32)>> = vec![vec![]; n + 1];

        for e in roads {
            let a = e[0] as usize;
            let b = e[1] as usize;
            let w = e[2];
            g[a].push((b, w));
            g[b].push((a, w));
        }

        let mut vis = vec![false; n + 1];
        let mut ans = i32::MAX;

        fn dfs(
            a: usize,
            g: &Vec<Vec<(usize, i32)>>,
            vis: &mut Vec<bool>,
            ans: &mut i32,
        ) {
            vis[a] = true;

            for &(b, w) in &g[a] {
                *ans = (*ans).min(w);
                if !vis[b] {
                    dfs(b, g, vis, ans);
                }
            }
        }

        dfs(1, &g, &mut vis, &mut ans);
        ans
    }
}

/**
 * @param {number} n
 * @param {number[][]} roads
 * @return {number}
 */
var minScore = function (n, roads) {
    const g = Array.from({ length: n + 1 }, () => []);

    for (const [a, b, w] of roads) {
        g[a].push([b, w]);
        g[b].push([a, w]);
    }

    const vis = new Array(n + 1).fill(false);
    let ans = Infinity;

    const dfs = a => {
        vis[a] = true;
        for (const [b, w] of g[a]) {
            ans = Math.min(ans, w);
            if (!vis[b]) dfs(b);
        }
    };

    dfs(1);
    return ans;
};

方法二：BFS

我们也可以用 BFS 来求解。将节点 \(1\) 加入队列，逐层扩展与节点 \(1\) 连通的子图，每次访问边时用 \(\textit{ans} = \min(\textit{ans}, w)\) 更新答案。