#3108

Hard

LeetCode Problem Workspace

Minimum Cost Walk in Weighted Graph

Find the minimum cost walk in a weighted graph using array and bit manipulation techniques for efficient path calculation.

array bit manipulation union find graph

Problem Statement

You are given an undirected weighted graph with n vertices labeled from 0 to n - 1. Each edge has a weight, and the graph is represented as an array edges where edges[i] = [ui, vi, wi] shows an edge between ui and vi with weight wi. You need to compute the minimum cost walk between pairs of vertices, where a walk can revisit vertices or edges multiple times.

Given multiple queries, each consisting of two vertices, return the minimum possible total weight for a walk connecting them. If no walk exists, return -1. Use array plus bit manipulation to track reachable nodes efficiently and Disjoint Set Union to manage connected components.

Examples

Example 1

Input: n = 5, edges = [[0,1,7],[1,3,7],[1,2,1]], query = [[0,3],[3,4]]

Output: [1,-1]

To achieve the cost of 1 in the first query, we need to move on the following edges: 0->1 (weight 7), 1->2 (weight 1), 2->1 (weight 1), 1->3 (weight 7). In the second query, there is no walk between nodes 3 and 4, so the answer is -1. Example 2:

Example 2

Input: n = 3, edges = [[0,2,7],[0,1,15],[1,2,6],[1,2,1]], query = [[1,2]]

Output: [0]

To achieve the cost of 0 in the first query, we need to move on the following edges: 1->2 (weight 1), 2->1 (weight 6), 1->2 (weight 1).

Constraints

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

Solution Approach

Preprocess Graph with DSU

Initialize a Disjoint Set Union structure to track connected components. Merge vertices connected by any edge using union operations. This helps quickly determine if two vertices are connected before computing minimum walks.

Use Bit Masks for Reachable Nodes

Represent reachable vertices for each component with bit masks stored in arrays. Update masks iteratively using edge weights. This array plus bit manipulation allows efficient propagation of reachable paths and helps compute minimal cost combinations for queries.

Answer Queries Using Preprocessed Data

For each query, first check if the start and end vertices are in the same DSU component. If connected, use the precomputed bit masks and arrays to find the minimal cost walk quickly. If not connected, return -1 immediately, avoiding unnecessary traversal.

Complexity Analysis

Metric	Value
Time	O(m + n + q)
Space	O(n + m)

Time 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.

What Interviewers Usually Probe

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

Common Pitfalls or Variants

Common pitfalls

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

Follow-up variants

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

FAQ

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.

terminal

Solution

Solution 1: Greedy + Union Find

We note that a positive integer performing bitwise AND operation with several other positive integers will only get smaller. Therefore, to minimize the cost of the journey, we should perform bitwise AND operation on the weights of all edges in the same connected component, and then perform the query.

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

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]

Continue Practicing

#3435 frequencies of shortest supersequences #3493 properties graph #3530 maximum profit from valid topological order in dag