# Minimum Cost Walk in Weighted Graph
**Difficulty:** HARD
[External](https://leetcode.com/problems/minimum-cost-walk-in-weighted-graph)
Canonical: https://scaleengineer.com/dsa/problems/minimum-cost-walk-in-weighted-graph
**Patterns:** [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Algorithms:** [Union Find](https://scaleengineer.com/algorithms/union-find)
**Data structures:** Array, Graph
**Companies:** [DE Shaw](https://scaleengineer.com/companies/de-shaw)
---
## Problem
There is an undirected weighted graph with `n` vertices labeled from `0` to `n - 1`.

You are given the integer `n` and an array `edges`, where `edges[i] = [ui, vi, wi]` indicates that there is an edge between vertices `ui` and `vi` with a weight of `wi`.

A walk on a graph is a sequence of vertices and edges. The walk starts and ends with a vertex, and each edge connects the vertex that comes before it and the vertex that comes after it. It's important to note that a walk may visit the same edge or vertex more than once.

The **cost** of a walk starting at node `u` and ending at node `v` is defined as the bitwise `AND` of the weights of the edges traversed during the walk. In other words, if the sequence of edge weights encountered during the walk is `w0, w1, w2, ..., wk`, then the cost is calculated as `w0 & w1 & w2 & ... & wk`, where `&` denotes the bitwise `AND` operator.

You are also given a 2D array `query`, where `query[i] = [si, ti]`. For each query, you need to find the minimum cost of the walk starting at vertex `si` and ending at vertex `ti`. If there exists no such walk, the answer is `-1`.

Return _the array_ `answer`_, where_ `answer[i]` _denotes the **minimum** cost of a walk for query_ `i`.

**Example 1:**

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

**Output:** \[1,-1\]

**Explanation:**

![](https://assets.glich.co/dsa/minimum-cost-walk-in-weighted-graph/image0.png) 

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:**

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

**Output:** \[0\]

**Explanation:**

![](https://assets.glich.co/dsa/minimum-cost-walk-in-weighted-graph/image1.png) 

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`

# Approaches
## Brute-Force Traversal per Query
This approach tackles each query independently. The core idea relies on the property of walks in the graph. Since a walk can revisit vertices and edges, if two vertices `s` and `t` are in the same connected component, we can construct a walk that starts at `s`, ends at `t`, and traverses every single edge within that component. The cost of this comprehensive walk is the bitwise AND of all edge weights in the component. Any other walk between `s` and `t` must use a subset of these edges, and the bitwise AND of a subset of numbers is always greater than or equal to the bitwise AND of the full set. Therefore, the minimum possible cost is precisely the bitwise AND of all edge weights within the connected component containing `s` and `t`.

Based on this insight, for each query, we can first find the connected component containing the start and end vertices. If they are not in the same component, no walk is possible. Otherwise, we calculate the bitwise AND of weights of all edges that belong to that component.
**Time:** O(Q * (N + M)), where Q is the number of queries. For each query, building the adjacency list (if not pre-built) and running the traversal takes O(N + M), and calculating the cost takes O(M). · **Space:** O(N + M) per query, where N is the number of vertices and M is the number of edges. This space is used for the adjacency list representation and the visited set.
**Pros:** The logic is straightforward and directly follows from the problem's properties.; It's relatively easy to implement using standard graph traversal algorithms.
**Cons:** The time complexity is very high, making it unsuitable for large inputs as it will likely result in a 'Time Limit Exceeded' error.; It performs a lot of redundant work by re-calculating connected components for each query, even if multiple queries concern the same component.
### Explanation
For each query `(s, t)`, we can run a graph traversal algorithm like Breadth-First Search (BFS) starting from `s`. We use a `Set` to keep track of all visited vertices. The traversal explores the graph, and all vertices it can reach form the connected component of `s`. After the BFS is complete, we check if `t` is in our set of visited vertices. If it's not, no path exists, and the answer is -1.

If `t` is present, we proceed to calculate the cost. We initialize a variable, say `minCost`, to a value where all bits are 1 (e.g., `(1<<30) - 1`). Then, we iterate through every edge in the input `edges` array. For each edge `[u, v, w]`, we check if both its endpoints `u` and `v` are in the set of component nodes we found earlier. If they are, we update our cost: `minCost &= w`. After checking all edges, `minCost` will hold the bitwise AND of all edge weights within the component, which is our answer.

```java
public int[] findAnswer(int n, int[][] edges, int[][] query) {
    int[] answer = new int[query.length];
    List<List<int[]>> adj = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        adj.add(new ArrayList<>());
    }
    for (int[] edge : edges) {
        adj.get(edge[0]).add(new int[]{edge[1], edge[2]});
        adj.get(edge[1]).add(new int[]{edge[0], edge[2]});
    }

    for (int i = 0; i < query.length; i++) {
        int s = query[i][0];
        int t = query[i][1];

        Set<Integer> componentNodes = new HashSet<>();
        Queue<Integer> q = new LinkedList<>();
        
        if (s < n) { // Check to avoid out of bounds if s is invalid
            q.add(s);
            componentNodes.add(s);
        }

        while (!q.isEmpty()) {
            int u = q.poll();
            for (int[] edge : adj.get(u)) {
                int v = edge[0];
                if (!componentNodes.contains(v)) {
                    componentNodes.add(v);
                    q.add(v);
                }
            }
        }

        if (!componentNodes.contains(t)) {
            answer[i] = -1;
            continue;
        }

        int minCost = (1 << 30) - 1;
        for (int[] edge : edges) {
            if (componentNodes.contains(edge[0])) { // Only need to check one endpoint
                minCost &= edge[2];
            }
        }
        answer[i] = minCost;
    }
    return answer;
}
```
### Algorithm
1. For each query `(s, t)`:
2. Perform a graph traversal (like Breadth-First Search or Depth-First Search) starting from vertex `s` to find all reachable vertices. This set of vertices forms the connected component containing `s`.
3. During the traversal, keep track of all visited nodes in a set.
4. After the traversal completes, check if vertex `t` is in the set of visited nodes. If not, it means `s` and `t` are in different components, and no walk exists. The answer for this query is -1.
5. If `t` is reachable, then iterate through all edges `(u, v, w)` of the graph. If both `u` and `v` are part of the discovered connected component, include the weight `w` in a running bitwise AND calculation. The initial value for this calculation should be a number with all relevant bits set to 1.
6. The final result of the bitwise AND operation is the minimum cost for the query.

## Optimized Pre-computation using Disjoint Set Union
The brute-force approach is inefficient because it repeatedly calculates component information. A much more efficient method is to pre-compute the answers for all possible connected components in the graph once, and then answer each query in constant time (or nearly constant time). The Disjoint Set Union (DSU) data structure is ideal for this task. It can efficiently group vertices into components.

The logic remains the same: the minimum cost of a walk between two vertices is the bitwise AND of all edge weights within their shared connected component. We can use DSU to find these components and calculate their associated costs in a single pass before processing any queries.
**Time:** O(M * α(N) + Q * α(N)), where M is the number of edges, Q is the number of queries, and α is the very slow-growing Inverse Ackermann function, making the operations nearly constant time. This is effectively a linear time solution. · **Space:** O(N) for the DSU's parent array and the `componentCosts` array.
**Pros:** Extremely efficient, with a near-linear time complexity.; Processes all queries after a single pre-computation phase, making it ideal for a large number of queries.
**Cons:** Requires knowledge of the Disjoint Set Union (DSU) data structure.; The key insight that the problem simplifies to finding component-wide costs might not be immediately obvious.
### Explanation
First, we use a DSU data structure to determine the connected components. We iterate through all edges `[u, v, w]` and call `dsu.union(u, v)` to merge the sets containing `u` and `v`. After processing all edges, the DSU structure correctly represents the components.

Next, we calculate the minimum cost for each component. We create an array `componentCosts` of size `n`, initialized with a mask of all ones. We iterate through the edges one more time. For each edge `[u, v, w]`, we find the root of the component it belongs to (e.g., `dsu.find(u)`) and update the cost for that root: `componentCosts[root] &= w`. After this loop, `componentCosts[i]` will hold the minimum cost for the component whose root is `i`.

Finally, we can answer all queries efficiently. For each query `[s, t]`, we use the DSU's `find` operation to get the roots of `s` and `t`. If the roots are different, they are not connected, and the answer is -1. If the roots are the same, they are connected, and the answer is the pre-calculated `componentCosts[root]`. This entire process is highly efficient, with the DSU operations taking nearly constant time on average.

```java
class DSU {
    int[] parent;
    public DSU(int n) {
        parent = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
    }
    public int find(int i) {
        if (parent[i] == i) return i;
        return parent[i] = find(parent[i]);
    }
    public void union(int i, int j) {
        int root_i = find(i);
        int root_j = find(j);
        if (root_i != root_j) {
            parent[root_i] = root_j;
        }
    }
}

class Solution {
    public int[] minimumCost(int n, int[][] edges, int[][] query) {
        DSU dsu = new DSU(n);
        for (int[] edge : edges) {
            dsu.union(edge[0], edge[1]);
        }

        int[] componentCosts = new int[n];
        Arrays.fill(componentCosts, (1 << 30) - 1);

        for (int[] edge : edges) {
            int root = dsu.find(edge[0]);
            componentCosts[root] &= edge[2];
        }

        int[] answer = new int[query.length];
        for (int i = 0; i < query.length; i++) {
            int s = query[i][0];
            int t = query[i][1];

            if (s == t) { // Although problem constraints say s_i != t_i
                answer[i] = 0;
                continue;
            }

            int root_s = dsu.find(s);
            int root_t = dsu.find(t);

            if (root_s != root_t) {
                answer[i] = -1;
            } else {
                answer[i] = componentCosts[root_s];
            }
        }
        return answer;
    }
}
```
### Algorithm
1. **Find Components:** Initialize a Disjoint Set Union (DSU) data structure with `n` elements, one for each vertex. Iterate through all the `edges` and for each edge `(u, v, w)`, perform a `union(u, v)` operation. After this step, all vertices in the graph are grouped into their respective connected components.
2. **Calculate Component Costs:** Create an array, say `componentCosts`, of size `n`, and initialize all its values to a number with all bits set to 1 (e.g., `(1<<30)-1`). Iterate through all edges `(u, v, w)` again. For each edge, find the representative (or root) of its component using `dsu.find(u)`. Update the cost for this component by ANDing it with the edge's weight: `componentCosts[root] &= w`.
3. **Process Queries:** Iterate through the `query` array. For each query `(s, t)`:
    a. Find the representatives for `s` and `t`: `root_s = dsu.find(s)` and `root_t = dsu.find(t)`.
    b. If `root_s` is not equal to `root_t`, the vertices are in different components, so no walk exists. The answer is -1.
    c. If the roots are the same, they are in the same component. The minimum cost is the pre-computed value stored for their component's root: `componentCosts[root_s]`.

# Solutions
### Java

```java
class UnionFind { private final int [] p ; private final int [] size ; public UnionFind ( int n ) { p = new int [ n ]; size = new int [ n ]; for ( int i = 0 ; i < n ; ++ i ) { p [ i ] = i ; size [ i ] = 1 ; } } public int find ( int x ) { if ( p [ x ] != x ) { p [ x ] = find ( p [ x ]); } return p [ x ]; } public boolean union ( int a , int b ) { int pa = find ( a ), pb = find ( b ); if ( pa == pb ) { return false ; } if ( size [ pa ] > size [ pb ]) { p [ pb ] = pa ; size [ pa ] += size [ pb ]; } else { p [ pa ] = pb ; size [ pb ] += size [ pa ]; } return true ; } public int size ( int x ) { return size [ find ( x )]; } } class Solution { private UnionFind uf ; private int [] g ; public int [] minimumCost ( int n , int [][] edges , int [][] query ) { uf = new UnionFind ( n ); for ( var e : edges ) { uf . union ( e [ 0 ], e [ 1 ]); } g = new int [ n ]; Arrays . fill ( g , - 1 ); for ( var e : edges ) { int root = uf . find ( e [ 0 ]); g [ root ] &= e [ 2 ]; } int m = query . length ; int [] ans = new int [ m ]; for ( int i = 0 ; i < m ; ++ i ) { int s = query [ i ][ 0 ], t = query [ i ][ 1 ]; ans [ i ] = f ( s , t ); } return ans ; } private int f ( int u , int v ) { if ( u == v ) { return 0 ; } int a = uf . find ( u ), b = uf . find ( v ); return a == b ? g [ a ] : - 1 ; } }
```

### CPP

```cpp
class UnionFind { public: UnionFind ( int n ) { p = vector < int > ( n ); size = vector < int > ( n , 1 ); iota ( p . begin (), p . end (), 0 ); } bool unite ( int a , int b ) { int pa = find ( a ), pb = find ( b ); if ( pa == pb ) { return false ; } if ( size [ pa ] > size [ pb ]) { p [ pb ] = pa ; size [ pa ] += size [ pb ]; } else { p [ pa ] = pb ; size [ pb ] += size [ pa ]; } return true ; } int find ( int x ) { if ( p [ x ] != x ) { p [ x ] = find ( p [ x ]); } return p [ x ]; } int getSize ( int x ) { return size [ find ( x )]; } private: vector < int > p , size ; }; class Solution { public: vector < int > minimumCost ( int n , vector < vector < int >>& edges , vector < vector < int >>& query ) { g = vector < int > ( n , - 1 ); uf = new UnionFind ( n ); for ( auto & e : edges ) { uf -> unite ( e [ 0 ], e [ 1 ]); } for ( auto & e : edges ) { int root = uf -> find ( e [ 0 ]); g [ root ] &= e [ 2 ]; } vector < int > ans ; for ( auto & q : query ) { ans . push_back ( f ( q [ 0 ], q [ 1 ])); } return ans ; } private: UnionFind * uf ; vector < int > g ; int f ( int u , int v ) { if ( u == v ) { return 0 ; } int a = uf -> find ( u ), b = uf -> find ( v ); return a == b ? g [ a ] : - 1 ; } };
```

### Python

```python
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 ]
```