3108. 加权图中的最小费用路径

Hard

题目描述

有一个无向加权图，包含 n 个顶点，标记从 0 到 n - 1。

给定整数 n 和数组 edges，其中 edges[i] = [ui, vi, wi] 表示顶点 ui 和 vi 之间有一条权重为 wi 的边。

图上的路径是顶点和边的序列。路径从一个顶点开始，以一个顶点结束，每条边连接它前面的顶点和后面的顶点。需要注意的是，路径可能多次访问同一条边或顶点。

从节点 u 开始到节点 v 结束的路径费用定义为路径中经过的边的权重的按位与。换句话说，如果路径中遇到的边权重序列是 w0, w1, w2, …, wk，那么费用计算为 w0 & w1 & w2 & … & wk，其中 & 表示按位与运算符。

给定一个二维数组 query，其中 query[i] = [si, ti]。对于每个查询，你需要找到从顶点 si 开始到顶点 ti 结束的路径的最小费用。如果不存在这样的路径，答案是 -1。

返回数组 answer，其中 answer[i] 表示查询 i 的路径的最小费用。

示例 1：

输入：n = 5, edges = [[0,1,7],[1,3,7],[1,2,1]], query = [[0,3],[3,4]]
输出：[1,-1]
解释：
要在第一个查询中实现费用为 1，我们需要沿着以下边移动：0->1 (权重 7), 1->2 (权重 1), 2->1 (权重 1), 1->3 (权重 7)。
在第二个查询中，节点 3 和 4 之间没有路径，所以答案是 -1。

示例 2：

输入：n = 3, edges = [[0,2,7],[0,1,15],[1,2,6],[1,2,1]], query = [[1,2]]
输出：[0]
解释：
要在第一个查询中实现费用为 0，我们需要沿着以下边移动：1->2 (权重 1), 2->1 (权重 6), 1->2 (权重 1)。

提示：

2 <= n <= 10^5
0 <= edges.length <= 10^5
edges[i].length == 3
0 <= ui, vi <= n - 1
ui != vi
0 <= wi <= 10^5
1 <= query.length <= 10^5
query[i].length == 2
0 <= si, ti <= n - 1
si != ti

解题思路

这道题的关键在于理解按位与运算的性质：对一个集合中的数字进行按位与运算，结果只会越来越小。这意味着如果两个节点在同一个连通分量中，我们可以通过重复走某些边来让路径费用最小化。

核心观察

连通性判断：如果两个节点不在同一连通分量中，则无路径存在，返回 -1
最小费用计算：如果两个节点连通，由于可以重复经过边，最小费用就是该连通分量中所有边权重的按位与

算法思路

使用并查集来解决这个问题：

用并查集维护图的连通分量
对每个连通分量，计算其中所有边权重的按位与作为该分量的最小费用
对于查询 [s, t]：
- 如果 s 和 t 不在同一分量，返回 -1
- 否则返回该分量的最小费用

为什么这样做是正确的？因为在同一连通分量中，我们总可以构造一条路径，让这条路径经过分量中的每一条边至少一次（通过重复访问），从而达到所有边权重按位与的最小值。

代码实现

class Solution {
public:
    vector<int> minimumCost(int n, vector<vector<int>>& edges, vector<vector<int>>& query) {
        vector<int> parent(n);
        iota(parent.begin(), parent.end(), 0);
        
        function<int(int)> find = [&](int x) {
            return parent[x] == x ? x : parent[x] = find(parent[x]);
        };
        
        auto unite = [&](int x, int y) {
            x = find(x);
            y = find(y);
            if (x != y) parent[y] = x;
        };
        
        unordered_map<int, int> componentCost;
        
        for (auto& edge : edges) {
            int u = edge[0], v = edge[1], w = edge[2];
            unite(u, v);
        }
        
        for (auto& edge : edges) {
            int u = edge[0], v = edge[1], w = edge[2];
            int root = find(u);
            if (componentCost.count(root)) {
                componentCost[root] &= w;
            } else {
                componentCost[root] = w;
            }
        }
        
        vector<int> result;
        for (auto& q : query) {
            int s = q[0], t = q[1];
            if (find(s) != find(t)) {
                result.push_back(-1);
            } else {
                int root = find(s);
                result.push_back(componentCost.count(root) ? componentCost[root] : 0);
            }
        }
        
        return result;
    }
};

class Solution:
    def minimumCost(self, n: int, edges: List[List[int]], query: List[List[int]]) -> List[int]:
        parent = list(range(n))
        
        def find(x):
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]
        
        def unite(x, y):
            px, py = find(x), find(y)
            if px != py:
                parent[py] = px
        
        component_cost = {}
        
        for u, v, w in edges:
            unite(u, v)
        
        for u, v, w in edges:
            root = find(u)
            if root in component_cost:
                component_cost[root] &= w
            else:
                component_cost[root] = w
        
        result = []
        for s, t in query:
            if find(s) != find(t):
                result.append(-1)
            else:
                root = find(s)
                result.append(component_cost.get(root, 0))
        
        return result

public class Solution {
    public int[] MinimumCost(int n, int[][] edges, int[][] query) {
        int[] parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
        
        int Find(int x) {
            return parent[x] == x ? x : parent[x] = Find(parent[x]);
        }
        
        void Unite(int x, int y) {
            int px = Find(x), py = Find(y);
            if (px != py) parent[py] = px;
        }
        
        var componentCost = new Dictionary<int, int>();
        
        foreach (var edge in edges) {
            Unite(edge[0], edge[1]);
        }
        
        foreach (var edge in edges) {
            int u = edge[0], v = edge[1], w = edge[2];
            int root = Find(u);
            if (componentCost.ContainsKey(root)) {
                componentCost[root] &= w;
            } else {
                componentCost[root] = w;
            }
        }
        
        var result = new int[query.Length];
        for (int i = 0; i < query.Length; i++) {
            int s = query[i][0], t = query[i][1];
            if (Find(s) != Find(t)) {
                result[i] = -1;
            } else {
                int root = Find(s);
                result[i] = componentCost.ContainsKey(root) ? componentCost[root] : 0;
            }
        }
        
        return result;
    }
}

var minimumCost = function(n, edges, query) {
    const parent = Array.from({length: n}, (_, i) => i);
    
    function find(x) {
        return parent[x]

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

项目	复杂度
时间复杂度	O(E·α(n) + Q·α(n))
空间复杂度	O(n + C)

其中：

E 是边数，Q 是查询数，n 是节点数，C 是连通分量数
α(n) 是反阿克曼函数，在实际应用中可视为常数
空间复杂度中的 C 通常远小于 n

题目描述#

解题思路#

核心观察#

算法思路#

代码实现#

复杂度分析#