Minimum Cost Walk in Weighted Graph - Practice Coding Problems

Minimum Cost Walk in Weighted Graph - 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] = [u_i, v_i, w_i] indicates that there is an edge between vertices u_i and v_i with a weight of w_i.

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 w₀, w₁, w₂, ..., w_k, then the cost is calculated as w₀ & w₁ & w₂ & ... & w_k, where & denotes the bitwise AND operator.

You are also given a 2D array query, where query[i] = [s_i, t_i]. For each query, you need to find the minimum cost of the walk starting at vertex s_i and ending at vertex t_i. 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.

Input & Output

Example 1 — Basic Connected Graph

$ Input: n = 5, edges = [[0,1,7],[1,3,7],[1,2,1]], query = [[0,3],[3,0],[0,2]]

› Output: [1,1,1]

💡 Note: Nodes 0,1,2,3 are connected. The minimum cost between any two is the AND of all edge weights: 7 & 7 & 1 = 1. Node 4 is isolated.

Example 2 — Multiple Components

$ Input: n = 3, edges = [[0,1,15],[1,2,6]], query = [[0,2]]

› Output: [6]

💡 Note: All nodes are connected in one component. Minimum cost is 15 & 6 = 6.

Example 3 — No Path Exists

$ Input: n = 3, edges = [[0,1,4]], query = [[0,2]]

› Output: [-1]

💡 Note: Node 2 is isolated from nodes 0 and 1, so no path exists.

Constraints

1 ≤ n ≤ 10⁵
0 ≤ edges.length ≤ 10⁵
edges[i].length == 3
0 ≤ u_i, v_i ≤ n - 1
u_i ≠ v_i
0 ≤ w_i ≤ 10⁵
1 ≤ query.length ≤ 10⁴
query[i].length == 2
0 ≤ s_i, t_i ≤ n - 1

Visualization

Tap to expand

Understanding the Visualization

Input Graph

Weighted undirected graph with n vertices and edges

Connected Components

Group vertices that can reach each other

Minimum Cost

Bitwise AND of all edges in component

Key Takeaway

🎯 Key Insight: Since walks can repeat edges, the minimum cost between any two nodes in a connected component is the bitwise AND of ALL edge weights in that component

Asked in

G Google 35 f Meta 28 a Amazon 22

The key insight is that in a connected component, you can traverse any edge multiple times, so the minimum cost is the bitwise AND of ALL edges in that component. Best approach uses Union-Find to identify connected components efficiently. Time: O(E × α(V) + Q), Space: O(V)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force DFS	O(Q × 2^E)	O(V)	For each query, use DFS to explore all possible paths and track minimum cost
Union-Find with Connected Components	O(E × α(V) + Q)	O(V)	Use Union-Find to group connected vertices, then compute minimum AND for each component

Brute Force DFS — Algorithm Steps

For each query, start DFS from source node
Explore all neighbors, updating current cost with bitwise AND
When reaching destination, update minimum cost
Return minimum cost found or -1 if unreachable

Visualization

Tap to expand

Step-by-Step Walkthrough

Start DFS

Begin from source node with initial cost

Explore Paths

Recursively visit all neighbors, updating cost with bitwise AND

Track Minimum

When reaching destination, update minimum cost found

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

#define MAX_N 1000
#define MAX_EDGES 2000

typedef struct {
    int to, weight;
} Edge;

Edge graph[MAX_N][MAX_EDGES];
int graphSize[MAX_N];
int visited[MAX_N][MAX_N];

int dfs(int node, int target, int currentCost) {
    if (node == target) {
        return currentCost;
    }
    
    int minCost = INT_MAX;
    for (int i = 0; i < graphSize[node]; i++) {
        int nextNode = graph[node][i].to;
        int weight = graph[node][i].weight;
        
        if (!visited[node][nextNode]) {
            visited[node][nextNode] = 1;
            visited[nextNode][node] = 1;
            int newCost = currentCost & weight;
            int result = dfs(nextNode, target, newCost);
            if (result != -1 && result < minCost) {
                minCost = result;
            }
            visited[node][nextNode] = 0;
            visited[nextNode][node] = 0;
        }
    }
    
    return minCost == INT_MAX ? -1 : minCost;
}

int* solution(int n, int edges[][3], int edgesSize, int query[][2], int querySize, int* returnSize) {
    *returnSize = querySize;
    int* answer = (int*)malloc(querySize * sizeof(int));
    
    // Initialize graph
    memset(graphSize, 0, sizeof(graphSize));
    
    // Build adjacency list
    for (int i = 0; i < edgesSize; i++) {
        int u = edges[i][0], v = edges[i][1], w = edges[i][2];
        graph[u][graphSize[u]++] = (Edge){v, w};
        graph[v][graphSize[v]++] = (Edge){u, w};
    }
    
    for (int i = 0; i < querySize; i++) {
        int s = query[i][0], t = query[i][1];
        if (s == t) {
            answer[i] = 0;
        } else {
            memset(visited, 0, sizeof(visited));
            answer[i] = dfs(s, t, (1 << 30) - 1);
        }
    }
    
    return answer;
}

int main() {
    int n;
    scanf("%d", &n);
    
    // Read edges and query arrays
    // Implementation depends on input format
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(Q × 2^E)

For each query Q, we may explore exponentially many paths in worst case

✓ Linear Growth

Space Complexity

O(V)

Recursion stack depth limited by number of vertices

✓ Linear Space

23.4K Views

Medium Frequency

~35 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force DFS — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler