Skip to content

Commit 4d8d409

Browse files
gazeldxgazeldx
committed
787-cheapest-flights-within-k-stops.md Added Python solution.
1 parent 20582be commit 4d8d409

File tree

5 files changed

+250
-0
lines changed

5 files changed

+250
-0
lines changed

‎en/1-1000/787-cheapest-flights-within-k-stops.md

Lines changed: 125 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,125 @@
1+
# 787. Cheapest Flights Within K Stops - Best Practices of LeetCode Solutions
2+
LeetCode link: [787. Cheapest Flights Within K Stops](https://leetcode.com/problems/cheapest-flights-within-k-stops), difficulty: **Medium**.
3+
4+
## LeetCode description of "787. Cheapest Flights Within K Stops"
5+
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 `to_i` with cost `price_i`.
6+
7+
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`.
8+
9+
### [Example 1]
10+
![](../../images/examples/787_1.png)
11+
12+
**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`
13+
14+
**Output**: `700`
15+
16+
**Explanation**:
17+
```
18+
The graph is shown above.
19+
The optimal path with at most 1 stop from city 0 to 3 is marked in red and has cost 100 + 600 = 700.
20+
Note that the path through cities [0,1,2,3] is cheaper but is invalid because it uses 2 stops.
21+
```
22+
23+
### [Example 2]
24+
**Input**: `n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1`
25+
26+
**Output**: `200`
27+
28+
**Explanation**:
29+
```
30+
The graph is shown above.
31+
The optimal path with at most 1 stop from city 0 to 2 is marked in red and has cost 100 + 100 = 200.
32+
```
33+
34+
### [Example 3]
35+
**Input**: `n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 0`
36+
37+
**Output**: `500`
38+
39+
**Explanation**:
40+
```
41+
The graph is shown above.
42+
The optimal path with no stops from city 0 to 2 is marked in red and has cost 500.
43+
```
44+
45+
### [Constraints]
46+
- `1 <= n <= 100`
47+
- `0 <= flights.length <= (n * (n - 1) / 2)`
48+
- `flights[i].length == 3`
49+
- `0 <= from_i, to_i < n`
50+
- `from_i != to_i`
51+
- `1 <= price_i <= 10000`
52+
- There will not be any multiple flights between two cities.
53+
- `0 <= src, dst, k < n`
54+
- `src != dst`
55+
56+
## Intuition
57+
We can solve it via **Bellman-Ford algorithm**.
58+
59+
For a detailed introduction to `Bellman-Ford algorithm`, please refer to [743. Network Delay Time](./743-network-delay-time.md).
60+
61+
## Complexity
62+
**V**: vertex count, **E**: Edge count.
63+
64+
* Time: `O(K * E)`.
65+
* Space: `O(V)`.
66+
67+
## Python
68+
```python
69+
class Solution:
70+
def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
71+
min_costs = [float('inf')] * n
72+
min_costs[src] = 0
73+
74+
for _ in range(k + 1):
75+
min_costs_clone = min_costs.copy()
76+
77+
for from_city, to_city, price in flights:
78+
if min_costs_clone[from_city] == float('inf'):
79+
continue
80+
81+
cost = min_costs_clone[from_city] + price
82+
83+
if cost < min_costs[to_city]:
84+
min_costs[to_city] = cost
85+
86+
if min_costs[dst] == float('inf'):
87+
return -1
88+
89+
return min_costs[dst]
90+
```
91+
92+
## JavaScript
93+
```javascript
94+
// Welcome to create a PR to complete the code of this language, thanks!
95+
```
96+
97+
## Java
98+
```java
99+
// Welcome to create a PR to complete the code of this language, thanks!
100+
```
101+
102+
## C++
103+
```cpp
104+
// Welcome to create a PR to complete the code of this language, thanks!
105+
```
106+
107+
## C#
108+
```c#
109+
// Welcome to create a PR to complete the code of this language, thanks!
110+
```
111+
112+
## Go
113+
```go
114+
// Welcome to create a PR to complete the code of this language, thanks!
115+
```
116+
117+
## Ruby
118+
```ruby
119+
# Welcome to create a PR to complete the code of this language, thanks!
120+
```
121+
122+
## C, Kotlin, Swift, Rust or other languages
123+
```
124+
// Welcome to create a PR to complete the code of this language, thanks!
125+
```

‎images/examples/787_1.png

22.8 KB
Loading

‎images/examples/787_2.png

14.8 KB
Loading

‎images/examples/787_3.png

14.9 KB
Loading

‎zh/1-1000/787-cheapest-flights-within-k-stops.md

Lines changed: 125 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,125 @@
1+
# 787. K 站中转内最便宜的航班 - 力扣题解最佳实践
2+
力扣链接：[787. K 站中转内最便宜的航班](https://leetcode.cn/problems/cheapest-flights-within-k-stops)，难度: **中等**。
3+
4+
## 力扣“787. K 站中转内最便宜的航班”问题描述
5+
有 `n` 个城市通过一些航班连接。给你一个数组 `flights` ，其中 `flights[i] = [fromi, toi, pricei]` ，表示该航班都从城市 `fromi` 开始，以价格 `pricei` 抵达 `toi`。
6+
7+
现在给定所有的城市和航班，以及出发城市 `src` 和目的地 `dst`，你的任务是找到出一条最多经过 `k` 站中转的路线，使得从 `src` 到 `dst` 的 **价格最便宜** ，并返回该价格。 如果不存在这样的路线，则输出 `-1`。
8+
9+
### [示例 1]
10+
![](../../images/examples/787_1.png)
11+
12+
**输入**: `n = 4, flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src = 0, dst = 3, k = 1`
13+
14+
**输出**: `700`
15+
16+
**解释**:
17+
```
18+
城市航班图如上
19+
从城市 0 到城市 3 经过最多 1 站的最佳路径用红色标记，费用为 100 + 600 = 700。
20+
请注意，通过城市 [0, 1, 2, 3] 的路径更便宜，但无效，因为它经过了 2 站。
21+
```
22+
23+
### [示例 2]
24+
**输入**: `n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1`
25+
26+
**输出**: `200`
27+
28+
**解释**:
29+
```
30+
城市航班图如上
31+
从城市 0 到城市 2 经过最多 1 站的最佳路径标记为红色，费用为 100 + 100 = 200。
32+
```
33+
34+
### [示例 3]
35+
**输入**: `n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 0`
36+
37+
**输出**: `500`
38+
39+
**解释**:
40+
```
41+
城市航班图如上
42+
从城市 0 到城市 2 不经过站点的最佳路径标记为红色，费用为 500。
43+
```
44+
45+
### [约束]
46+
- `1 <= n <= 100`
47+
- `0 <= flights.length <= (n * (n - 1) / 2)`
48+
- `flights[i].length == 3`
49+
- `0 <= from_i, to_i < n`
50+
- `from_i != to_i`
51+
- `1 <= price_i <= 10000`
52+
- 航班没有重复，且不存在自环
53+
- `0 <= src, dst, k < n`
54+
- `src != dst`
55+
56+
## 思路
57+
本题可用 **Bellman-Ford算法** 解决。
58+
59+
**Bellman-Ford算法**的详细说明，请参考 [743. 网络延迟时间](./743-network-delay-time.md)。
60+
61+
## 复杂度
62+
**V**: 顶点数量，**E**: 边的数量。
63+
64+
* 时间: `O(K * E)`.
65+
* 空间: `O(V)`.
66+
67+
## Python
68+
```python
69+
class Solution:
70+
def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
71+
min_costs = [float('inf')] * n
72+
min_costs[src] = 0
73+
74+
for _ in range(k + 1):
75+
min_costs_clone = min_costs.copy()
76+
77+
for from_city, to_city, price in flights:
78+
if min_costs_clone[from_city] == float('inf'):
79+
continue
80+
81+
cost = min_costs_clone[from_city] + price
82+
83+
if cost < min_costs[to_city]:
84+
min_costs[to_city] = cost
85+
86+
if min_costs[dst] == float('inf'):
87+
return -1
88+
89+
return min_costs[dst]
90+
```
91+
92+
## JavaScript
93+
```javascript
94+
// Welcome to create a PR to complete the code of this language, thanks!
95+
```
96+
97+
## Java
98+
```java
99+
// Welcome to create a PR to complete the code of this language, thanks!
100+
```
101+
102+
## C++
103+
```cpp
104+
// Welcome to create a PR to complete the code of this language, thanks!
105+
```
106+
107+
## C#
108+
```c#
109+
// Welcome to create a PR to complete the code of this language, thanks!
110+
```
111+
112+
## Go
113+
```go
114+
// Welcome to create a PR to complete the code of this language, thanks!
115+
```
116+
117+
## Ruby
118+
```ruby
119+
# Welcome to create a PR to complete the code of this language, thanks!
120+
```
121+
122+
## C, Kotlin, Swift, Rust or other languages
123+
```
124+
// Welcome to create a PR to complete the code of this language, thanks!
125+
```

0 commit comments

Comments
 (0)