# Cheapest Flights Within K Stops

Published: Oct 21, 2022

## Problem Description

There are `n` cities connected by some number of flights. You are given an array `flights` where `flights[i] = [from[i], to[i], price[i]]` indicates that there is a flight from city `from[i]` to city toi with cost `price[i]`.

You are also given three integers `src`, `dst`, and `k`, return the cheapest price from `src` to `dst` with at most `k` stops. If there is no such route, return -1.

Constraints:

• 1 <= n <= 100`
• `0 <= flights.length <= (n * (n - 1) / 2)`
• `flights[i].length == 3`
• `0 <= from[i], to[i] < n`
• `from[i] != to[i]`
• `1 <= price[i] <= 10**4`
• There will not be any multiple flights between two cities.
• `0 <= src, dst, k < n`
• `src != dst`

https://leetcode.com/problems/cheapest-flights-within-k-stops/

## Examples

``````Example 1

Input: n = 4, flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src = 0, dst = 3, k = 1
Output: 700
Explanation:
The graph is shown above.
The optimal path with at most 1 stop from city 0 to 3 is marked in red and has cost 100 + 600 = 700.
Note that the path through cities [0,1,2,3] is cheaper but is invalid because it uses 2 stops.
``````
``````Exampoe 2

Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1
Output: 200
Explanation:
The graph is shown above.
The optimal path with at most 1 stop from city 0 to 2 is marked in red and has cost 100 + 100 = 200.
``````
``````Example 3

Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 0
Output: 500
Explanation:
The graph is shown above.
The optimal path with no stops from city 0 to 2 is marked in red and has cost 500.
``````

## How to Solve

The problem asks the shortest path based on an edge weight. Given that, Dijkstra or Bellman Ford might come up as a solution. However, simple breadth first search (BFS) also works. The solution here uses an array to save a total weights of the visited node.

The first step is to create a directed graph with edge weights. The solution here uses a tuple or array of (node, weight). Once the graph is created, do the graph traversal by BFS. The visited state is saved in a queue instead of typical set data structure. This is to handle at most k stops condition. While traversing, if the visited count exceeds the currently visiting node, skip the further process. When the popped out node is the destination, return the weight.

## Solution

``````#include <queue>
#include <vector>

using namespace std;

class CheapestFlightsWithinKStops {
public:
int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
vector<vector<pair<int, int>>> graph(n);
for (auto flight: flights) {
int s = flight, d = flight, w = flight;
graph[s].push_back({d, w});
}
vector<int> weights(n, INT_MAX);
weights[src] = 0;
queue<vector<int>> q;
q.push({0, 0, src});  // weight, stops, node
while (!q.empty()) {
vector<int> cur = q.front();
q.pop();
int cur_w = cur, cur_s = cur, cur_n = cur;
if (cur_s > k) { continue; }
for (auto &[next_n, next_w] : graph[cur_n]) {
if (cur_w + next_w < weights[next_n] && cur_s <= k) {
weights[next_n] = cur_w + next_w;
q.push({weights[next_n], cur_s + 1, next_n});
}
}
}
return weights[dst] == INT_MAX ? -1 : weights[dst];
}
};
``````
``````import java.util.*;

class CheapestFlightsWithinKStops {
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
List<List<List<Integer>>> graph = new ArrayList<>();
for (int i = 0; i < n; ++i) { graph.add(new ArrayList<>()); }
for (int i = 0; i < flights.length; ++i) {
int s = flights[i], d = flights[i], w = flights[i];
} });
}
int[] weights = new int[n];
Arrays.fill(weights, Integer.MAX_VALUE);
weights[src] = 0;
while (!queue.isEmpty()) {
int[] cur = queue.poll();
int cur_w = cur, cur_s = cur, cur_n = cur;
if (cur_s > k) { continue; }
for (int i = 0; i < adjs.size(); ++i) {
if (cur_w + next_w < weights[next_n] && cur_s <= k) {
weights[next_n] = cur_w + next_w;
queue.add(new int[]{weights[next_n], cur_s + 1, next_n});
}
}
}
return weights[dst] == Integer.MAX_VALUE ? -1 : weights[dst];
}
}
``````
``````/**
* @param {number} n
* @param {number[][]} flights
* @param {number} src
* @param {number} dst
* @param {number} k
* @return {number}
*/
var findCheapestPrice = function(n, flights, src, dst, k) {
const graph = [...Array(n)].map(_ => []);
for (const [s, d, w] of flights) {
graph[s].push([d, w]);
}
const weights = Array(n).fill(Infinity);
weights[src] = 0;
const queue = [[0, 0, src]];     // weight, stops, node
while (queue.length > 0) {
const [cur_w, cur_s, cur_n] = queue.shift();
if (cur_s > k) { continue; }
for (const [next_n, next_w] of graph[cur_n]) {
if ((cur_w + next_w) < weights[next_n] && cur_s <= k) {
weights[next_n] = cur_w + next_w;
queue.push([weights[next_n], cur_s + 1, next_n]);
}
}
}
return weights[dst] === Infinity ? -1 : weights[dst];
};
``````
``````from typing import List

class CheapestFlightsWithinKStops:
def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
graph = [[] for _ in range(n)]
for s, d, w in flights:
graph[s].append([d, w])
weights = [float('inf') for _ in range(n)];
weights[src] = 0
queue = [[0, 0, src]]
while queue:
cur_w, cur_s, cur_n = queue.pop(0)
if cur_s > k:
continue
for next_n, next_w in graph[cur_n]:
if cur_w + next_w < weights[next_n] and cur_s <= k:
weights[next_n] = cur_w + next_w
queue.append([weights[next_n], cur_s + 1, next_n])
return -1 if weights[dst] == float('inf') else weights[dst]
``````
``````# @param {Integer} n
# @param {Integer[][]} flights
# @param {Integer} src
# @param {Integer} dst
# @param {Integer} k
# @return {Integer}
def find_cheapest_price(n, flights, src, dst, k)
graph = Array.new(n){Array.new}
flights.each do |s, d, w|
graph[s] << [d, w]
end
weights = Array.new(n, Float::INFINITY)
weights[src] = 0
queue = [[0, 0, src]]
while !queue.empty?
cur_w, cur_s, cur_n = queue.shift
if cur_s > k
next
end
graph[cur_n].each do |next_n, next_w|
if cur_w + next_w < weights[next_n] && cur_s <= k
weights[next_n] = cur_w + next_w
queue << [weights[next_n], cur_s + 1, next_n]
end
end
end
return weights[dst] == Float::INFINITY ? -1 : weights[dst]
end
``````

## Complexities

• Time: `O(n + e * k)` – n: number of vertices, e: number of edges, k: given k
• Space: `O(n + e)`