Minimum Cost Walk in Weighted Graph

Challenge Points: 30

Level: Hard

You are given an undirected graph with n nodes numbered from 0 to n-1.
Each edge in the graph is described as [u, v, w], meaning nodes u and v are connected with weight w.

A walk can revisit edges or nodes any number of times.
The cost of a walk is determined by applying the bitwise AND (&) on every edge-weight used along the walk.

For example, if a walk uses edges with weights:
w1, w2, w3 ... wk
then the walk cost is:

w1 & w2 & w3 & ... & wk

You are also given a list of queries, where each query is [s, t], meaning:
Find the minimum possible cost of any walk starting at s and ending at t.
If no walk exists between the two nodes, return -1.

Your task is to return an array where each element corresponds to the minimum cost for its respective query.

Example 1:

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

Output: [2, 0, 0]

Explanation:

0 → 1 → 2 gives cost 3 & 2 = 2 1 → 2 → 3 → 1 allows repeating edges, giving 2 & 6 & 2 = 0 3 → 2 → 1 gives 6 & 2 = 2, but using loops we can reach cost 0.

Example 2:

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

Output: [0, 0, 0]

Explanation:

All paths have at least one edge with weight 1, and x & 1 = 1 OR if loops exist on a segment, cost can drop to 0. Thus minimum cost is 0 for all queries.

to Continue

Accepted:

Submission:

Report an issue

Code

You need toto run or submitYou need toto run or submit

Test Case

Test Result