 🚀 Minimum Cost Walk – BFS Brute vs. DFS Pro Max Edition 🔥
Intuition 🧠Ayo, so we got a graph with weights, and we tryna walk from s to t, but there’s a twist—the cost ain't sum basic addition/subtraction type beat. Inst
# Intuition 🧠
Ayo, so we got a graph with weights, and we tryna walk from s to t, but there’s a twist—the cost ain't sum basic addition/subtraction type beat. Instead, we gotta bitwise AND the weights. 🧑‍💻✨

Now, the **brute force** idea?
Just **BFS** it out, no thoughts, head empty. Goofy ah approach just explores every path and slaps an & on the weights until we (hopefully) hit t. But BFS ain't built different—it’s just brute forcing every path like a silver player spamming ranked. 💀

# Brute Force (BFS) - The Painful Route 😩
This method really just throws everything at the wall and hopes something sticks. 🚶‍♂️🏃‍♂️
## How It Works?
1. Start from s, explore all possible paths to t using BFS.
2. Track the bitwise AND of edge weights along the way.
3. The first time we reach t, we store the smallest AND value we’ve seen.
4. If we never reach t, just return -1 and cry about it. 😔

### Why this ain't it? 🚫
- Time Complexity is brutal—since we're visiting every possible path, worst case is O(n^2).
- Too many unnecessary calculations, like bro, that ain't even efficient.

# Code
```cpp []
vector<int> minimumCost(int n, vector<vector<int>>& edges, vector<vector<int>>& queries) {
    vector<vector<pair<int, int>>> adj(n);
    for (auto& e : edges) {
        adj[e[0]].push_back({e[1], e[2]});
        adj[e[1]].push_back({e[0], e[2]});
    }
    
    vector<int> res;
    for (auto& q : queries) {
        int s = q[0], t = q[1];
        if (s == t) {
            res.push_back(0);
            continue;
        }
        
        queue<pair<int, int>> q;
        q.push({s, INT_MAX});
        vector<bool> visited(n, false);
        visited[s] = true;
        
        int minAnd = INT_MAX;
        while (!q.empty()) {
            auto [node, currAnd] = q.front(); q.pop();
            if (node == t) {
                minAnd = min(minAnd, currAnd);
            }
            for (auto& [neighbor, weight] : adj[node]) {
                if (!visited[neighbor]) {
                    q.push({neighbor, currAnd & weight});
                    visited[neighbor] = true;
                }
            }
        }
        
        res.push_back(minAnd == INT_MAX ? -1 : minAnd);
    }
    return res;
}
```
# Complexity
- Time complexity: O(n⋅q) (For each query, we do BFS—ouch! 😭)

- Space complexity: O(n) (Adjacency list + BFS queue)

### 👎 BFS is slow, and the repeated searches make it TLE city. 🚧

# DFS - The GOAT Approach 🐐🔥
Realized BFS ain't hitting right, so we pull out the big brain play—DFS + Connected Components 💀

### Steps to the glow-up:
### 1️⃣ Preprocess the Graph 🏗️

- Use DFS to group nodes into connected components.
- For each component, calculate the minimum AND value of all edges in it.

### 2️⃣ Query like a G 🔍

- If s and t in different components, then GG bro, no path exists (-1).
- Else, we instantly return the precomputed AND value. 🚀

### Why this is built different? 🦍
- Time Complexity: O(n + m) for preprocessing, and O(1) for each query. WAYYY faster.
- No unnecessary searches, straight optimized movement.
- DFS clutches up, finding optimal paths and storing answers for later.

# Complexity
- Time complexity:
1. DFS for components: 𝑂(𝑛+𝑒)
1. Answering queries: O(1) per query 💀
1. Total: O(n + e + q) (Absolute W) ✅

- Space complexity: O(n) (Component array + Adjacency list)

# Why is this OP?🤔
✅ No redundant computations - We precompute AND values using DFS.
✅ Faster than BFS - Each query is O(1) instead of O(n).

| Approach  | Query Time | Overall Time | Verdict                |
|-----------|------------|--------------|------------------------|
| BFS Brute🤓 | O(n)       | O(n * q)     | 🚫 TLE Zone 🚧      |
| DFS Chads🗿  | O(1)       | O(n + e + q) | ✅ Absolute W 🔥    |

# Code
```cpp []
class Solution {
public:
    vector<vector<pair<int, int>>> adj;
    vector<int> component;
    vector<int> minAndValue;

    void dfs(int node, int compId, int& andValue) {
        component[node] = compId;
        for (auto& [neighbor, weight] : adj[node]) {
            andValue &= weight;
            if (component[neighbor] == -1) {
                dfs(neighbor, compId, andValue);
            }
        }
    }

    vector<int> minimumCost(int n, vector<vector<int>>& edges, vector<vector<int>>& queries) {
        adj.resize(n);
        component.assign(n, -1);
        minAndValue.assign(n, INT_MAX);
        
        for (auto& e : edges) {
            int u = e[0], v = e[1], w = e[2];
            adj[u].push_back({v, w});
            adj[v].push_back({u, w});
        }

        int compId = 0;
        for (int i = 0; i < n; i++) {
            if (component[i] == -1) {
                int andValue = INT_MAX;
                dfs(i, compId, andValue);
                minAndValue[compId] = andValue;
                compId++;
            }
        }

        vector<int> res;
        for (auto& q : queries) {
            int s = q[0], t = q[1];
            if (component[s] != component[t]) res.push_back(-1);
            else res.push_back(minAndValue[component[s]]);
        }
        
        return res;
    }
};
```
``` Python []
from collections import defaultdict

class Solution:
    def minimumCost(self, n, edges, queries):
        adj = defaultdict(list)
        for u, v, w in edges:
            adj[u].append((v, w))
            adj[v].append((u, w))

        component = [-1] * n

        comp_value = []
        
        comp_id = 0
        
        def dfs(node):
            nonlocal comp_and
            component[node] = comp_id
            for neighbor, weight in adj[node]:
                comp_and &= weight
                if component[neighbor] == -1:
                    dfs(neighbor)
        for i in range(n):
            if component[i] == -1:
                comp_and = (1 << 30) - 1
                dfs(i)
                comp_value.append(comp_and)
                comp_id += 1

        res = []
        for s, t in queries:
            if component[s] != component[t]:
                res.append(-1)
            else:
                res.append(comp_value[component[s]])
                
        return res
```
``` Java []
import java.util.*;

class Solution {
    public int[] minimumCost(int n, int[][] edges, int[][] queries) {
        List<int[]>[] adj = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            adj[i] = new ArrayList<>();
        }

        for (int[] edge : edges) {
            int u = edge[0], v = edge[1], w = edge[2];
            adj[u].add(new int[]{v, w});
            adj[v].add(new int[]{u, w});
        }

        int[] component = new int[n];
        Arrays.fill(component, -1);
        List<Integer> compValue = new ArrayList<>();
        int compId = 0;

        for (int i = 0; i < n; i++) {
            if (component[i] == -1) {
                int[] compAnd = new int[]{(1 << 30) - 1}; 
                dfs(i, compId, compAnd, component, adj);
                compValue.add(compAnd[0]);
                compId++;
            }
        }

        int[] res = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int s = queries[i][0], t = queries[i][1];
            if (component[s] != component[t]) {
                res[i] = -1;
            } else {
                res[i] = compValue.get(component[s]);
            }
        }
        return res;
    }

    private void dfs(int node, int compId, int[] compAnd, int[] component, List<int[]>[] adj) {
        component[node] = compId;
        for (int[] neighbor : adj[node]) {
            int next = neighbor[0], weight = neighbor[1];
            compAnd[0] &= weight;
            if (component[next] == -1) {
                dfs(next, compId, compAnd, component, adj);
            }
        }
    }
}
```
```C []
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_NODES 100005
#define INF ((1 << 30) - 1)

typedef struct {
    int v, w;
} Edge;

typedef struct {
    Edge *edges;
    int size, capacity;
} AdjList;

AdjList adj[MAX_NODES];
int component[MAX_NODES];
int compValue[MAX_NODES];
int compId = 0;

void initGraph(int n) {
    for (int i = 0; i < n; i++) {
        adj[i].edges = NULL;
        adj[i].size = 0;
        adj[i].capacity = 0;
    }
}

void addEdge(int u, int v, int w) {
    if (adj[u].capacity == adj[u].size) {
        adj[u].capacity = (adj[u].capacity == 0) ? 1 : adj[u].capacity * 2;
        adj[u].edges = (Edge *)realloc(adj[u].edges, adj[u].capacity * sizeof(Edge));
    }
    adj[u].edges[adj[u].size++] = (Edge){v, w};

    if (adj[v].capacity == adj[v].size) {
        adj[v].capacity = (adj[v].capacity == 0) ? 1 : adj[v].capacity * 2;
        adj[v].edges = (Edge *)realloc(adj[v].edges, adj[v].capacity * sizeof(Edge));
    }
    adj[v].edges[adj[v].size++] = (Edge){u, w};
}

void dfs(int node, int *compAnd) {
    component[node] = compId;
    for (int i = 0; i < adj[node].size; i++) {
        int neighbor = adj[node].edges[i].v;
        int weight = adj[node].edges[i].w;
        *compAnd &= weight;
        if (component[neighbor] == -1) {
            dfs(neighbor, compAnd);
        }
    }
}

void minimumCost(int n, int edges[][3], int edgesSize, int queries[][2], int queriesSize, int *result) {
    initGraph(n);
    memset(component, -1, sizeof(component));
    memset(compValue, 0, sizeof(compValue));

    for (int i = 0; i < edgesSize; i++) {
        addEdge(edges[i][0], edges[i][1], edges[i][2]);
    }

    for (int i = 0; i < n; i++) {
        if (component[i] == -1) {
            int compAnd = INF;
            dfs(i, &compAnd);
            compValue[compId++] = compAnd;
        }
    }

    for (int i = 0; i < queriesSize; i++) {
        int s = queries[i][0], t = queries[i][1];
        result[i] = (component[s] != component[t]) ? -1 : compValue[component[s]];
    }
}
```
``` Ruby []
class Solution
  def minimum_cost(n, edges, queries)
    adj = Array.new(n) { [] }
    
    edges.each do |u, v, w|
      adj[u] << [v, w]
      adj[v] << [u, w]
    end

    component = Array.new(n, -1)
    comp_value = []
    comp_id = 0

    dfs = lambda do |node, comp_and|
      component[node] = comp_id
      adj[node].each do |neighbor, weight|
        comp_and[0] &= weight
        dfs.call(neighbor, comp_and) if component[neighbor] == -1
      end
    end

    n.times do |i|
      if component[i] == -1
        comp_and = [(1 << 30) - 1]
        dfs.call(i, comp_and)
        comp_value << comp_and[0]
        comp_id += 1
      end
    end

    queries.map do |s, t|
      component[s] != component[t] ? -1 : comp_value[component[s]]
    end
  end
end 
```
``` Kotlin []
class Solution {
    private lateinit var adj: Array<MutableList<Pair<Int, Int>>>
    private lateinit var component: IntArray
    private lateinit var minAndValue: IntArray

    private fun dfs(node: Int, compId: Int, andValue: IntArray) {
        component[node] = compId
        for ((neighbor, weight) in adj[node]) {
            andValue[0] = andValue[0] and weight
            if (component[neighbor] == -1) {
                dfs(neighbor, compId, andValue)
            }
        }
    }

    fun minimumCost(n: Int, edges: Array<IntArray>, queries: Array<IntArray>): IntArray {
        adj = Array(n) { mutableListOf() }
        component = IntArray(n) { -1 }
        minAndValue = IntArray(n) { Int.MAX_VALUE }

        for ((u, v, w) in edges) {
            adj[u].add(v to w)
            adj[v].add(u to w)
        }

        var compId = 0
        for (i in 0 until n) {
            if (component[i] == -1) {
                val andValue = intArrayOf(Int.MAX_VALUE)
                dfs(i, compId, andValue)
                minAndValue[compId] = andValue[0]
                compId++
            }
        }

        return queries.map { (s, t) ->
            if (component[s] != component[t]) -1 else minAndValue[component[s]]
        }.toIntArray()
    }
}
```
``` JavaScript []
class Solution {
    constructor() {
        this.adj = [];
        this.component = [];
        this.minAndValue = [];
    }

    dfs(node, compId, andValue) {
        this.component[node] = compId;
        for (const [neighbor, weight] of this.adj[node]) {
            andValue[0] &= weight;
            if (this.component[neighbor] === -1) {
                this.dfs(neighbor, compId, andValue);
            }
        }
    }

    minimumCost(n, edges, queries) {
        this.adj = Array.from({ length: n }, () => []);
        this.component = Array(n).fill(-1);
        this.minAndValue = Array(n).fill(Number.MAX_SAFE_INTEGER);

        for (const [u, v, w] of edges) {
            this.adj[u].push([v, w]);
            this.adj[v].push([u, w]);
        }

        let compId = 0;
        for (let i = 0; i < n; i++) {
            if (this.component[i] === -1) {
                let andValue = [Number.MAX_SAFE_INTEGER];
                this.dfs(i, compId, andValue);
                this.minAndValue[compId] = andValue[0];
                compId++;
            }
        }

        return queries.map(([s, t]) => 
            this.component[s] !== this.component[t] ? -1 : this.minAndValue[this.component[s]]
        );
    }
}

// Global function to meet the testing environment's expectations:
function minimumCost(n, edges, queries) {
    return new Solution().minimumCost(n, edges, queries);
}

// Example usage:
const n = 5;
const edges = [
    [0, 1, 3],
    [1, 2, 5],
    [3, 4, 7]
];
const queries = [
    [0, 2],
    [3, 4],
    [1, 3]
];

console.log(minimumCost(n, edges, queries));
```
# Conclusion 🏁
🚀 BFS was moving like a bot, but DFS locked in and gave us O(1) query time. From skibidi inefficient to sigma optimal. 🔥

If u still tryna use BFS, u might be stuck in **Silver**, my guy. 💀 **DFS is HIM**. Use it.

![solution-for-streak-v0-6bhrtic9bpdd1.webp](https://assets.leetcode.com/users/images/5d47184e-9c1f-4916-90fc-cf8df06e1b68_1742489474.6616766.webp)

['Depth-First Search', 'Breadth-First Search', 'Graph', 'C', 'C++', 'Java', 'Python3', 'Ruby', 'Kotlin', 'JavaScript']