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. Topics: Array, Bit Manipulation, Union Find, Graph. View on LeetCode.

Generate this problem as a practice environment: tested reference solution, 22 parametrized pytest cases, and a playground notebook:

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

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.

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, full suite in test_solution.py:

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.