Cheapest Flights with 'K' slots
import java.util.*;
public class CheapestFlightsWithinKslots {
static class Edge {
int src;
int dest;
int wt;
public Edge(int src, int dest, int wt) {
this.src = src;
this.dest = dest;
this.wt = wt;
}
}
static class Info {
int v;
int cost;
int stops;
public Info(int v, int cost, int stops) {
this.v = v;
this.cost = cost;
this.stops = stops;
}
}
public static void Create(ArrayList<Edge> graph[], int flights[][]) {
for (int i = 0; i < graph.length; i++) {
graph[i] = new ArrayList<>();
}
for (int i = 0; i < flights.length; i++) {
int src = flights[i][0];
int dest = flights[i][1];
int wt = flights[i][2];
Edge e = new Edge(src, dest, wt);
// ADDING THIS EDGE TO SOURCE
graph[src].add(e);
}
}
public static int CheapestFlight(int n, int flights[][], int source, int dest, int k) {
ArrayList<Edge> graph[] = new ArrayList[n];
Create(graph, flights);
int dist[] = new int[n];
for (int i = 0; i < n; i++) {
if (i != source) {
dist[i] = Integer.MAX_VALUE;
}
}
Queue<Info> q = new LinkedList<>();
q.add(new Info(0, 0, 0));
while (!q.isEmpty()) {
Info curr = q.remove();
for (int i = 0; i < graph[curr.v].size(); i++) {
Edge e = graph[curr.v].get(i);
int u = e.src;
int v = e.dest;
int wt = e.wt;
if (dist[u] != Integer.MAX_VALUE && curr.stops <= k && curr.cost + wt < dist[v]) {
dist[v] = curr.cost + wt;
q.add(new Info(v, dist[v], curr.stops + 1));
}
}
}
if (dist[dest] == Integer.MAX_VALUE) {
return -1;
} else {
return dist[dest];
}
}
public static void main(String[] args) {
int n = 4;
int flights[][] = { { 0, 1, 100 }, { 1, 2, 100 }, { 2, 0, 100 }, { 1, 3, 600 }, { 2, 3, 200 } };
int source = 0;
int dest = 3;
int k = 1;
System.out.println(CheapestFlight(n, flights, source, dest, k));
}
}
Comments
Post a Comment