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 = 1Output: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[]>());
}
graph.get(flight[0]).add(new int[]{flight[1], flight[2]});
}
PriorityQueue<Node> q = new PriorityQueue<Node>((a,b) -> (a.cost - b.cost));
q.add(new Node(src, 0, -1));
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){
q.add(new Node(next[0], curr.cost+next[1], curr.stop+1));
}
}
}
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:**