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
- 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.
- So the minimum cost within a component is the AND of all its edges.
- Union-find identifies the components; a second pass computes each component's AND.
- 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.