Medium

题目描述

给你一个正整数 n，表示从 1 到 n 编号的 n 座城市。同时给你一个二维数组 roads，其中 roads[i] = [ai, bi, distancei] 表示在城市 ai 和城市 bi 之间有一条距离为 distancei 的双向道路。城市图不一定是连通的。

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

返回城市 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^5
  • 1 <= roads.length <= 10^5
  • roads[i].length == 3
  • 1 <= ai, bi <= n
  • ai != bi
  • 1 <= distancei <= 10^4
  • 没有重复的边。
  • 城市 1 和城市 n 之间至少存在一条路径。

解题思路

这道题的关键洞察是：由于可以重复使用道路和访问城市，我们只需要找到连通城市1和城市n的连通分量中所有道路的最小距离。

思路分析

由于路径可以包含相同道路多次，这意味着我们可以在连通的城市之间任意移动。因此，问题转化为：在包含城市1和城市n的连通分量中，找到所有道路的最小距离。

具体来说：

  1. 如果城市1和城市n在同一个连通分量中，我们可以通过重复使用道路来构造任意路径
  2. 在这个连通分量中，路径的分数就是所有道路中距离的最小值

解法选择

  1. 并查集解法：使用并查集找到城市1所在的连通分量，统计该连通分量中所有边的最小权重
  2. DFS/BFS解法：从城市1出发遍历所有可达城市，记录遍历过程中遇到的最小边权重

推荐使用DFS解法，因为它更直观且代码简洁。我们从城市1开始DFS，访问所有可达的城市，并记录访问过程中遇到的所有边的最小权重。

代码实现

class Solution {
public:
    int minScore(int n, vector<vector<int>>& roads) {
        vector<vector<pair<int, int>>> graph(n + 1);
        
        // 构建图
        for (auto& road : roads) {
            int u = road[0], v = road[1], dist = road[2];
            graph[u].push_back({v, dist});
            graph[v].push_back({u, dist});
        }
        
        vector<bool> visited(n + 1, false);
        int minDist = INT_MAX;
        
        function<void(int)> dfs = [&](int node) {
            visited[node] = true;
            for (auto& [neighbor, dist] : graph[node]) {
                minDist = min(minDist, dist);
                if (!visited[neighbor]) {
                    dfs(neighbor);
                }
            }
        };
        
        dfs(1);
        return minDist;
    }
};

class Solution:
    def minScore(self, n: int, roads: List[List[int]]) -> int:
        from collections import defaultdict
        
        graph = defaultdict(list)
        
        # 构建图
        for u, v, dist in roads:
            graph[u].append((v, dist))
            graph[v].append((u, dist))
        
        visited = set()
        min_dist = float('inf')
        
        def dfs(node):
            nonlocal min_dist
            visited.add(node)
            for neighbor, dist in graph[node]:
                min_dist = min(min_dist, dist)
                if neighbor not in visited:
                    dfs(neighbor)
        
        dfs(1)
        return min_dist

public class Solution {
    public int MinScore(int n, int[][] roads) {
        var graph = new List<(int, int)>[n + 1];
        for (int i = 0; i <= n; i++) {
            graph[i] = new List<(int, int)>();
        }
        
        // 构建图
        foreach (var road in roads) {
            int u = road[0], v = road[1], dist = road[2];
            graph[u].Add((v, dist));
            graph[v].Add((u, dist));
        }
        
        var visited = new bool[n + 1];
        int minDist = int.MaxValue;
        
        void Dfs(int node) {
            visited[node] = true;
            foreach (var (neighbor, dist) in graph[node]) {
                minDist = Math.Min(minDist, dist);
                if (!visited[neighbor]) {
                    Dfs(neighbor);
                }
            }
        }
        
        Dfs(1);
        return minDist;
    }
}

var minScore = function(n, roads) {
    const graph = Array(n + 1).fill().map(() => []);
    
    // 构建图
    for (const [u, v, dist] of roads) {
        graph[u].push([v, dist]);
        graph[v].push([u, dist]);
    }
    
    const visited = new Array(n + 1).fill(false);
    let minDist = Infinity;
    
    function dfs(node) {
        visited[node] = true;
        for (const [neighbor, dist] of graph[node]) {
            minDist = Math.min(minDist, dist);
            if (!visited[neighbor]) {
                dfs(neighbor);
            }
        }
    }
    
    dfs(1);
    return minDist;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(V + E)，其中V是城市数量，E是道路数量
空间复杂度O(V + E)，用于存储图和访问标记

相关题目