当前位置：首页 > news >正文

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

news 2026/7/5 6:39:29

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

力扣题目链接：https://leetcode.cn/problems/minimum-score-of-a-path-between-two-cities/

给你一个正整数n，表示总共有n个城市，城市从1到n编号。给你一个二维数组roads，其中roads[i] = [a_i, b_i, distance_i]表示城市a_i和b_i之间有一条双向道路，道路距离为distance_i。城市构成的图不一定是连通的。

两个城市之间一条路径的分数定义为这条路径中道路的最小距离。

返回城市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⁵
1 <= roads.length <= 10⁵
roads[i].length == 3
1 <= a_i, b_i<= n
a_i!= b_i
1 <= distance_i<= 10⁴
不会有重复的边。
城市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;}};