LeetCode 3108: Minimum Cost Walk in Weighted Graph Solution
Master LeetCode problem 3108 (Minimum Cost Walk in Weighted Graph), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.
3108. Minimum Cost Walk in Weighted Graph
Problem Explanation
Explanation:
To solve this problem, we can use a variant of Dijkstra's algorithm. We will create a graph representation using an adjacency list where each node will store the cost so far and the current bitwise AND value. Initially, we will set the cost to infinity and the bitwise AND value to 0 for all nodes except the starting node. We will then traverse the graph from the starting node using a priority queue, updating the cost and bitwise AND value of each neighboring node. If the new cost is less than the current cost, we will update the node's information. We will continue this process until we reach the destination node or there are no more nodes to explore.
Time Complexity:
The time complexity of this approach is O(E log V), where E is the number of edges and V is the number of vertices.
Space Complexity:
The space complexity is O(V), where V is the number of vertices.
:
Solution Code
class Node {
int id;
int cost;
int andValue;
public Node(int id, int cost, int andValue) {
this.id = id;
this.cost = cost;
this.andValue = andValue;
}
}
class Solution {
public int[] findWalkCost(int n, int[][] edges, int[][] query) {
Map<Integer, List<int[]>> graph = new HashMap<>();
for (int[] edge : edges) {
graph.computeIfAbsent(edge[0], k -> new ArrayList<>()).add(new int[]{edge[1], edge[2]});
graph.computeIfAbsent(edge[1], k -> new ArrayList<>()).add(new int[]{edge[0], edge[2]});
}
int[] result = new int[query.length];
for (int i = 0; i < query.length; i++) {
int start = query[i][0];
int end = query[i][1];
PriorityQueue<Node> pq = new PriorityQueue<>((a, b) -> a.cost - b.cost);
pq.offer(new Node(start, 0, 0));
int[] minCost = new int[n];
Arrays.fill(minCost, Integer.MAX_VALUE);
minCost[start] = 0;
while (!pq.isEmpty()) {
Node node = pq.poll();
if (node.id == end) {
result[i] = node.andValue;
break;
}
for (int[] neighbor : graph.getOrDefault(node.id, new ArrayList<>())) {
int newCost = node.cost + neighbor[1];
int newAndValue = node.andValue & neighbor[1];
if (newCost < minCost[neighbor[0]]) {
minCost[neighbor[0]] = newCost;
pq.offer(new Node(neighbor[0], newCost, newAndValue));
}
}
}
if (result[i] == 0) {
result[i] = -1;
}
}
return result;
}
}Try It Yourself
Loading code editor...
Related LeetCode Problems
Frequently Asked Questions
How to solve LeetCode 3108 (Minimum Cost Walk in Weighted Graph)?
This page provides optimized solutions for LeetCode problem 3108 (Minimum Cost Walk in Weighted Graph) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.
What is the time complexity of LeetCode 3108 (Minimum Cost Walk in Weighted Graph)?
The time complexity for LeetCode 3108 (Minimum Cost Walk in Weighted Graph) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.
Can I run code for LeetCode 3108 on DevExCode?
Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 3108 in Java, C++, or Python.