2. Linux.do
  3. Leetcode每日一题 —— 2492. 两个城市间路径的最小分数

Leetcode每日一题 —— 2492. 两个城市间路径的最小分数

魔法师 2026-07-04 08:23 1


思路


题目里说 一条路径可以 多次 包含同一条道路，你也可以沿着路径多次到达城市 1 和城市 n 那么意味着最小距离是具有传染性的，节点联通的所有路径中的最小距离，就是这个连通图的最小分数。

所以问题就变成了检查1所在的连通图中所有边的最小距离。而检查是否连通我们刚好有个适用的算法并查集~

遍历两遍roads，第一遍构造连通图，第二遍检查这条路径是否与1连通，如果连通更新最小分数。

当然也可以在第一遍的时候把最小分数记录下来，第二遍遍历节点。


代码


class Solution {

    private int[] parent;

    public int minScore(int n, int[][] roads) {

        // 并查集初始化

        parent = new int[n + 1];

        for (int i = 1; i <= n; i++) {

            parent[i] = i;

        }

        for (int[] road : roads) {

            union(road[0], road[1]);

        }

        int ans = Integer.MAX_VALUE;

        for (int[] road : roads) {

            if (find(1) == find(road[0])) {

                ans = Math.min(ans, road[2]);

            }

        }

        return ans;

    }

    // 并查集查找（路径压缩）

    private int find(int i) {

        if (parent[i] == i) return i;

        return parent[i] = find(parent[i]);

    }



    // 并查集合并

    private void union(int i, int j) {

        int rootI = find(i);

        int rootJ = find(j);

        if (rootI != rootJ) {

            // 始终让 0 所在的集合作为根

            if (rootI == find(0)) parent[rootJ] = rootI;

            else parent[rootI] = rootJ;

        }

    }

}
最新回复 (3)
  • SomeBottle 07-04 10:24
    1楼

    其实就是一句话：“找城市 1 所在的连通分量中最短的道路距离”


    在用并查集的时候，注意就算两个节点已经连通，也要更新这个连通分量的最小值。


    class Solution {
    
public:
    
    int minScore(int n, vector<vector<int>>& roads) {
    
        // 无向图
    
        // 分数是路径中最小的道路距离
    
        // 1 和 n 之间所有路径的最小分数
    
        // 测试数据保证 1 和 n 连通，那么问题就转换成了 1 所在的连通分量的最小道路距离
    
        // 并查集，就决定是你了！
    
        vector<int> parents(n,-1);
    
        vector<int> sizes(n,1);
    
        // mins 存以某个节点为代表的连通分量中的最小道路距离
    
        vector<int> mins(n,10001);
    
        auto find=[&](auto&&self,int x)->int{
    
            return parents[x]==-1 ? x : parents[x]=self(self,parents[x]);
    
        };
    
        auto merge=[&](int x1,int x2,int dist)->void{
    
            int root1=find(find,x1),root2=find(find,x2);
    
            if(root1==root2){
    
                // 就算根相同，也要更新 dist 最小值，不然结果不对
    
                mins[root1] = min(mins[root1], dist);
    
                return;
    
            }
    
            if(sizes[root1]<sizes[root2]){
    
                // 小树并入大树
    
                swap(root1,root2);
    
            }
    
            parents[root2]=root1;
    
            sizes[root1]+=sizes[root2];
    
            mins[root1]=min(mins[root1],min(mins[root2],dist));
    
        };
    
        for(auto& r:roads){
    
            merge(r[0]-1,r[1]-1,r[2]);
    
        }
    
        return mins[find(find,0)];
    
    }
    
};
  • CPython 07-04 19:39
    2楼

    深度优先就可以


    class Solution:
    
    def minScore(self, n: int, roads: List[List[int]]) -> int:
    
        g = [[] for _ in range(n + 1)]
    
        for u, v, w in roads:
    
            g[u].append((v, w))
    
            g[v].append((u, w))
    
        vis = [False] * (n + 1)
    

    
        ans = inf
    

    
        def dfs(u):
    
            nonlocal ans
    
            vis[u] = True
    
            for v, w in g[u]:
    
                ans = min(ans, w)
    
                if not vis[v]:
    
                    dfs(v)
    
        dfs(1)
    
        return ans
  • Lvvvv 07-04 21:16
    3楼

    周末玩忘了 ^-^。并查集。


    class Solution {
    
public:
    
    int minScore(int n, vector<vector<int>>& roads) {
    
        std::vector<int> p(n + 1,0);
    
        std::iota(p.begin(),p.end(),0);
    
        const int inf = 1e4;
    
        std::vector<int> w(n + 1,inf);
    
        auto find = [&](this auto&& find, int x) -> int {
    
            return x == p[x] ? x : p[x] = find(p[x]);
    
        };
    
        for(const auto& e: roads) {
    
            int a = e[0], b = e[1], dis = e[2];
    
            int pa = find(a), pb = find(b);
    
            if(pa != pb) {
    
                if(w[pa] < w[pb]) {
    
                    p[pb] = pa;
    
                    w[pa] = min(w[pa],dis);
    
                } else {
    
                    p[pa] = pb;
    
                    w[pb] = min(w[pb],dis);
    
                }
    
            } else {
    
                w[pa] =  min(w[pa],dis);
    
            }
    
        }
    
        return w[find(1)];
    
    }
    
};
* 帖子来源Linux.do
附近帖子
返回
飞读
随机推荐