LeetCode 题解工作台
两个城市间路径的最小分数
给你一个正整数 n ，表示总共有 n 个城市，城市从 1 到 n 编号。给你一个二维数组 roads ，其中 roads[i] = [a i , b i , distance i ] 表示城市 a i 和 b i 之间有一条 双向 道路，道路距离为 distance i 。城市构成的图不一定是连通的…
4
题型
7
代码语言
3
相关题
当前训练重点
中等 · 图·DFS·traversal
答案摘要
根据题目描述，每条边可以经过多次，并且保证节点 和节点 在同一个连通块中。因此，题目实际上求的是节点 所在的连通块的最小边。我们可以用 DFS，从节点 开始搜索所有的边，找到最小的边即可。 时间复杂度 $O(n + m)$。其中 和 分别是节点数和边数。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 图·DFS·traversal 题型思路
题目描述
给你一个正整数 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 <= 1051 <= roads.length <= 105roads[i].length == 31 <= ai, bi <= nai != bi1 <= distancei <= 104- 不会有重复的边。
- 城市
1和城市n之间至少有一条路径。
解题思路
方法一：DFS
根据题目描述，每条边可以经过多次，并且保证节点 和节点 在同一个连通块中。因此，题目实际上求的是节点 所在的连通块的最小边。我们可以用 DFS，从节点 开始搜索所有的边，找到最小的边即可。
时间复杂度 。其中 和 分别是节点数和边数。
class Solution:
def minScore(self, n: int, roads: List[List[int]]) -> int:
def dfs(i):
nonlocal ans
for j, d in g[i]:
ans = min(ans, d)
if not vis[j]:
vis[j] = True
dfs(j)
g = defaultdict(list)
for a, b, d in roads:
g[a].append((b, d))
g[b].append((a, d))
vis = [False] * (n + 1)
ans = inf
dfs(1)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity depends on the chosen traversal: DFS or BFS is O(n + m) where n is the number of cities and m is the number of roads. Union Find can approach near-linear with path compression. Space complexity is O(n + m) for adjacency lists or Union Find structures. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Are you considering all reachable paths to capture the true minimum distance?
- question_mark
Can you handle disconnected components without missing valid paths?
- question_mark
Have you thought about optimizing repeated minimum checks using Union Find?
常见陷阱
外企场景- error
Failing to track the global minimum across all valid paths, leading to an incorrect score.
- error
Not marking visited cities in DFS, which can create infinite loops or repeated paths.
- error
Assuming the graph is fully connected and ignoring edge cases where only certain nodes are reachable.
进阶变体
外企场景- arrow_right_alt
Compute maximum score along any path instead of minimum, flipping the edge comparison logic.
- arrow_right_alt
Find minimum score between multiple city pairs, requiring repeated traversals or component precomputation.
- arrow_right_alt
Add weight constraints on roads, requiring filtered traversal and dynamic minimum updates.