-
Notifications
You must be signed in to change notification settings - Fork 761
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Java code Issue #24
Comments
To fix these issues:
|
Hi @SunilKumarPradhan Have you ran your code ? it's still giving the incorrect output for the test case mentioned (in top) |
TRY this public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
List<Pair<Integer, Integer>>[] graph = new List[n];
for (int i = 0; i < n; i++)
graph[i] = new ArrayList<>();
for (int[] flight : flights) {
final int u = flight[0];
final int v = flight[1];
final int w = flight[2];
graph[u].add(new Pair<>(v, w));
}
return dijkstra(graph, src, dst, k);
}
private int dijkstra(List<Pair<Integer, Integer>>[] graph, int src, int dst, int k) {
int[][] dist = new int[graph.length][k + 2];
Arrays.stream(dist).forEach(A -> Arrays.fill(A, Integer.MAX_VALUE));
// (d, u, stops)
Queue<int[]> minHeap = new PriorityQueue<>((a, b) -> a[0] - b[0]);
dist[src][k + 1] = 0;
minHeap.offer(new int[] {dist[src][k + 1], src, k + 1});
while (!minHeap.isEmpty()) {
final int d = minHeap.peek()[0];
final int u = minHeap.peek()[1];
final int stops = minHeap.poll()[2];
if (u == dst)
return d;
if (stops == 0)
continue;
for (Pair<Integer, Integer> pair : graph[u]) {
final int v = pair.getKey();
final int w = pair.getValue();
if (d + w < dist[v][stops - 1]) {
dist[v][stops - 1] = d + w;
minHeap.offer(new int[] {dist[v][stops - 1], v, stops - 1});
}
}
}
return -1;
}
} |
Hi Found the simple java BFS level wise traversal public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
// Create graph
List<ArrayList<Pair>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
for (int[] flight : flights) adj.get(flight[0]).add(new Pair(flight[1], flight[2]));
int[] dis = new int[n];
Arrays.fill(dis, Integer.MAX_VALUE);
dis[src] = 0;
Queue<Pair> q = new LinkedList<>();
q.add(new Pair(src, 0)); // cost = 0 to reach src
int stops = 0;
while (!q.isEmpty()) {
int size = q.size();
while (size-- > 0) {
Pair pair = q.poll();
int node = pair.first;
int cost = pair.second; // cost to reach node
for (Pair al : adj.get(node)) {
int adjNode = al.first;
int edgeWt = al.second;
if (dis[adjNode] > cost + edgeWt) {
dis[adjNode] = cost + edgeWt;
q.add(new Pair(adjNode, dis[adjNode]));
}
}
}
stops++;
if (stops > k) break;
}
return dis[dst] == Integer.MAX_VALUE ? -1 : dis[dst];
}
``` / |
Problem link : https://leetcode.com/problems/cheapest-flights-within-k-stops/
This is the exact replica code in Java and some test case is failing(Leetcode 47/53)
n = 4
[[0,1,1],[0,2,5],[1,2,1],[2,3,1]]
src = 0
dest = 3
k = 1
Expected output : 6
Actual output: 3
Was struggling to solve this problem from 5-6 hours then came to your video and explanation was wow but in java it's not passing all test case, Please help out with this
The text was updated successfully, but these errors were encountered: