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

难度: Medium

给你一个正整数 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 之间至少有一条路径。

Submission

运行时间: 203 ms

内存: 49.9 MB

class Unionfind:
    def __init__(self,size):
        self.fa=[None]*size
    def find(self,i):
        if self.fa[i] is None:
            return i
        self.fa[i]=self.find(self.fa[i])
        return self.fa[i]
    def is_connected(self,x,y):
        return self.find(x)==self.find(y)
    def merge(self,x,y):
        f_x,f_y=self.find(x),self.find(y)
        if f_x!=f_y:
           self.fa[f_x]=f_y
class Solution:
    def minScore(self, n: int, roads: List[List[int]]) -> int:
        u=Unionfind(n)
        for x,y,z in roads:
            u.merge(x-1,y-1)
        root=u.find(0)
        v=[0]*n
        v[0]=1
        for i in range(1,n):
            if u.find(i)==root:
                v[i]=1
        ans=inf
        for x,y,z in roads:
            if v[x-1]&v[y-1]==1:
                ans=min(ans,z)
        return ans

Explain

该题解采用了并查集来判断城市之间的连通性。首先，使用并查集结构初始化所有城市，然后按照给定的道路信息将城市合并，构建联通分量。通过遍历所有城市，检查每个城市是否与起点城市1（编号0）在同一个连通分量中。然后，检查所有道路，只有当道路的两端城市都与起点城市在同一个连通分量中时，才考虑该道路的距离。最后，求得这些道路中距离的最小值，即为城市1到城市n之间路径的最小分数。

时间复杂度: O(n + m)

空间复杂度: O(n)

class Unionfind:
    def __init__(self,size):
        self.fa=[None]*size  # 初始化并查集，每个节点的父节点初始化为None
    def find(self,i):
        if self.fa[i] is None:
            return i  # 如果节点i的父节点是None，说明它是根节点
        self.fa[i]=self.find(self.fa[i])  # 路径压缩，直接指向根节点
        return self.fa[i]
    def is_connected(self,x,y):
        return self.find(x)==self.find(y)  # 判断两个节点是否连通
    def merge(self,x,y):
        f_x,f_y=self.find(x),self.find(y)
        if f_x!=f_y:
           self.fa[f_x]=f_y  # 将两个不同连通分量的根节点合并

class Solution:
    def minScore(self, n: int, roads: List[List[int]]) -> int:
        u=Unionfind(n)
        for x,y,z in roads:
            u.merge(x-1,y-1)  # 遍历道路信息，将道路两端的城市合并到同一连通分量
        root=u.find(0)  # 找到城市1的根节点
        v=[0]*n
        v[0]=1
        for i in range(1,n):
            if u.find(i)==root:
                v[i]=1  # 标记所有与城市1在同一个连通分量的城市
        ans=inf
        for x,y,z in roads:
            if v[x-1]&v[y-1]==1:
                ans=min(ans,z)  # 检查道路两端的城市，如果都与城市1连通，更新最小距离
        return ans  # 返回最小距离值

Explore

并查集是一种高效的数据结构，用来处理动态连通性问题。在处理非连通图时，它依然保持高效，因为并查集的主要操作，即`find`和`merge`，其时间复杂度近似为常数时间（均摊复杂度为O(α(n))，其中α是阿克曼函数的反函数，增长非常慢）。即使图分为多个连通分量，每次操作仍然非常快速。因此，使用并查集检查图的连通性，无论图是否完全连通，都是有效且效率高的方法。

在并查集中，`merge`函数的主要作用是合并两个元素所在的连通分量。对于多条连接相同城市对的道路，即使多次执行`merge`操作，也不会影响结果的正确性。这是因为一旦两个城市通过某条道路连接后，它们属于同一个连通分量，后续的`merge`操作尝试将它们再次合并时，检测到它们已经在同一个连通分量中，操作会简单地忽略这一事实，不会有任何副作用。因此，并查集可以正确处理重复边，保证连通性的同时避免错误的重复合并。

使用数组`v`来标记与城市1在同一连通分量的城市具有预处理的优点。一旦完成标记，对于每条道路的连通性检查就变得非常快速，只需检查两个城市是否都被标记为连通即可，这是O(1)的操作。相比之下，如果在遍历中直接检查连通性，则每次都需要调用并查集的`find`方法，尽管这也是高效的，但相比于直接访问数组，还是稍慢一些。不过，使用数组需要额外的空间，并且在初始化阶段需要额外的遍历，这在某些情况下可能是缺点。

题解中返回的最小距离只是考虑了所有与城市1直接或间接连通的道路中的最小值，并没有考虑道路的组合或多段路径的可能性。这意味着，如果城市1到城市n间的最优路径涉及多条道路的组合，该解法可能不会返回真正的最小分数。要确保找到真正的最小分数，通常需要使用如Dijkstra或Floyd-Warshall等算法来考虑所有可能的路径和道路组合，确保找到从城市1到城市n的最短路径。因此，题解中的方法在某些情况下可能不返回最佳结果。