最便宜的航班中转路线：Dijkstra 算法详解

算法：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;
    }
}