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 = 1 Output: 200 Explanation: The graph looks like this:The cheapest price from city
0
to city2
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 city2
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.
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.