# Leetcode 787 Cheapest Flights Within K Stops Java Solution

There are `n` cities connected by `m` flights. Each flight starts from city `u` and arrives at `v` with a price `w`.

Now given all the cities and flights, together with starting city `src` and the destination `dst`, your task is to find the cheapest price from `src` to `dst` with up to `k` stops. If there is no such route, output `-1`.

```Example 1:
Input:
n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
src = 0, dst = 2, k = 1
Output: 200```
```Explanation:
The graph looks like this:```
```The cheapest price from city `0` to city `2` with at most 1 stop costs 200, as marked red in the picture.

Solution:```
``````class Solution {
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {
if(flights.length==0) return -1;

HashMap<Integer, List<int []>> graph = new HashMap<>();

for(int[] flight: flights){

if(!graph.containsKey(flight[0])){
graph.put(flight[0], new ArrayList<int[]>());
}

}

PriorityQueue<Node> q = new PriorityQueue<Node>((a,b) -> (a.cost - b.cost));

while(!q.isEmpty()){

Node curr = q.poll();

if(curr.city == dst){
return curr.cost;
}

if(curr.stop<K){
List<int []> nexts = graph.getOrDefault(curr.city, new ArrayList<int[]>());

for(int[] next: nexts){
}
}
}
return -1;
}
}
class Node {
int city;
int cost;
int stop;
public Node(int city, int cost, int stop){
this.city = city;
this.cost = cost;
this.stop = stop;
}
}``````

Here is the video explanation: