当前位置： 面试刷题>> 寻找最便宜的航行旅途(最多经过k个中转站) (经典算法题500道)
### 题目描述补充
给定一个包含航班信息的二维数组 `flights`，其中 `flights[i] = [fromi, toi, pricei]` 表示从城市 `fromi` 到城市 `toi` 的航班价格为 `pricei`。此外，给定一个整数 `src` 表示起始城市，一个整数 `dst` 表示目标城市，以及一个整数 `k` 表示最多可以经过的中转站数量（包括起始站和目标站在内，总站点数不超过 `k+1`）。
你需要找到从起始城市 `src` 到目标城市 `dst` 的最便宜旅行方式，并返回所需的最小价格。如果没有可能的旅行方式，则返回 `-1`。
### 示例
```
输入:
flights = [[0,1,100],[1,2,100],[0,2,500]]
src = 0
dst = 2
k = 1
输出: 200
解释:
从城市 0 到城市 2 的最便宜路径是 0 -> 1 -> 2，总价格为 100 + 100 = 200。
```
### PHP 示例代码
```php
function findCheapestPrice($flights, $src, $dst, $k) {
$n = count($flights); // 假设航班数量可以代表城市数量（每个城市至少出现一次）
$dp = array_fill(0, $n, array_fill(0, $k + 2, PHP_INT_MAX)); // dp[i][j] 表示到达城市i且经过j个站点的最小价格
$dp[$src][0] = 0; // 起始城市不需要花费
for ($stops = 1; $stops <= $k + 1; $stops++) {
for ($from = 0; $from < $n; $from++) {
for ($to = 0; $to < $n; $to++) {
// 查找是否存在从 from 到 to 的航班
foreach ($flights as $flight) {
if ($flight[0] == $from && $flight[1] == $to) {
$dp[$to][$stops] = min($dp[$to][$stops], $dp[$from][$stops - 1] + $flight[2]);
}
}
}
}
}
$minPrice = PHP_INT_MAX;
for ($i = 0; $i <= $k + 1; $i++) {
$minPrice = min($minPrice, $dp[$dst][$i]);
}
return $minPrice == PHP_INT_MAX ? -1 : $minPrice;
}
```
### Python 示例代码
```python
def findCheapestPrice(flights, src, dst, k):
n = len(flights)
dp = [[float('inf')] * (k + 2) for _ in range(n)]
dp[src][0] = 0
for stops in range(1, k + 2):
for from_city in range(n):
for to_city, _, price in flights:
if from_city == to_city:
continue
dp[to_city][stops] = min(dp[to_city][stops], dp[from_city][stops - 1] + price)
return min(dp[dst]) if min(dp[dst]) != float('inf') else -1
```
### JavaScript 示例代码
```javascript
function findCheapestPrice(flights, src, dst, k) {
const n = flights.length;
const dp = Array.from({ length: n }, () => Array(k + 2).fill(Infinity));
dp[src][0] = 0;
for (let stops = 1; stops <= k + 1; stops++) {
for (let from = 0; from < n; from++) {
for (const [to, _, price] of flights) {
if (from !== to) {
dp[to][stops] = Math.min(dp[to][stops], dp[from][stops - 1] + price);
}
}
}
}
return dp[dst].includes(Infinity) ? -1 : Math.min(...dp[dst]);
}
```
### 备注
- 以上代码均实现了题目要求的功能，但请注意，这些代码假设了航班数组 `flights` 的长度可以用来近似代表城市的数量，这在实际情况中可能需要根据具体数据结构进行调整。
- 面试时，根据面试官的要求和题目细节，可能还需要考虑边界条件、输入验证等。
- 码小课网站中有更多关于算法和数据结构的内容，可以帮助大家深入学习相关知识。