Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit4d8d409

Browse files
committed
787-cheapest-flights-within-k-stops.md Added Python solution.
1 parent20582be commit4d8d409

File tree

5 files changed

+250
-0
lines changed

5 files changed

+250
-0
lines changed
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+
classSolution:
70+
deffindCheapestPrice(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 _inrange(k+1):
75+
min_costs_clone= min_costs.copy()
76+
77+
for from_city, to_city, pricein 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
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+
classSolution:
70+
deffindCheapestPrice(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 _inrange(k+1):
75+
min_costs_clone= min_costs.copy()
76+
77+
for from_city, to_city, pricein 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)
[8]ページ先頭
©2009-2025 Movatter.jp