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)$

AC代码

C++ —— BFS

/*
 * @LastEditTime: 2026-07-04 10:58:26
 */
#ifdef _DEBUG
#include "_[1,2]toVector.h"
#endif

class Solution {
public:
    int minScore(int n, 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]);
        }
        
        int ans = 100000;
        vector<bool> visited(n + 1);
        queue<int> q;
        q.push(1);
        visited[1] = true;
        while (q.size()) {
            int a = q.front();
            q.pop();
            for (int b: graph[a]) {
                if (!visited[b]) {
                    visited[b] = true;
                    q.push(b);
                    ans = min(ans, m[b]);
                }
            }
        }
        return ans;
    }
};

C++ —— DFS

/*
 * @LastEditTime: 2026-07-04 11:02:17
 */
class Solution {
private:
    int ans;
    vector<bool> visited;
    vector<vector<pair<int, int>>> graph;

    void dfs(int from) {
        visited[from] = true;
        for (auto [to, dis] : graph[from]) {
            ans = min(ans, dis);
            if (!visited[to]) {
                dfs(to);
            }
        }
    }
public:
    int minScore(int n, 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);
        return ans;
    }
};

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

千篇源码题解已开源