⚡Flashcard Drill➔
NeetCode #645LC-3108HardAdvanced Graphs
← Back to All Problems

#645 · #3108 · Minimum Cost Walk in Weighted Graph(带权图里旅游的最小代价)

📌 Problem Statement & Constraints

You are given n nodes, edges[i] = [u, v, w] as undirected weighted edges, and query[i] = [s, t]. The cost of a walk from s to t is the bitwise AND of all edge weights on it. Return the minimum cost for each query, or -1 if unreachable. Constraints: 2 <= n <= 10^5, 1 <= edges.length <= 10^5, 1 <= query.length <= 10^5.

💡 Core Algorithmic Approaches

  1. Key insight: a walk may repeat edges, so any edge in the connected component can be included. The AND only decreases as more edges are ANDed.
  2. So the minimum cost within a component is the AND of all its edges.
  3. Union-find identifies the components; a second pass computes each component's AND.
  4. Queries are then O(1) per component lookup.

💻 Benchmark Python3 Implementation

class Solution:
    def minimumCost(self, n: int, edges: List[List[int]], query: List[List[int]]) -> List[int]:
        parent = list(range(n))

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

        for u, v, _ in edges:
            ru, rv = find(u), find(v)
            if ru != rv:
                parent[ru] = rv

        # AND of all edges per component (computed after all unions)
        and_of = {}
        for u, v, w in edges:
            r = find(u)
            and_of[r] = w if r not in and_of else and_of[r] & w

        res = []
        for s, t in query:
            if find(s) != find(t):
                res.append(-1)             # different components
            else:
                res.append(and_of.get(find(s), 0))
        return res

⚡ Complexity Deep Dive

⏱️ Time Complexity
O((n + E) * alpha + q): near-linear.
💾 Space Complexity
O(n) for the union-find and the component ANDs.

⚠️ Interview Pitfalls & Follow-ups

  • Running a shortest-path search per query: the AND objective is not additive.
  • Computing the AND before all unions are done: the component roots would be stale.
  • Forgetting the edgeless-component case: a single node gives 0 (an empty walk).
  • Assuming the AND is monotone along a path: it is, but the walk may revisit edges, which is the key insight.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Advanced Graphs Problems