LeetCode 2492.两个城市间路径的最小分数：找1所在连通图的最小边(BFS / DFS)

【LetMeFly】2492.两个城市间路径的最小分数找1所在连通图的最小边(BFS / DFS)力扣题目链接https://leetcode.cn/problems/minimum-score-of-a-path-between-two-cities/给你一个正整数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之间至少有一条路径。解题方法找1所在连通图的最小边由于路径可以无限往返所以其实只要和1联通的路径都可以走。由于1一定和n联通所以实际上是找和1联通的节点的所有边中值最小的那条边。解题方法一广度优先搜索(BFS)遍历一遍roads得到邻接表graph其中graph[i]是所有和节点i相邻的节点同时得到节点相邻最小路长m其中m[i]是所有和节点i相邻的路的最短距离。使用一个队列进行广度优先搜索初始时把i入队每出队一个节点就更新答案最小值并把其相邻未入队过的节点入队。解题方法二深度优先搜索(DFS)遍历一遍roads得到邻接表graph其中graph[i]是所有和节点i相邻的(节点, 路的距离)。从节点i开始深度优先搜索遍历每一条与i相邻的路并更新答案最小值若某条路上与i相邻的节点还未遍历过则递归。时空复杂度分析时间复杂度O ( n ) O(n)O(n)空间复杂度O ( n ) O(n)O(n)AC代码C —— BFS/* * LastEditTime: 2026-07-04 10:58:26 */#ifdef_DEBUG#include_[1,2]toVector.h#endifclassSolution{public:intminScore(intn,vectorvectorintroads){vectorvectorintgraph(n1);vectorintm(n1,100000);for(vectorintroad:roads){graph[road[0]].push_back(road[1]);graph[road[1]].push_back(road[0]);m[road[0]]min(m[road[0]],road[2]);m[road[1]]min(m[road[1]],road[2]);}intans100000;vectorboolvisited(n1);queueintq;q.push(1);visited[1]true;while(q.size()){intaq.front();q.pop();for(intb:graph[a]){if(!visited[b]){visited[b]true;q.push(b);ansmin(ans,m[b]);}}}returnans;}};C —— DFS/* * LastEditTime: 2026-07-04 11:02:17 */classSolution{private:intans;vectorboolvisited;vectorvectorpairint,intgraph;voiddfs(intfrom){visited[from]true;for(auto[to,dis]:graph[from]){ansmin(ans,dis);if(!visited[to]){dfs(to);}}}public:intminScore(intn,vectorvectorintroads){visitedvectorbool(n1);graphvectorvectorpairint,int(n1);for(vectorintroad:roads){graph[road[0]].push_back({road[1],road[2]});graph[road[1]].push_back({road[0],road[2]});}ans100000;dfs(1);returnans;}};同步发文于CSDN和我的个人博客原创不易转载经作者同意后请附上原文链接哦~千篇源码题解已开源