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

给你一个正整数 n ，表示总共有 n 个城市，城市从 1 到 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 <= 105
• 1 <= roads.length <= 105
• roads[i].length == 3
• 1 <= ai, bi <= n
• ai != bi
• 1 <= distancei <= 104
• 不会有重复的边。
• 城市 1 和城市 n 之间至少有一条路径。

视频讲解 已出炉，欢迎点赞三连，在评论区分享你对这场周赛的看法~

---

阅读理解题。

由于路径可以折返，取连通块中的 distance}_i 最小的那条边，即为答案。

[sol1-Python3]

class Solution:
    def minScore(self, n: int, roads: List[List[int]]) -> int:
        g = [[] for _ in range(n)]
        for x, y, d in roads:
            g[x - 1].append((y - 1, d))
            g[y - 1].append((x - 1, d))
        ans = inf
        vis = [False] * n
        def dfs(x: int) -> None:
            nonlocal ans
            vis[x] = True
            for y, d in g[x]:
                ans = min(ans, d)
                if not vis[y]:
                    dfs(y)
        dfs(0)
        return ans

[sol1-Go]

func minScore(n int, roads [][]int) int {
	type edge struct{ to, d int }
	g := make([][]edge, n)
	for _, e := range roads {
		x, y, d := e[0]-1, e[1]-1, e[2]
		g[x] = append(g[x], edge{y, d})
		g[y] = append(g[y], edge{x, d})
	}
	ans := math.MaxInt32
	vis := make([]bool, n)
	var dfs func(int)
	dfs = func(x int) {
		vis[x] = true
		for _, e := range g[x] {
			ans = min(ans, e.d)
			if !vis[e.to] {
				dfs(e.to)
			}
		}
	}
	dfs(0)
	return ans
}

func min(a, b int) int { if a > b { return b }; return a }

复杂度分析

• 时间复杂度：O(n+m)，其中 m 为 roads 的长度。
• 空间复杂度：O(n+m)。