有 n 个城市通过一些航班连接。给你一个数组 flights 其中 flightsi = starti endi pricei 表示该航班都从城市 starti 开始以价格 pricei 抵达 endi。现在给定所有的城市和航班以及出发城市 src 和目的地 dst你的任务是找到一条中转的路线使得从 src 到 dst 的 总价格最便宜 并返回该价格。 题目保证了这样的路线一定存在。

算法：Dijkstra

题目要求中转一次，所以我们需要考虑的是中转城市。可以使用 Dijkstra 算法来求解，每次找到当前距离最小的节点，然后更新与其相邻节点的距离，如果中途遇到目的地，就可以直接返回当前的距离。

需要注意的是，题目中给定的是每条边的价格，而 Dijkstra 算法是基于边权来更新距离的，所以我们可以使用邻接表来存储图，每个节点保存其相邻节点和对应的边权即可。

时间复杂度

Dijkstra 算法的时间复杂度为 O(ElogV)，其中 E 表示边数，V 表示节点数。在这道题中，我们需要遍历所有的边，因此时间复杂度为 O(ElogV)。

空间复杂度

我们需要使用邻接表来存储图，空间复杂度为 O(E+V)，其中 E 表示边数，V 表示节点数。在这道题中，我们需要使用一个数组来保存距离，空间复杂度为 O(V)。因此总的空间复杂度为 O(E+V)。

Java 代码

class Solution { public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) { // 构造邻接表 List<int[]>[] graph = new List[n]; for (int i = 0; i < n; i++) { graph[i] = new ArrayList<>(); } for (int[] flight : flights) { graph[flight[0]].add(new int[]{flight[1], flight[2]}); }

    // 初始化距离数组
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[src] = 0;

    // 使用优先队列来实现 Dijkstra 算法
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
    pq.offer(new int[]{src, 0, k});

    while (!pq.isEmpty()) {
        int[] node = pq.poll();
        int u = node[0], d = node[1], s = node[2];
        if (u == dst) {
            return d;
        }
        if (s >= 0) {
            for (int[] edge : graph[u]) {
                int v = edge[0], w = edge[1];
                if (dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    pq.offer(new int[]{v, dist[v], s - 1});
                }
            }
        }
    }

    return -1;
}