We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Cost Walk in Weighted Graph

Number: 3348

Difficulty: Hard

Paid? No

Companies: Google, Microsoft, DE Shaw

Problem Description

Given an undirected weighted graph with n vertices (labeled 0 to n – 1) and an array of edges (each given as [u, v, w]), a walk on the graph is a sequence of vertices and edges (vertices and edges may repeat). The cost of a walk is defined as the bitwise AND (using the & operator) of all of its edge weights. You are also given several queries; each query is a pair [s, t] asking: what is the minimum possible cost that can be obtained by some walk from vertex s to vertex t? If no such walk exists, return –1.

Key Insights

  • A walk may include cycles and extra detours. This means that even if there exists a “direct” s–t path that avoids low bits, we can always detour (go off the direct route and come back) to “force” additional bits to be cleared (changed to 0).
  • For any bit position, if there is at least one edge in the connected component that is missing that bit (i.e. has a 0 in that bit), then it is possible to design an s–t walk that passes through that edge; therefore, that bit can be “cleared” in the final AND.
  • Conversely, if in the entire connected component every edge has a certain bit set then no walk between any two vertices in that component can clear that bit.
  • Hence, for any query (s, t): if s and t are not in the same connected component (using all edges), the answer is –1; otherwise, the minimum achievable cost equals the bitwise AND over all edge weights in that connected component.

Space and Time Complexity

Time Complexity: O(m · α(n)) for union–find processing of the m edges plus an O(m) pass to compute the per–component AND; O(q) for answering q queries. Space Complexity: O(n) for DSU arrays and O(m) to store the edges.

Solution

We use a disjoint–set union (DSU) structure to find the full connected components of the graph (ignoring weights). Once the components are identified, observe that because we can take arbitrarily long walks (repeating vertices and edges as needed), if there exists even one edge in the component whose weight does not have a given bit set then we may “detour” to include it and force that bit to 0 in our overall AND. Therefore, for any component the best (i.e. minimum) cost achievable on any s–t walk is simply the bitwise AND over the weights of all edges present in that component. (If every edge in the component has a certain bit set, then that bit will be forced to 1; otherwise it can be dropped to 0 by including a detour through an edge that is missing that bit.) The query answer is then: • If s and t are not in the same full component, answer –1. • Otherwise, answer = (AND of all edge weights in the component containing s).

The “gotcha” is to realize that because walks are allowed to be arbitrarily long, you are never forced to “pick” only one particular s–t path. Instead, you can always add a detour to lower the AND value, and as a result the minimum cost is completely determined by the properties of the overall connected component.

Code Solutions

# Python solution using DSU (Union Find)
class DSU:
    def __init__(self, n):
        # Parent pointer for each node
        self.parent = list(range(n))
    
    def find(self, a):
        # Path compression find
        if self.parent[a] != a:
            self.parent[a] = self.find(self.parent[a])
        return self.parent[a]
    
    def union(self, a, b):
        # Union two nodes by their roots
        rootA = self.find(a)
        rootB = self.find(b)
        if rootA != rootB:
            self.parent[rootB] = rootA

def minimumCostWalk(n, edges, query):
    dsu = DSU(n)
    # First, union all vertices using all edges (ignoring weight values)
    for u, v, w in edges:
        dsu.union(u, v)
    
    # Initialize a dictionary to store component forced AND
    # Use an initial mask with all bits 1 (covers weights up to 10^5, so 17 bits needed)
    full_mask = (1 << 17) - 1  # 2^17 - 1 = 131071
    comp_and = {}
    
    # For each edge, update the AND for the component it belongs to.
    for u, v, w in edges:
        comp = dsu.find(u)
        if comp in comp_and:
            comp_and[comp] &= w  # update with bitwise AND
        else:
            comp_and[comp] = full_mask & w  # initialize with full_mask & edge weight
    
    # For queries, if s and t belong to same component, answer is the forced AND of that component.
    res = []
    for s, t in query:
        if dsu.find(s) != dsu.find(t):
            res.append(-1)
        else:
            comp = dsu.find(s)
            res.append(comp_and.get(comp, full_mask))
    return res

# Example usage:
if __name__ == '__main__':
    # Example 1:
    n = 5
    edges = [[0,1,7],[1,3,7],[1,2,1]]
    query = [[0,3],[3,4]]
    print(minimumCostWalk(n, edges, query))  # Expected output: [1,-1]
← Back to All Questions