Minimum Cost Walk in Weighted Graph

hard graph union find bitwise

Problem

An undirected graph has weighted edges [u, v, w]. The cost of a walk is the bitwise AND of the weights of all edges traversed (edges may be repeated, and each repeat is counted). For each query [s, t], return the minimum walk cost from s to t, or −1 if they are not connected.

Because ANDing in more edges can only clear bits, the cheapest walk uses every edge of the component: the answer is the AND of all edge weights inside the connected component shared by s and t.

Inputn = 5, edges = [[0,1,7],[0,1,15],[1,2,6],[1,2,1]], queries = [[1,2],[0,3]]

Output[0, -1]

Component {0,1,2} AND = 7&15&6&1 = 0, so query (1,2) → 0. Node 3 is isolated, so (0,3) → −1.

edges (u,v,w;...)

queries (s,t;...)

def min_cost_walk(n, edges, query):
    parent = list(range(n))
    cost = [-1] * n  # AND of all edge weights in the component (all bits set initially)
    for i in range(n):
        cost[i] = -1  # -1 = all bits 1 in two's complement
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x
    for u, v, w in edges:
        ru, rv = find(u), find(v)
        if ru != rv:
            parent[ru] = rv
            cost[rv] &= cost[ru]
        cost[find(u)] &= w
    ans = []
    for s, t in query:
        if s == t:
            ans.append(0)
        elif find(s) != find(t):
            ans.append(-1)
        else:
            ans.append(cost[find(s)])
    return ans

function minCostWalk(n, edges, query) {
  const parent = Array.from({ length: n }, (_, i) => i);
  const cost = new Array(n).fill(-1); // -1 = all bits set
  function find(x) {
    while (parent[x] !== x) { parent[x] = parent[parent[x]]; x = parent[x]; }
    return x;
  }
  for (const [u, v, w] of edges) {
    const ru = find(u), rv = find(v);
    if (ru !== rv) { parent[ru] = rv; cost[rv] &= cost[ru]; }
    cost[find(u)] &= w;
  }
  return query.map(([s, t]) => {
    if (s === t) return 0;
    if (find(s) !== find(t)) return -1;
    return cost[find(s)];
  });
}

class Solution {
    int[] parent;
    int find(int x) {
        while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; }
        return x;
    }
    public int[] minimumCost(int n, int[][] edges, int[][] query) {
        parent = new int[n];
        int[] cost = new int[n];
        for (int i = 0; i < n; i++) { parent[i] = i; cost[i] = -1; }
        for (int[] e : edges) {
            int ru = find(e[0]), rv = find(e[1]);
            if (ru != rv) { parent[ru] = rv; cost[rv] &= cost[ru]; }
            cost[find(e[0])] &= e[2];
        }
        int[] ans = new int[query.length];
        for (int i = 0; i < query.length; i++) {
            int s = query[i][0], t = query[i][1];
            if (s == t) ans[i] = 0;
            else if (find(s) != find(t)) ans[i] = -1;
            else ans[i] = cost[find(s)];
        }
        return ans;
    }
}

class Solution {
public:
    vector<int> parent;
    int find(int x) {
        while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; }
        return x;
    }
    vector<int> minimumCost(int n, vector<vector<int>>& edges, vector<vector<int>>& query) {
        parent.resize(n);
        vector<int> cost(n, -1);
        for (int i = 0; i < n; i++) parent[i] = i;
        for (auto& e : edges) {
            int ru = find(e[0]), rv = find(e[1]);
            if (ru != rv) { parent[ru] = rv; cost[rv] &= cost[ru]; }
            cost[find(e[0])] &= e[2];
        }
        vector<int> ans;
        for (auto& q : query) {
            int s = q[0], t = q[1];
            if (s == t) ans.push_back(0);
            else if (find(s) != find(t)) ans.push_back(-1);
            else ans.push_back(cost[find(s)]);
        }
        return ans;
    }
};

Explanation

The cost of a walk is the bitwise AND of every edge weight it crosses, counting repeats. The crucial property of AND is that adding more numbers can only turn bits off, never on. So a longer walk is never more expensive than a shorter one.

Since revisiting edges is allowed and free to add, the cheapest walk between two connected nodes can traverse every edge of their connected component. Therefore the answer for any reachable pair is fixed: the AND of all edge weights in that component.

We compute those per-component ANDs with a union-find. Each component root stores a running cost, started at -1 (all bits set, the identity for AND). As we add each edge we merge its endpoints and fold its weight into the root with cost &= w. When two components merge, we AND their accumulated costs together too.

For a query (s, t): if s == t the walk is empty so the cost is 0; if they sit in different components the answer is -1; otherwise it is the stored AND of their shared root.

Example: edges 7, 15, 6, 1 all live in component {0,1,2}. Their AND is 7 & 15 & 6 & 1 = 0, so query (1,2) returns 0. Node 3 is isolated, so query (0,3) returns -1 → [0, -1].

Time: O((E + Q) · α(n)) Space: O(n)