题目描述补充

给定一个包含航班信息的二维数组 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 示例代码

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 示例代码

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 示例代码

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 的长度可以用来近似代表城市的数量，这在实际情况中可能需要根据具体数据结构进行调整。
• 面试时，根据面试官的要求和题目细节，可能还需要考虑边界条件、输入验证等。
• 码小课网站中有更多关于算法和数据结构的内容，可以帮助大家深入学习相关知识。