Minimum Cost Walk in Weighted Graph
Source: leetcode
Difficulty: Hard
Tags: array, bit-manipulation, union-find, graph

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.leetcode.com/uploads/2024/01/31/q4_example1-1.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.leetcode.com/uploads/2024/01/31/q4_example2e.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`




C++ solution:
/*
My Intuition -
I think bitwise `AND` of 2 operands will always result in a number that is `<=` both operands. So if problem asks you to minimize result of multiple `AND` operation, then you would want to take all operands as much as possible.

"It's important to note that a walk may visit the same edge or vertex more than once." implies AND operation of all edges in a connected component.

So we use DSU.

Now question is how to get the ANDResult of a component. The way I initially thought was to store result of ANDResult at parent level and when performing Union, I get ANDResult from both u and v and put & it to new parent of (u,v) after Union.

The constraints say that s!=t, but if that was not the case then when s==t, min cost = 0.
*/
// modified DSU
const int speedup = [] { ios::sync_with_stdio(0); cin.tie(0); return 0; }();
class DSU {
    public:
    vector<int> parent,size,ANDResult;
    DSU(int n){
        parent.resize(n);
        iota(parent.begin(),parent.end(),0);
        size.resize(n,1);
        ANDResult.resize(n,-1);     // -1 has all bits set to 1
    }
    int Find(int v){
        if(parent[v]==v)
            return v;
        return parent[v] = Find(parent[v]);
    }
    void Union(int a, int b){
        a=Find(a);
        b=Find(b);
        if(a==b) return;
        if(size[a]<size[b])
            swap(a,b);
        parent[b]=a;
        size[a]+=size[b];
        ANDResult[a]&=ANDResult[b];
    }
};
class Solution {
public:
    vector<int> minimumCost(int n, vector<vector<int>>& edges, vector<vector<int>>& query) {
        int q=query.size();
        DSU dsu(n);
        vector<int> answer(q,-1);
        for(auto &edge:edges){
            int u=edge[0], v=edge[1], w=edge[2];
            dsu.Union(u,v);
            int p=dsu.Find(u);
            dsu.ANDResult[p]&=w;
        }
        for(int i=0;i<q;i++){
            int s=query[i][0], t=query[i][1];
            if(dsu.Find(s)!=dsu.Find(t)) continue;
            answer[i]=dsu.ANDResult[dsu.Find(s)];
        }
        return answer;
    }
};
/*
// Initial implementation
class DSU {
    public:
    vector<int> parent,size;
    DSU(int n){
        parent.resize(n);
        iota(parent.begin(),parent.end(),0);
        size.resize(n,1);
    }
    int Find(int v){
        if(parent[v]==v)
            return v;
        return parent[v] = Find(parent[v]);
    }
    void Union(int a, int b){
        a=Find(a);
        b=Find(b);
        if(a==b) return;
        if(size[a]<size[b])
            swap(a,b);
        parent[b]=a;
        size[a]+=size[b];
    }
};
class Solution {
public:
    vector<int> minimumCost(int n, vector<vector<int>>& edges, vector<vector<int>>& query) {
        int q=query.size();
        DSU dsu(n);
        vector<int> answer(q,-1);
        vector<int> ANDResult(n,-1);
        for(auto &edge:edges){
            int u=edge[0], v=edge[1], w=edge[2];
            if(ANDResult[dsu.Find(u)]!=-1) w&=ANDResult[dsu.Find(u)];
            if(ANDResult[dsu.Find(v)]!=-1) w&=ANDResult[dsu.Find(v)];
            dsu.Union(u,v);
            int p=dsu.Find(u);
            if(ANDResult[p]==-1) ANDResult[p]=w;
            else ANDResult[p]&=w;
        }
        for(int i=0;i<q;i++){
            int s=query[i][0], t=query[i][1];
            if(dsu.Find(s)!=dsu.Find(t)) continue;
            answer[i]=ANDResult[dsu.Find(s)];
        }
        return answer;
    }
};
*/

Go solution:
func minimumCost(n int, edges, query [][]int) []int {
	type edge struct{ to, w int }
	g := make([][]edge, n)
	for _, e := range edges {
		x, y, w := e[0], e[1], e[2]
		g[x] = append(g[x], edge{y, w})
		g[y] = append(g[y], edge{x, w})
	}

	ids := make([]int, n) 
	for i := range ids {
		ids[i] = -1
	}
	ccAnd := []int{} 
	var dfs func(int) int
	dfs = func(x int) int {
		ids[x] = len(ccAnd) 
		and := -1
		for _, e := range g[x] {
			and &= e.w
			if ids[e.to] < 0 {
				and &= dfs(e.to)
			}
		}
		return and
	}
	for i, id := range ids {
		if id < 0 { // 没有访问过
			ccAnd = append(ccAnd, dfs(i))
		}
	}

	ans := make([]int, len(query))
	for i, q := range query {
		s, t := q[0], q[1]
		if s == t {
			continue
		}
		if ids[s] != ids[t] {
			ans[i] = -1
		} else {
			ans[i] = ccAnd[ids[s]]
		}
	}
	return ans
}

Java solution:
class Solution {
    public int[] minimumCost(int n, int[][] edges, int[][] query) {
        List<int[]>[] g = new ArrayList[n];
        Arrays.setAll(g, i -> new ArrayList<>());
        for (int[] e : edges) {
            int x = e[0], y = e[1], w = e[2];
            g[x].add(new int[]{y, w});
            g[y].add(new int[]{x, w});
        }

        int[] ids = new int[n];
        Arrays.fill(ids, -1);
        List<Integer> ccAnd = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (ids[i] < 0) {
                ccAnd.add(dfs(i, ccAnd.size(), g, ids));
            }
        }

        int[] ans = new int[query.length];
        for (int i = 0; i < query.length; i++) {
            int s = query[i][0], t = query[i][1];
            ans[i] = s == t ? 0 : ids[s] != ids[t] ? -1 : ccAnd.get(ids[s]);
        }
        return ans;
    }

    private int dfs(int x, int curId, List<int[]>[] g, int[] ids) {
        ids[x] = curId;
        int and = -1;
        for (int[] e : g[x]) {
            and &= e[1];
            if (ids[e[0]] < 0) {
                and &= dfs(e[0], curId, g, ids);
            }
        }
        return and;
    }
}

JavaScript solution:
/**
 * @param {number} numberOfNodes
 * @param {number[][]} edges
 * @param {number[][]} queries
 * @return {number[]}
 */
var minimumCost = function (numberOfNodes, edges, queries) {
    this.NO_PATH_FOUND = -1;
    const unionFind = new UnionFind(numberOfNodes);
    const minCostToReachParent = createMinCostToReachParent(unionFind, numberOfNodes, edges);
    return createMinCostPerQuery(unionFind, minCostToReachParent, queries);
};

/**
 * @param {UnionFind} unionFind
 * @param {number} numberOfNodes
 * @param {number[][]} edges
 * @return {number[]}
 */
function createMinCostToReachParent(unionFind, numberOfNodes, edges) {
    const minCostToReachParent = new Array(numberOfNodes).fill(Number.MAX_SAFE_INTEGER);

    for (let edge of edges) {
        const parentFirst = unionFind.findParent(edge[0]);
        const parentSecond = unionFind.findParent(edge[1]);
        const cost = edge[2];

        minCostToReachParent[parentFirst] &= cost & minCostToReachParent[parentSecond];
        minCostToReachParent[parentSecond] &= cost & minCostToReachParent[parentFirst];

        if (parentFirst !== parentSecond) {
            unionFind.joinByRank(parentFirst, parentSecond);
        }
    }
    return minCostToReachParent;
}

/**
 * @param {UnionFind} unionFind
 * @param {number[]} minCostToReachParent
 * @param {number[][]} queries
 * @return {number[]}
 */
function  createMinCostPerQuery(unionFind, minCostToReachParent, queries) {
    const minCostPerQuery = new Array(queries.length);

    for (let i = 0; i < queries.length; ++i) {
        const parentFirst = unionFind.findParent(queries[i][0]);
        const parentSecond = unionFind.findParent(queries[i][1]);

        if (parentFirst !== parentSecond) {
            minCostPerQuery[i] = this.NO_PATH_FOUND;
        } else {
            minCostPerQuery[i] = minCostToReachParent[parentFirst];
        }
    }

    return minCostPerQuery;
}

class UnionFind {

    #rank
    #parent

    /**
     * @param {number} numberOfNodes
     */
    constructor(numberOfNodes) {
        this.#rank = new Array(numberOfNodes).fill(0);
        this.#parent = new Array(numberOfNodes).fill(0);
        // Alternatively: this.parent = Array.from(Array(numberOfNodes).keys());
        for (let node = 0; node < numberOfNodes; ++node) {
            this.#parent[node] = node;
        }
    }

    /**
     * @param {number} node
     * @return {number}
     */
    findParent(node) {
        while (this.#parent[node] !== node) {
            node = this.#parent[node];
        }
        return this.#parent[node];
    }

    /**
     * @param {number} firstNode
     * @param {number} secondNode
     * @return {void}
     */
    joinByRank(firstNode, secondNode) {
        if (this.#rank[firstNode] >= this.#rank[secondNode]) {
            this.#parent[secondNode] = firstNode;
            this.#rank[firstNode] += this.#rank[secondNode] + 1;
        } else {
            this.#parent[firstNode] = secondNode;
            this.#rank[secondNode] += this.#rank[firstNode] + 1;
        }
    }
}

Python solution:
class Solution:
    def minimumCost(self, n: int, edges: List[List[int]], query: List[List[int]]) -> List[int]:
        parents = list(range(n))
        weights = [(1<<31)-1] * n

        def find(x: int) -> int:
            if parents[x] != x:
                parents[x] = find(parents[x])
            return parents[x]
        
        def union(x: int, y: int, w: int) -> None:
            px, py = find(x), find(y)
            parents[py] = px
            weights[px] &= weights[py] & w
        
        def get_weight(x: int, y: int) -> int:
            if x == y: return 0
            px, py = find(x), find(y)
            if px != py:
                return -1
            return weights[px]
        
        for u, v, w in edges:
            union(u, v, w)
        
        return [get_weight(u, v) for u, v in query]

Ruby solution:
def minimum_cost(n, edges, query)
  parent = (0...n).to_a
  size = Array.new(n, 1)
  and_val = Array.new(n, -1)

  find = lambda do |u|
    while parent[u] != u
      parent[u] = parent[parent[u]]
      u = parent[u]
    end
    u
  end

  edges.each do |u, v, w|
    root_u = find.call(u)
    root_v = find.call(v)

    if root_u != root_v
      if size[root_u] < size[root_v]
        root_u, root_v = root_v, root_u
      end
      parent[root_v] = root_u
      size[root_u] += size[root_v]
      and_val[root_u] &= and_val[root_v] & w
    else
      and_val[root_u] &= w
    end
  end

  query.map do |s, t|
    root_s = find.call(s)
    root_t = find.call(t)
    root_s == root_t ? and_val[root_s] : -1
  end
end