> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Minimum Cost Walk in Weighted Graph

> Tested Python solution for LeetCode 3108 with 22 pytest cases. Generate a practice environment with lcpy.

LeetCode 3108, [Hard](/catalog/hard). Topics: [Array](/catalog/topics/array), [Bit Manipulation](/catalog/topics/bit-manipulation), [Union Find](/catalog/topics/union-find), [Graph](/catalog/topics/graph). [View on LeetCode](https://leetcode.com/problems/minimum-cost-walk-in-weighted-graph/description/).

Generate this problem as a practice environment: tested reference solution, 22 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 3108   # by problem number
lcpy gen -s minimum_cost_walk_in_weighted_graph   # by problem name
```

## 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] = [ui, vi, wi]` indicates that there is an edge between vertices `ui` and `vi` with a weight of `wi`.

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 `w0, w1, w2, ..., wk`, then the cost is calculated as `w0 & w1 & w2 & ... & wk`, where `&` denotes the bitwise `AND` operator.

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

### Examples

![Example 1](https://assets.leetcode.com/uploads/2024/01/31/q4_example1-1.png)

```
Input: n = 5, edges = [[0,1,7],[1,3,7],[1,2,1]], query = [[0,3],[3,4]]
Output: [1,-1]
Explanation:
To achieve the cost of 1 in the first query, we need to move on the following edges: 0->1 (weight 7), 1->2 (weight 1), 2->1 (weight 1), 1->3 (weight 7).
In the second query, there is no walk between nodes 3 and 4, so the answer is -1.
```

![Example 2](https://assets.leetcode.com/uploads/2024/01/31/q4_example2e.png)

```
Input: n = 3, edges = [[0,2,7],[0,1,15],[1,2,6],[1,2,1]], query = [[1,2]]
Output: [0]
Explanation:
To achieve the cost of 0 in the first query, we need to move on the following edges: 1->2 (weight 1), 2->1 (weight 6), 1->2 (weight 1).
```

### Constraints

* 2 \<= n \<= 10^5
* 0 \<= edges.length \<= 10^5
* edges\[i].length == 3
* 0 \<= ui, vi \<= n - 1
* ui != vi
* 0 \<= wi \<= 10^5
* 1 \<= query.length \<= 10^5
* query\[i].length == 2
* 0 \<= si, ti \<= n - 1
* si != ti

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/minimum_cost_walk_in_weighted_graph/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/minimum_cost_walk_in_weighted_graph/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
FULL_MASK = (1 << 17) - 1


class Solution:
    # Time: O((len(edges) + len(query)) * alpha(n))
    # Space: O(n)
    def minimum_cost(self, n: int, edges: list[list[int]], query: list[list[int]]) -> list[int]:
        # A walk may repeat edges, so within a connected component every edge can be
        # traversed, and extra edges only clear bits. The minimum cost for two nodes
        # in the same component is therefore the AND of all weights in it.
        parent = list(range(n))
        and_by_root = [FULL_MASK] * n

        def find(node: int) -> int:
            while parent[node] != node:
                parent[node] = parent[parent[node]]
                node = parent[node]
            return node

        for u, v, weight in edges:
            ru, rv = find(u), find(v)
            if ru == rv:
                and_by_root[ru] &= weight
            else:
                parent[ru] = rv
                and_by_root[rv] &= and_by_root[ru] & weight

        result: list[int] = []
        for start, end in query:
            if start == end:
                result.append(0)
                continue
            root = find(start)
            result.append(and_by_root[root] if root == find(end) else -1)
        return result
```

## Complexity

| Time | Space |
| - | - |
| O((len(edges) + len(query)) \* alpha(n)) | O(n) |

## Tags

[NeetCode All](/catalog/neetcode).


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.