3108. Minimum Cost Walk in Weighted Graph [C++]
IntuitionThe problem involves a graph with weighted edges, and we need to determine the minimum bitwise AND cost between pairs of nodes in queries. This suggest
### **Intuition**
The problem involves a graph with weighted edges, and we need to determine the minimum bitwise AND cost between pairs of nodes in queries. This suggests that the graph's connectivity structure should be efficiently determined, and the minimum path cost should be maintained. A **Union-Find (Disjoint Set Union, DSU)** structure with **path compression** and **union by rank** is a natural choice for tracking connected components. 

### **Approach**
1. **Union-Find (DSU) Setup**:  
   - Initialize `parent` and `minPathCost` for each node.
   - Assign each node as its own parent initially.
  
2. **Graph Processing (Union edges using DSU)**:  
   - For each edge, determine the root of its endpoints.
   - Merge the sets if they are not already connected.
   - Update the **bitwise AND** cost for the component.
  
3. **Query Processing**:  
   - If both nodes belong to the same component, return the stored **bitwise AND** cost.
   - If they are not connected, return `-1`.
   - If the start and end nodes are the same, return `0`.

### **Complexity Analysis**
- **Time Complexity**:  
  - **Union-Find operations** (with path compression): \(O(\alpha(n))\), where \(\alpha(n)\) is the inverse Ackermann function, which is nearly constant in practice.
  - **Processing edges**: \(O(E \cdot \alpha(n))\)
  - **Processing queries**: \(O(Q \cdot \alpha(n))\)
  - Overall complexity: **\(O((E + Q) \cdot \alpha(n))\)**, which is nearly **\(O(E + Q)\)**.

- **Space Complexity**:  
  - **DSU Storage (parent array and minPathCost array)**: \(O(n)\)
  - **Result storage**: \(O(Q)\)
  - Overall: **\(O(n + Q)\)**

### **Code**
```cpp
class Solution {
public:
    vector<int> parent, minPathCost;

    int findRoot(int node) {
        if (parent[node] != node) {
            parent[node] = findRoot(parent[node]); // Path compression
        }
        return parent[node];
    }

    vector<int> minimumCost(int n, vector<vector<int>>& edges, vector<vector<int>>& queries) {
        parent.resize(n);
        minPathCost.assign(n, -1);
        for (int i = 0; i < n; i++) parent[i] = i;

        for (auto& edge : edges) {
            int source = edge[0], target = edge[1], weight = edge[2];
            int sourceRoot = findRoot(source);
            int targetRoot = findRoot(target);

            if (minPathCost[sourceRoot] == -1) minPathCost[sourceRoot] = weight;
            else minPathCost[sourceRoot] &= weight;

            if (minPathCost[targetRoot] == -1) minPathCost[targetRoot] = weight;
            else minPathCost[targetRoot] &= weight;

            if (sourceRoot != targetRoot) {
                parent[sourceRoot] = targetRoot;
                minPathCost[targetRoot] &= minPathCost[sourceRoot];
            }
        }

        vector<int> result;
        for (auto& q : queries) {
            int start = q[0], end = q[1];

            if (start == end) result.push_back(0);
            else if (findRoot(start) != findRoot(end)) result.push_back(-1);
            else result.push_back(minPathCost[findRoot(start)]);
        }

        return result;
    }
};
```
['C++']