Cheapest Flights Within K Stops
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.
Example 2:
Input:
n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
src = 0, dst = 2, k = 0
Output: 500
Explanation:
The graph looks like this:

The cheapest price from city 0 to city 2 with at most 0 stop costs 500, as marked blue in the picture.
Constraints:
The number of nodes
n
will be in range[1, 100]
, with nodes labeled from0
ton - 1
.The size of
flights
will be in range[0, n * (n - 1) / 2]
.The format of each flight will be
(src, dst, price)
.The price of each flight will be in the range
[1, 10000]
.k
is in the range of[0, n - 1]
.There will not be any duplicated flights or self cycles.
class Solution {
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
Map<Integer, Map<Integer, Integer>> graph = new HashMap<>();
for (int[] edge : flights) {
if (!graph.containsKey(edge[0]))
graph.put(edge[0], new HashMap<>());
graph.get(edge[0]).put(edge[1], edge[2]);
}
// PQ based on cost
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
// Cost , Node , Stops allowed
pq.add(new int[] { 0, src, k + 1 });
while (!pq.isEmpty()) {
int[] top = pq.remove();
int price = top[0];
int city = top[1];
int stops = top[2];
if (city == dst)
return price;
// Because there could be routes which their length is shorter but pass more
// stops, and those routes don't necessarily constitute the best route in the
// end. To deal with this, rather than maintain the optimal routes for each
// node, the solution simply put all possible routes into the
// priority queue, so that all of them has a chance to be processed.
if (stops > 0) {
// Going through all the neighbors
Map<Integer, Integer> adjNodes = graph.getOrDefault(city, new HashMap<>());
for (int node : adjNodes.keySet()) {
// Adding all the neighbor nodes
// (irrespective of whether they already are used or not with a different cost)
pq.add(new int[] { price + adjNodes.get(node), node, stops - 1 });
}
}
}
return -1;
}
}
Last updated