## Min Cost of Flight (This question has been seen in the interviews of the following companies: Airbnb)

Min cost of flight from start to end if allowed at most k transfers.
Given all the flights in a string:
A->B,100,
B->C,100,
A->C,500,
If k = 1，from A to C the best route is A->B->C at the cost of 200.

``````
public int minCost(String flights, String from, String to, int k) {
if(from == to) return 0;
if(flights.isEmpty()) return -1;

int[][] edges = parseString(flights,from, to);
Map minCostSet = new HashMap<>();
minCostSet.put(0, 0);

Queue prev = new ArrayDeque<>(); //previous level of nodes

while(k >= 0 && !prev.isEmpty()) {  //BFS
Queue current = new ArrayDeque<>();
for(int source: prev) {
for(int destination = 0; destination < edges.length; destination++) {
if(edges[source][destination] > 0) {
int minCost = minCostSet.containsKey(destination) ? minCostSet.get(destination) : Integer.MAX_VALUE;
int newCost = Math.min(minCost, minCostSet.get(source) + edges[source][destination]);
if (minCost > newCost) {
minCostSet.put(destination, newCost);
}
}
}
}
prev = current;
k--;
}
return minCostSet.containsKey(edges.length - 1) ? minCostSet.get(edges.length - 1): -1;
}

private int[][] parseString(String flights, String start, String end) {
Map map = new HashMap<>();
List edges = new ArrayList<>();
String[] f = flights.split(",");
map.put(start, 0);
map.put(end, -1);
for(int i = 0; i < f.length; i+=2) {
int idx = f[i].indexOf('-');
String src = f[i].substring(0, idx);
String des = f[i].substring(idx + 2);
if(!map.containsKey(src)) {
map.put(src, map.size() - 1);
}
if(!map.containsKey(des)){
map.put(des, map.size() - 1);
}
if(map.get(src) != -1) {    //exclude flights that departs from the ultimate destination
edges.add(new int[]{map.get(src), map.get(des), Integer.parseInt(f[i + 1])});
}
}
int n = map.size();
int[][] graph = new int[n][n];
for(int[] edge: edges) {
if(edge == -1) edge = n - 1;
graph[edge][edge] = edge;
}
return graph;
}

``````