There is an undirected weighted graph with n vertices labeled from 0 to n - 1.
You are given the integer n and an array edges, where edges[i] = [ui, vi, wi] indicates that there is an edge between vertices ui and vi with a weight of wi.
A walk on a graph is a sequence of vertices and edges. The walk starts and ends with a vertex, and each edge connects the vertex that comes before it and the vertex that comes after it. It's important to note that a walk may visit the same edge or vertex more than once.
The cost of a walk starting at node u and ending at node v is defined as the bitwise AND of the weights of the edges traversed during the walk. In other words, if the sequence of edge weights encountered during the walk is w0, w1, w2, ..., wk, then the cost is calculated as w0 & w1 & w2 & ... & wk, where & denotes the bitwise AND operator.
You are also given a 2D array query, where query[i] = [si, ti]. For each query, you need to find the minimum cost of the walk starting at vertex si and ending at vertex ti. If there exists no such walk, the answer is -1.
Return the array answer, where answer[i] denotes the minimum cost of a walk for query i.
Example 1:
Input: n = 5, edges = [[0,1,7],[1,3,7],[1,2,1]], query = [[0,3],[3,4]]
Output: [1,-1]
Explanation:
To achieve the cost of 1 in the first query, we need to move on the following edges: 0->1 (weight 7), 1->2 (weight 1), 2->1 (weight 1), 1->3 (weight 7).
In the second query, there is no walk between nodes 3 and 4, so the answer is -1.
Example 2:
Input: n = 3, edges = [[0,2,7],[0,1,15],[1,2,6],[1,2,1]], query = [[1,2]]
Output: [0]
Explanation:
To achieve the cost of 0 in the first query, we need to move on the following edges: 1->2 (weight 1), 2->1 (weight 6), 1->2 (weight 1).
Constraints:
2 <= n <= 1050 <= edges.length <= 105edges[i].length == 30 <= ui, vi <= n - 1ui != vi0 <= wi <= 1051 <= query.length <= 105query[i].length == 20 <= si, ti <= n - 1si != tiThis approach uses a modified version of BFS (Breadth-First Search) with a priority queue to find paths with the minimum bitwise AND cost.
The priority queue helps in exploring paths with lower AND costs first. We start from the source node and aim to reach the target node with the least bitwise AND cost.
This Python solution makes use of a priority queue to perform a BFS-like traversal. The core operation here is maintaining the maximum bitwise AND cost using Dijkstra-like behavior where nodes are explored based on the highest AND-able path cost.
C++
Time Complexity: O(E log V) for each query, where E is the number of edges and V is the number of vertices.
Space Complexity: O(V + E) for the adjacency list and priority queue.
This approach leverages bit manipulation to reduce the problem space. We iteratively refine the set of edges to consider by deconstructing edge weights into significant bits and use these to filter edges in consideration for paths.
The solution uses BFS with an enhancement of bitwise operations to iteratively refine and find the minimum AND path. This Java solution focuses on AND operation behavior to prune unnecessary paths early in the algorithm.
JavaScript
Time Complexity: O(V * E) worst-case per query, making it possible to handle up to moderate graph sizes per query.
Space Complexity: O(V + E) representing the graph storage in adjacency lists.
| Approach | Complexity |
|---|---|
| Approach 1: BFS with Priority Queue | Time Complexity: O(E log V) for each query, where E is the number of edges and V is the number of vertices. Space Complexity: O(V + E) for the adjacency list and priority queue. |
| Approach 2: Bitmask Optimization | Time Complexity: O(V * E) worst-case per query, making it possible to handle up to moderate graph sizes per query. Space Complexity: O(V + E) representing the graph storage in adjacency lists. |
Minimum Cost Walk in Weighted Graph - Leetcode 3108 - Python • NeetCodeIO • 10,891 views views
Watch 9 more video solutions →Practice Minimum Cost Walk in Weighted Graph with our built-in code editor and test cases.
Practice on FleetCode