787. Cheapest Flights Within K Stops Medium

1/**
2 * [787] Cheapest Flights Within K Stops
3 *
4 * There are n cities connected by some number of flights. You are given an array flights where flights[i] = [fromi, toi, pricei] indicates that there is a flight from city fromi to city toi with cost pricei.
5 * 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.
6 *  
7 * Example 1:
8 * <img alt="" src="https://assets.leetcode.com/uploads/2022/03/18/cheapest-flights-within-k-stops-3drawio.png" style="width: 332px; height: 392px;" />
9 * 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
10 * Output: 700
11 * Explanation:
12 * The graph is shown above.
13 * The optimal path with at most 1 stop from city 0 to 3 is marked in red and has cost 100 + 600 = 700.
14 * Note that the path through cities [0,1,2,3] is cheaper but is invalid because it uses 2 stops.
15 * 
16 * Example 2:
17 * <img alt="" src="https://assets.leetcode.com/uploads/2022/03/18/cheapest-flights-within-k-stops-1drawio.png" style="width: 332px; height: 242px;" />
18 * Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1
19 * Output: 200
20 * Explanation:
21 * The graph is shown above.
22 * The optimal path with at most 1 stop from city 0 to 2 is marked in red and has cost 100 + 100 = 200.
23 * 
24 * Example 3:
25 * <img alt="" src="https://assets.leetcode.com/uploads/2022/03/18/cheapest-flights-within-k-stops-2drawio.png" style="width: 332px; height: 242px;" />
26 * Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 0
27 * Output: 500
28 * Explanation:
29 * The graph is shown above.
30 * The optimal path with no stops from city 0 to 2 is marked in red and has cost 500.
31 * 
32 *  
33 * Constraints:
34 * 
35 * 	1 <= n <= 100
36 * 	0 <= flights.length <= (n * (n - 1) / 2)
37 * 	flights[i].length == 3
38 * 	0 <= fromi, toi < n
39 * 	fromi != toi
40 * 	1 <= pricei <= 10^4
41 * 	There will not be any multiple flights between two cities.
42 * 	0 <= src, dst, k < n
43 * 	src != dst
44 * 
45 */
46pub struct Solution {}
47
48// problem: https://leetcode.com/problems/cheapest-flights-within-k-stops/
49// discuss: https://leetcode.com/problems/cheapest-flights-within-k-stops/discuss/?currentPage=1&orderBy=most_votes&query=
50
51// submission codes start here
52
53impl Solution {
54    pub fn find_cheapest_price(n: i32, flights: Vec<Vec<i32>>, src: i32, dst: i32, k: i32) -> i32 {
55        0
56    }
57}
58
59// submission codes end
60
61#[cfg(test)]
62mod tests {
63    use super::*;
64
65    #[test]
66    fn test_787() {
67    }
68}
69