What pattern does Minimum Cost Walk in Weighted Graph use?

It primarily uses the Array plus Bit Manipulation pattern combined with Disjoint Set Union for efficiently handling multiple queries.

Can a walk revisit vertices or edges?

Yes, walks may revisit the same vertex or edge multiple times, which is critical for computing the true minimum cost.

What should I do if two nodes are disconnected?

Return -1 immediately, as no valid walk exists between nodes in different DSU components.

How does bit manipulation help in this problem?

Bit masks represent reachable nodes efficiently, allowing fast updates and minimal cost calculations for all queries.

What are common mistakes in implementing this problem?

Failing to handle revisited edges, ignoring disconnected components, or not using array plus bit manipulation for propagation can all lead to incorrect answers.

#3108

Hard

auto_awesome并查集

LeetCode 题解工作台

带权图里旅途的最小代价

给你一个 n 个节点的带权无向图，节点编号为 0 到 n - 1 。给你一个整数 n 和一个数组 edges ，其中 edges[i] = [u i , v i , w i ] 表示节点 u i 和 v i 之间有一条权值为 w i 的无向边。在图中，一趟旅途包含一系列节点和边。旅途开始和结束点…

数组位运算并查集图

题目描述

给你一个 n 个节点的带权无向图，节点编号为 0 到 n - 1 。

给你一个整数 n 和一个数组 edges ，其中 edges[i] = [u_i, v_i, w_i] 表示节点 u_i 和 v_i 之间有一条权值为 w_i 的无向边。

在图中，一趟旅途包含一系列节点和边。旅途开始和结束点都是图中的节点，且图中存在连接旅途中相邻节点的边。注意，一趟旅途可能访问同一条边或者同一个节点多次。

如果旅途开始于节点 u ，结束于节点 v ，我们定义这一趟旅途的代价是经过的边权按位与 AND 的结果。换句话说，如果经过的边对应的边权为 w₀, w₁, w₂, ..., w_k ，那么代价为w₀ & w₁ & w₂ & ... & w_k ，其中 & 表示按位与 AND 操作。

给你一个二维数组 query ，其中 query[i] = [s_i, t_i] 。对于每一个查询，你需要找出从节点开始 s_i ，在节点 t_i 处结束的旅途的最小代价。如果不存在这样的旅途，答案为 -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 ）。

提示：

1 <= n <= 10⁵
0 <= edges.length <= 10⁵
edges[i].length == 3
0 <= u_i, v_i <= n - 1
u_i != v_i
0 <= w_i <= 10⁵
1 <= query.length <= 10⁵
query[i].length == 2
0 <= s_i, t_i <= n - 1

lightbulb

解题思路

方法一：贪心 + 并查集

我们注意到，一个正整数与其他若干个正整数不断进行“按位与”运算，结果只会越来越小。因此，为了使得旅途的代价尽可能小，我们应该将处于同一个连通分量的所有边的权值进行“按位与”运算，然后再进行查询。

那么，问题转化为，如何找出同一个连通份量的所有边，然后进行“按位与”运算。

我们可以用并查集来维护连通分量。

具体地，我们遍历每一条边 $(u, v, w)$ ，将 $u$ 和 $v$ 进行合并。然后，我们再一次遍历每一条边 $(u, v, w)$ ，找到 $u$ 和 $v$ 所在的连通分量的根节点 $root$ ，用一个数组 $g$ 记录每个连通分量的所有边的权值进行“按位与”运算的结果。

最后，对于每一个查询 $(s, t)$ ，我们首先判断 $s$ 与 $t$ 是否相等，如果相等，那么答案为 $0$ ，否则，我们判断 $s$ 和 $t$ 是否在同一个连通分量中，如果在同一个连通分量中，那么答案为该查询的连通分量的根节点的 $g$ 值，否则，答案为 $-1$ 。

时间复杂度 $O((n + m + q) \times \alpha(n))$ ，空间复杂度 $O(n)$ 。其中 $n$ , $m$ 和 $q$ 分别表示节点数、边数和查询数，而 $\alpha(n)$ 表示 Ackermann 函数的反函数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

class UnionFind:
    def __init__(self, n):
        self.p = list(range(n))
        self.size = [1] * n

    def find(self, x):
        if self.p[x] != x:
            self.p[x] = self.find(self.p[x])
        return self.p[x]

    def union(self, a, b):
        pa, pb = self.find(a), self.find(b)
        if pa == pb:
            return False
        if self.size[pa] > self.size[pb]:
            self.p[pb] = pa
            self.size[pa] += self.size[pb]
        else:
            self.p[pa] = pb
            self.size[pb] += self.size[pa]
        return True


class Solution:
    def minimumCost(
        self, n: int, edges: List[List[int]], query: List[List[int]]
    ) -> List[int]:
        g = [-1] * n
        uf = UnionFind(n)
        for u, v, _ in edges:
            uf.union(u, v)
        for u, _, w in edges:
            root = uf.find(u)
            g[root] &= w

        def f(u: int, v: int) -> int:
            if u == v:
                return 0
            a, b = uf.find(u), uf.find(v)
            return g[a] if a == b else -1

        return [f(s, t) for s, t in query]

speed

复杂度分析

指标	值
时间	complexity is O(m + n + q) because each edge and vertex is processed once during DSU merging and bit mask updates, and each query is answered in constant time using precomputed structures. Space complexity is O(n + m) for storing DSU arrays and bit masks.
空间	O(n + m)

psychology

面试官常问的追问

外企场景

question_mark
Look for usage of Disjoint Set Union with array indices to represent connected components.
question_mark
Expect candidates to optimize repeated path queries with bit manipulation for fast cost computation.
question_mark
Watch for correct handling of walks that can revisit vertices or edges multiple times.

warning

常见陷阱

外企场景

error
Assuming a walk cannot reuse edges or vertices, leading to incorrect minimum costs.
error
Ignoring cases where nodes are disconnected, producing wrong outputs instead of -1.
error
Overcomplicating propagation without using array plus bit manipulation, causing timeouts on large inputs.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Compute minimum cost walks in directed weighted graphs with array plus bit manipulation for strongly connected components.
arrow_right_alt
Limit walk lengths to k edges and use array-based DP with bit masks to find minimum cost.
arrow_right_alt
Handle dynamic edge insertions or deletions while maintaining minimum cost queries using DSU and bit manipulation.

help

常见问题

外企场景

继续练习

#3435 最短公共超序列的字母出现频率 #3493 属性图 #3530 有向无环图中合法拓扑排序的最大利润