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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Cost Walk in Weighted Graph

Difficulty: Hard

Problem Description

Given an undirected weighted graph with n vertices and an array of edges, each defined by two vertices and a weight, you need to find the minimum cost of a walk starting at vertex s and ending at vertex t. The cost of the walk is defined as the bitwise AND of the weights of the edges traversed. If no such walk exists, return -1.

Key Insights

  • The cost of the walk is determined by the minimum weight edges traversed through bitwise AND operations.
  • A walk can revisit vertices and edges, which means paths can be explored multiple times to find a minimum cost.
  • The problem requires efficient traversal and representation of the graph due to potentially high limits on n and the number of edges.

Space and Time Complexity

Time Complexity: O(E log E + Q * E) where E is the number of edges and Q is the number of queries, as we need to consider all edges for each query. Space Complexity: O(E + V) where E is the number of edges and V is the number of vertices, for storing the graph representation and auxiliary structures.

Solution

To solve this problem, we can use a combination of graph traversal (like BFS or DFS) along with bit manipulation. The main steps include:

  1. Constructing an adjacency list from the given edges.
  2. Using a priority queue (or a similar structure) to explore paths while keeping track of the minimum AND cost encountered.
  3. For each query, perform the traversal from the starting vertex s to the target vertex t, updating the minimum cost based on the weights of the edges encountered.

Code Solutions

import heapq
from collections import defaultdict

def minCostWalk(n, edges, queries):
    graph = defaultdict(list)
    for u, v, w in edges:
        graph[u].append((v, w))
        graph[v].append((u, w))
    
    results = []
    
    for s, t in queries:
        min_cost = float('inf')
        visited = set()
        heap = [(float('inf'), s)]  # (cost, vertex)

        while heap:
            current_cost, current_vertex = heapq.heappop(heap)
            if current_vertex in visited:
                continue
            visited.add(current_vertex)

            if current_vertex == t:
                min_cost = min(min_cost, current_cost)

            for neighbor, weight in graph[current_vertex]:
                if neighbor not in visited:
                    new_cost = current_cost & weight
                    heapq.heappush(heap, (new_cost, neighbor))

        results.append(min_cost if min_cost != float('inf') else -1)
    
    return results
← Back to All Questions