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[0], d = flight[1], w = flight[2];
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[0], cur_s = cur[1], cur_n = cur[2];
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][0], d = flights[i][1], w = flights[i][2];
graph.get(s).add(new ArrayList<>(){ {
add(d);
add(w);
} });
}
int[] weights = new int[n];
Arrays.fill(weights, Integer.MAX_VALUE);
weights[src] = 0;
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[]{0, 0, src});
while (!queue.isEmpty()) {
int[] cur = queue.poll();
int cur_w = cur[0], cur_s = cur[1], cur_n = cur[2];
if (cur_s > k) { continue; }
List<List<Integer>> adjs = graph.get(cur_n);
for (int i = 0; i < adjs.size(); ++i) {
int next_n = adjs.get(i).get(0), next_w = adjs.get(i).get(1);
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)`