## 787. 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 = 1Output:200Explanation: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 = 0Output:500Explanation: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 from`0`

to`n`

`- 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.

## Rust Solution

```
struct Solution;
use std::cmp::Ordering;
use std::collections::BinaryHeap;
use std::i32;
#[derive(Eq, Debug)]
struct State {
position: usize,
stop: usize,
cost: i32,
}
impl Ord for State {
fn cmp(&self, other: &Self) -> Ordering {
other.cost.cmp(&self.cost)
}
}
impl PartialOrd for State {
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
Some(self.cmp(other))
}
}
impl PartialEq for State {
fn eq(&self, other: &Self) -> bool {
self.cost == other.cost
}
}
#[derive(Copy, Clone)]
struct Edge {
u: usize,
v: usize,
cost: i32,
}
impl Solution {
fn find_cheapest_price(n: i32, flights: Vec<Vec<i32>>, src: i32, dst: i32, k: i32) -> i32 {
let n = n as usize;
let src = src as usize;
let dst = dst as usize;
let k = k as usize;
let mut prices = vec![i32::MAX; n];
prices[src] = 0;
let mut edges: Vec<Vec<Edge>> = vec![vec![]; n];
for f in flights {
let u = f[0] as usize;
let v = f[1] as usize;
let cost = f[2];
edges[u].push(Edge { u, v, cost });
}
let mut pq: BinaryHeap<State> = BinaryHeap::new();
pq.push(State {
position: src,
stop: 0,
cost: 0,
});
while let Some(s) = pq.pop() {
if s.position == dst {
return s.cost;
}
prices[s.position] = i32::min(s.cost, prices[s.position]);
if s.stop <= k {
for e in &edges[s.position] {
pq.push(State {
position: e.v,
cost: s.cost + e.cost,
stop: s.stop + 1,
});
}
}
}
if prices[dst] == i32::MAX {
-1
} else {
prices[dst]
}
}
}
#[test]
fn test() {
let n = 3;
let flights = vec![vec![0, 1, 100], vec![1, 2, 100], vec![0, 2, 500]];
let src = 0;
let dst = 2;
let k = 1;
assert_eq!(Solution::find_cheapest_price(n, flights, src, dst, k), 200);
}
```

Having problems with this solution? Click here to submit an issue on github.