目标
给你一个正整数 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 <= 10^5
- 1 <= roads.length <= 10^5
- roads[i].length == 3
- 1 <= ai, bi <= n
- ai != bi
- 1 <= distancei <= 10^4
- 不会有重复的边。
- 城市 1 和城市 n 之间至少有一条路径。
思路
单源最短路径，可以使用 Dijkstra 算法。但是需要注意，这里求的不是路径和的最小值，而是从城市 1 出发，每段路径的最小值。
从城市 1 开始 dfs 访问所能到达的城市，记录路径中的最小值。需要注意，虽然城市可能已访问过，但是边仍可能是未处理的，比如 1 -> 2 -> 3 -> 1，3 -> 1 这条路径也应该参与最终结果的计算，因此需要先比较再判断是否访问过。
代码
/**
* @date 2026-07-06 11:35
*/
public class MinScore2492 {
public int minScore(int n, int[][] roads) {
List<int[]>[] g = new List[n + 1];
Arrays.setAll(g, x -> new ArrayList<>());
for (int[] road : roads) {
g[road[0]].add(new int[]{road[1], road[2]});
g[road[1]].add(new int[]{road[0], road[2]});
}
boolean[] visited = new boolean[n + 1];
return dfs(1, g, visited);
}
public int dfs(int cur, List<int[]>[] g, boolean[] visited) {
int res = Integer.MAX_VALUE;
visited[cur] = true;
for (int[] next : g[cur]) {
res = Math.min(res, next[1]);
if (visited[next[0]]) {
continue;
}
res = Math.min(dfs(next[0], g, visited), res);
}
return res;
}
}
性能
