Minimum Cost Walk in Weighted Graph

An undirected graph has n vertices labeled from 0 to n - 1. Each entry [u, v, weight] in edges connects u and v with the given weight. Multiple edges may connect the same pair of vertices.

A walk may revisit vertices and edges. Its cost is the bitwise AND of every edge weight it traverses.

For each pair [start, end] in query, find the smallest possible cost of any walk from start to end. Return the answers in query order, using -1 when the two vertices are disconnected.

Example 1:

Input: n = 4
edges = [[0,1,6],[1,2,3]]
query = [[0,2],[0,3]]

Output: [2,-1]

Explanation: The walk 0 → 1 → 2 has cost 6 & 3 = 2. No walk reaches isolated vertex 3 from vertex 0, so the answers are [2,-1].

Example 2:

Input: n = 3
edges = [[0,1,7],[1,2,1]]
query = [[0,1],[2,0]]

Output: [1,1]

Explanation: For the first query, walk 0 → 1 → 2 → 1. The weights are 7, 1, and 1, whose AND is 1. For the second query, walk 2 → 1 → 0, also costing 1. Revisiting edges can improve on the direct edge cost.

Example 3:

Input: n = 2
edges = [[0,1,10],[0,1,5]]
query = [[0,1],[1,0]]

Output: [0,0]

Explanation: The two parallel edges have weights 10 and 5. A walk can cross on the first edge, return on the second, and cross again, giving cost 10 & 5 & 10 = 0. Reversing this walk also has cost 0.

Constraints:

• 2 <= n <= 100000
• 0 <= edges.length <= 100000
• Each edge is [u, v, weight], with distinct endpoints between 0 and n - 1.
• 0 <= weight <= 100000
• Multiple edges between the same vertices are allowed.
• 1 <= query.length <= 100000
• Each query contains two distinct vertex labels between 0 and n - 1.

Topics

Graph Union Find Bit Manipulation

Company Tags

Please upgrade to NeetCode Pro to view company tags.