Learn AI Create the Future — with Pranay
Main site

LeetCode solutions

3348. Minimum Cost Walk in Weighted Graph

My accepted Python solution to LeetCode problem 3348, Minimum Cost Walk in Weighted Graph, running in 181ms.

  • Difficulty: Hard
  • Python
  • Runtime 181ms
  • Memory 86.8MB

Read the problem on LeetCode View on GitHub

The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.

Python

Accepted on LeetCode — runtime 181ms, memory 86.8MB, accepted 2026-01-01.

python
class Solution:
    def minimumCost(self, n: int, edges: List[List[int]], query: List[List[int]]) -> List[int]:
        # Use Union-Find with AND of all edges in component
        parent = list(range(n))
        rank = [0] * n
        component_and = [(1 << 30) - 1] * n  # Initialize with all 1s
        
        def find(x):
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]
        
        def union(x, y, w):
            px, py = find(x), find(y)
            if px == py:
                # Update the component AND with this edge weight
                component_and[px] &= w
                return
            
            # Merge the two components
            if rank[px] < rank[py]:
                px, py = py, px
            parent[py] = px
            if rank[px] == rank[py]:
                rank[px] += 1
            
            # Merge ANDs and include the new edge weight
            component_and[px] = component_and[px] & component_and[py] & w
        
        # Build the graph
        for u, v, w in edges:
            union(u, v, w)
        
        result = []
        for s, t in query:
            if s == t:
                result.append(0)
            elif find(s) != find(t):
                result.append(-1)
            else:
                result.append(component_and[find(s)])
        
        return result

Source