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 <= 105
• 1 <= roads.length <= 105
• roads[i].length == 3
• 1 <= ai, bi<= n
• ai!= bi
• 1 <= 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,vector<vector<int>>&roads){vector<vector<int>>graph(n+1);vector<int>m(n+1,100000);for(vector<int>&road: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]);}intans=100000;vector<bool>visited(n+1);queue<int>q;q.push(1);visited[1]=true;while(q.size()){inta=q.front();q.pop();for(intb:graph[a]){if(!visited[b]){visited[b]=true;q.push(b);ans=min(ans,m[b]);}}}returnans;}};

C++ —— DFS

/* * @LastEditTime: 2026-07-04 11:02:17 */classSolution{private:intans;vector<bool>visited;vector<vector<pair<int,int>>>graph;voiddfs(intfrom){visited[from]=true;for(auto[to,dis]:graph[from]){ans=min(ans,dis);if(!visited[to]){dfs(to);}}}public:intminScore(intn,vector<vector<int>>&roads){visited=vector<bool>(n+1);graph=vector<vector<pair<int,int>>>(n+1);for(vector<int>&road:roads){graph[road[0]].push_back({road[1],road[2]});graph[road[1]].push_back({road[0],road[2]});}ans=100000;dfs(1);returnans;}};

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源