🏙️ 两个城市间路径的最小分数

📝 题目描述

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

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

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

​ 注意：

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

📋 代码模板

java

class Solution {
    public int minScore(int n, int[][] roads) {

    }
}

typescript

function minScore(n: number, roads: number[][]): number {
    
}

💡 提示

1. $2<=n<={10}^5$
2. $1<=roads.length<={10}^5$
3. $roads[i].length==3$
4. $1<=a_i<=n$
5. $1<=b_i<=n$
6. $a_i\ne b_i$
7. $1<=distanc{e}_i<={10}^4$
8. 不会有重复的边
9. 城市1和城市n之间至少有一条路径

🚀 示例

🖊️ 题解

DFS

可惜没有如果

java

class Solution {
    public int minScore(int n, int[][] roads) {
        Map<Integer, Integer>[] graph = new Map[n + 1];
        for (int i = 1; i <= n; i++) {
            graph[i] = new HashMap<>();
        }
        for (int[] road : roads) {
            int x = road[0], y = road[1], d = road[2];
            graph[x].put(y, d);
            graph[y].put(x, d);
        }
        boolean[] visited = new boolean[n + 1];
        int[] minEdge = new int[]{Integer.MAX_VALUE};
        dfs(graph, visited, minEdge, 1);
        return minEdge[0];
    }

    private void dfs(Map<Integer, Integer>[] graph, boolean[] visited, int[] minEdge, int i) {
        if (visited[i]) {
            return;
        }
        visited[i] = true;
        for (int next : graph[i].keySet()) {
            minEdge[0] = Math.min(minEdge[0], graph[i].get(next));
            dfs(graph, visited, minEdge, next);
        }
    }
}

typescript

function minScore(n: number, roads: number[][]): number {
    const graph: Map<number, number>[] = [];
    for (let i = 1; i <= n; i++) {
        graph[i] = new Map<number, number>();
    }
    for (const road of roads) {
        const x = road[0], y = road[1], d = road[2];
        graph[x].set(y, d);
        graph[y].set(x, d);
    }
    const visited: boolean[] = Array(n + 1).fill(false);
    let minEdge = Number.MAX_SAFE_INTEGER;
    const dfs = (graph: Map<number, number>[], visited: boolean[], i: number): void => {
        if (visited[i]) {
            return;
        }
        visited[i] = true;
        for (const next of graph[i].keys()) {
            minEdge = Math.min(minEdge, graph[i].get(next)!);
            dfs(graph, visited, next);
        }
    }
    dfs(graph, visited, 1);
    return minEdge;
}

BFS

可惜没有固若

java

class Solution {
    public int minScore(int n, int[][] roads) {
        Map<Integer, Integer>[] graph = new Map[n + 1];
        for (int i = 1; i <= n; i++) {
            graph[i] = new HashMap<>();
        }
        for (int[] road : roads) {
            int x = road[0], y = road[1], d = road[2];
            graph[x].put(y, d);
            graph[y].put(x, d);
        }
        boolean[] visited = new boolean[n + 1];
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(1);
        visited[1] = true;
        int minEdge = Integer.MAX_VALUE;
        while (!queue.isEmpty()) {
            int i = queue.poll();
            for (int next : graph[i].keySet()) {
                minEdge = Math.min(minEdge, graph[i].get(next));
                if (!visited[next]) {
                    queue.offer(next);
                    visited[next] = true;
                }
            }
        }
        return minEdge;
    }
}

typescript

function minScore(n: number, roads: number[][]): number {
    const graph: Map<number, number>[] = [];
    for (let i = 1; i <= n; i++) {
        graph[i] = new Map<number, number>();
    }
    for (const road of roads) {
        const x = road[0], y = road[1], d = road[2];
        graph[x].set(y, d);
        graph[y].set(x, d);
    }
    const visited: boolean[] = Array(n + 1).fill(false);
    const queue: number[] = [1];
    visited[1] = true;
    let minEdge = Number.MAX_SAFE_INTEGER;
    while (queue.length > 0) {
        const i: number = queue.shift()!;
        for (const next of graph[i].keys()) {
            minEdge = Math.min(minEdge, graph[i].get(next)!);
            if (!visited[next]) {
                queue.push(next);
                visited[next] = true;
            }
        }
    }
    return minEdge;
}

💭 复杂度分析