LeetCode 2247: Maximum Cost of Trip With K Highways
Problem Description
Explanation:
This problem can be solved using Dijkstra's algorithm to find the shortest path in a graph with positive weights. We can modify Dijkstra's algorithm to keep track of the maximum cost while traversing the graph. The idea is to maintain a priority queue to store the vertices to be explored next based on their cost.
- Create an adjacency list to represent the graph where each edge has a weight representing the cost.
- Initialize an array to keep track of the maximum cost to reach each node, initially set to negative infinity except for the starting node which is set to 0.
- Initialize a priority queue to store vertices based on their maximum cost.
- Start with the starting node, update the maximum cost to reach neighboring nodes if the cost is greater and add them to the priority queue.
- Repeat the process until the priority queue is empty.
Time complexity: O(E log V), where E is the number of edges and V is the number of vertices. Space complexity: O(V), where V is the number of vertices.
: :
Solutions
import java.util.*;
class Edge {
int to;
int cost;
public Edge(int to, int cost) {
this.to = to;
this.cost = cost;
}
}
public int maxCost(int n, int k, int[][] highways) {
List<List<Edge>> graph = new ArrayList<>();
for (int i = 0; i < n; i++) {
graph.add(new ArrayList<>());
}
for (int[] highway : highways) {
int from = highway[0];
int to = highway[1];
int cost = highway[2];
graph.get(from).add(new Edge(to, cost));
}
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(b[1], a[1]));
int[] maxCost = new int[n];
Arrays.fill(maxCost, Integer.MIN_VALUE);
maxCost[0] = 0;
pq.offer(new int[]{0, 0});
while (!pq.isEmpty()) {
int[] curr = pq.poll();
int node = curr[0];
int cost = curr[1];
if (cost < maxCost[node]) continue;
for (Edge edge : graph.get(node)) {
int neighbor = edge.to;
int newCost = cost + edge.cost;
if (newCost > maxCost[neighbor]) {
maxCost[neighbor] = newCost;
pq.offer(new int[]{neighbor, newCost});
}
}
}
return maxCost[n - 1];
}Loading editor...