787. K 站中转内最便宜的航班

题目描述

有 n 个城市，编号 0 到 n - 1。输入数组 flights，其中 flights[i] = [from_i, to_i, price_i] 表示一班从 from_i 飞往 to_i 的单向航班，票价为 price_i。

再输入出发城市 src、目的城市 dst 和整数 k。路线中途停留的城市数不能超过 k，即最多乘坐 k + 1 段航班。

返回满足条件的路线中总票价的最小值。如果没有这样的路线，返回 -1。

示例 1

输入：n = 4
flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]]
src = 0
dst = 3
k = 1
输出：700

解释：0→1→3 中转 1 次，花费 100+600=700；0→1→2→3 更便宜但中转了 2 次。

示例 2

输入：n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1
输出：200

解释：0→1→2 中转 1 次，花费 200。

示例 3

输入：n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 0
输出：500

解释：不允许中转，只能直飞，花费 500。

数据范围

2 <= n <= 100
0 <= flights.length <= (n * (n - 1) / 2)
flights[i].length == 3
0 <= from_i, to_i < n
from_i != to_i
1 <= price_i <= 10^4
航班不重复，也没有起点和终点相同的航班。
0 <= src, dst, k < n
src != dst

解题思路：Bellman-Ford（限制轮数）

限制航段数的最短路用 Bellman-Ford：第 t 轮结束后，dist[v] 是最多乘 t 段航班到达 v 的最低价。每轮用上一轮的 dist 去松弛所有航班，结果写到副本 nxt，这样一轮里最多只多用一段航班。做 k+1 轮即可。

为什么正确

第 t 轮结束时，dist[v] = 从 src 出发、最多乘 t 段航班到达 v 的最低价格。

复杂度分析

时间 O(k · E)，空间 O(n)。

易错点

同一轮里如果直接在 dist 上更新，刚更新的值可能在同一轮继续被使用，相当于多乘了航班。必须用上一轮的副本读、写入 nxt。另外 k 站中转对应 k+1 轮。

参考代码

Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。

class Solution:
    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
        dist = [float('inf')] * n
        dist[src] = 0
        for _ in range(k + 1):
            nxt = dist[:]
            for u, v, w in flights:
                if dist[u] + w < nxt[v]:
                    nxt[v] = dist[u] + w
            dist = nxt
        return -1 if dist[dst] == float('inf') else dist[dst]

class Solution {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        final int INF = Integer.MAX_VALUE / 2;
        int[] dist = new int[n];
        Arrays.fill(dist, INF);
        dist[src] = 0;
        for (int t = 0; t < k + 1; t++) {
            int[] nxt = dist.clone();
            for (int[] f : flights) {
                int u = f[0], v = f[1], w = f[2];
                if (dist[u] + w < nxt[v]) {
                    nxt[v] = dist[u] + w;
                }
            }
            dist = nxt;
        }
        return dist[dst] == INF ? -1 : dist[dst];
    }
}

class Solution {
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
        const int INF = INT_MAX / 2;
        vector<int> dist(n, INF);
        dist[src] = 0;
        for (int t = 0; t < k + 1; t++) {
            vector<int> nxt = dist;
            for (auto& f : flights) {
                int u = f[0], v = f[1], w = f[2];
                if (dist[u] + w < nxt[v]) {
                    nxt[v] = dist[u] + w;
                }
            }
            dist = nxt;
        }
        return dist[dst] == INF ? -1 : dist[dst];
    }
};

func findCheapestPrice(n int, flights [][]int, src int, dst int, k int) int {
	const INF = math.MaxInt32
	dist := make([]int, n)
	for i := range dist {
		dist[i] = INF
	}
	dist[src] = 0
	for t := 0; t < k+1; t++ {
		nxt := append([]int(nil), dist...)
		for _, f := range flights {
			u, v, w := f[0], f[1], f[2]
			if dist[u]+w < nxt[v] {
				nxt[v] = dist[u] + w
			}
		}
		dist = nxt
	}
	if dist[dst] == INF {
		return -1
	}
	return dist[dst]
}

var findCheapestPrice = function(n, flights, src, dst, k) {
    let dist = new Array(n).fill(Infinity);
    dist[src] = 0;
    for (let t = 0; t < k + 1; t++) {
        const nxt = dist.slice();
        for (const [u, v, w] of flights) {
            if (dist[u] + w < nxt[v]) {
                nxt[v] = dist[u] + w;
            }
        }
        dist = nxt;
    }
    return dist[dst] === Infinity ? -1 : dist[dst];
};

function findCheapestPrice(n: number, flights: number[][], src: number, dst: number, k: number): number {
    let dist: number[] = new Array(n).fill(Infinity);
    dist[src] = 0;
    for (let t = 0; t < k + 1; t++) {
        const nxt = dist.slice();
        for (const [u, v, w] of flights) {
            if (dist[u] + w < nxt[v]) {
                nxt[v] = dist[u] + w;
            }
        }
        dist = nxt;
    }
    return dist[dst] === Infinity ? -1 : dist[dst];
}

载入编辑器，自己跑一遍 →

其他解法

Bellman-Ford 天然适合“最多走 k + 1 条边”的限制，代码最短；Dijkstra 需要把航班数加入状态并剪枝，写法更长，但可以提前结束。

解法 2：带中转次数的 Dijkstra 时间 O(k·E·log(k·E))，空间 O(n + k·E)

把状态扩展为（当前花费，城市，已乘航班数），用小根堆按花费弹出。第一次弹出 dst 时的花费就是答案。用 minEdges[u] 记录到达 u 时弹出过的最少航班数：后弹出的状态花费更高，只有航班数更少时才可能有用，否则跳过。航班数已达 k + 1 的状态不再扩展。

常常很早就弹出 dst、提前结束，实际速度可能更快。但普通 Dijkstra 的“每点只处理一次”在这里不成立，必须按航班数剪枝，写错很容易超时或答错。

class Solution:
    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
        adj = [[] for _ in range(n)]
        for u, v, w in flights:
            adj[u].append((v, w))
        min_edges = [float('inf')] * n
        heap = [(0, src, 0)]
        while heap:
            cost, u, e = heapq.heappop(heap)
            if u == dst:
                return cost
            if e >= min_edges[u]:
                continue
            min_edges[u] = e
            if e == k + 1:
                continue
            for v, w in adj[u]:
                heapq.heappush(heap, (cost + w, v, e + 1))
        return -1

class Solution {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        List<List<int[]>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (int[] f : flights) adj.get(f[0]).add(new int[]{f[1], f[2]});
        int[] minEdges = new int[n];
        Arrays.fill(minEdges, Integer.MAX_VALUE);
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        pq.offer(new int[]{0, src, 0});
        while (!pq.isEmpty()) {
            int[] cur = pq.poll();
            int cost = cur[0], u = cur[1], e = cur[2];
            if (u == dst) return cost;
            if (e >= minEdges[u]) continue;
            minEdges[u] = e;
            if (e == k + 1) continue;
            for (int[] vw : adj.get(u)) pq.offer(new int[]{cost + vw[1], vw[0], e + 1});
        }
        return -1;
    }
}

class Solution {
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
        vector<vector<pair<int, int>>> adj(n);
        for (auto& f : flights) adj[f[0]].push_back({f[1], f[2]});
        vector<int> minEdges(n, INT_MAX);
        priority_queue<array<int, 3>, vector<array<int, 3>>, greater<array<int, 3>>> pq;
        pq.push({0, src, 0});
        while (!pq.empty()) {
            auto [cost, u, e] = pq.top();
            pq.pop();
            if (u == dst) return cost;
            if (e >= minEdges[u]) continue;
            minEdges[u] = e;
            if (e == k + 1) continue;
            for (auto& [v, w] : adj[u]) pq.push({cost + w, v, e + 1});
        }
        return -1;
    }
};

type flightState struct{ cost, node, edges int }

type flightHeap []flightState

func (h flightHeap) Len() int            { return len(h) }
func (h flightHeap) Less(i, j int) bool  { return h[i].cost < h[j].cost }
func (h flightHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *flightHeap) Push(x interface{}) { *h = append(*h, x.(flightState)) }
func (h *flightHeap) Pop() interface{} {
	old := *h
	x := old[len(old)-1]
	*h = old[:len(old)-1]
	return x
}

func findCheapestPrice(n int, flights [][]int, src int, dst int, k int) int {
	adj := make([][][2]int, n)
	for _, f := range flights {
		adj[f[0]] = append(adj[f[0]], [2]int{f[1], f[2]})
	}
	minEdges := make([]int, n)
	for i := range minEdges {
		minEdges[i] = math.MaxInt32
	}
	h := &flightHeap{{0, src, 0}}
	for h.Len() > 0 {
		cur := heap.Pop(h).(flightState)
		if cur.node == dst {
			return cur.cost
		}
		if cur.edges >= minEdges[cur.node] {
			continue
		}
		minEdges[cur.node] = cur.edges
		if cur.edges == k+1 {
			continue
		}
		for _, vw := range adj[cur.node] {
			heap.Push(h, flightState{cur.cost + vw[1], vw[0], cur.edges + 1})
		}
	}
	return -1
}

var findCheapestPrice = function(n, flights, src, dst, k) {
    const adj = Array.from({ length: n }, () => []);
    for (const [u, v, w] of flights) adj[u].push([v, w]);
    const minEdges = new Array(n).fill(Infinity);
    const heap = [];
    const push = (item) => {
        heap.push(item);
        let i = heap.length - 1;
        while (i > 0) {
            const p = (i - 1) >> 1;
            if (heap[p][0] <= heap[i][0]) break;
            [heap[p], heap[i]] = [heap[i], heap[p]];
            i = p;
        }
    };
    const pop = () => {
        const top = heap[0], last = heap.pop();
        if (heap.length > 0) {
            heap[0] = last;
            let i = 0;
            while (true) {
                let s = i;
                const l = 2 * i + 1, r = 2 * i + 2;
                if (l < heap.length && heap[l][0] < heap[s][0]) s = l;
                if (r < heap.length && heap[r][0] < heap[s][0]) s = r;
                if (s === i) break;
                [heap[s], heap[i]] = [heap[i], heap[s]];
                i = s;
            }
        }
        return top;
    };
    push([0, src, 0]);
    while (heap.length > 0) {
        const [cost, u, e] = pop();
        if (u === dst) return cost;
        if (e >= minEdges[u]) continue;
        minEdges[u] = e;
        if (e === k + 1) continue;
        for (const [v, w] of adj[u]) push([cost + w, v, e + 1]);
    }
    return -1;
};

function findCheapestPrice(n: number, flights: number[][], src: number, dst: number, k: number): number {
    const adj: number[][][] = Array.from({ length: n }, () => []);
    for (const [u, v, w] of flights) adj[u].push([v, w]);
    const minEdges: number[] = new Array(n).fill(Infinity);
    const heap: number[][] = [];
    const push = (item: number[]): void => {
        heap.push(item);
        let i = heap.length - 1;
        while (i > 0) {
            const p = (i - 1) >> 1;
            if (heap[p][0] <= heap[i][0]) break;
            [heap[p], heap[i]] = [heap[i], heap[p]];
            i = p;
        }
    };
    const pop = (): number[] => {
        const top = heap[0], last = heap.pop()!;
        if (heap.length > 0) {
            heap[0] = last;
            let i = 0;
            while (true) {
                let s = i;
                const l = 2 * i + 1, r = 2 * i + 2;
                if (l < heap.length && heap[l][0] < heap[s][0]) s = l;
                if (r < heap.length && heap[r][0] < heap[s][0]) s = r;
                if (s === i) break;
                [heap[s], heap[i]] = [heap[i], heap[s]];
                i = s;
            }
        }
        return top;
    };
    push([0, src, 0]);
    while (heap.length > 0) {
        const [cost, u, e] = pop();
        if (u === dst) return cost;
        if (e >= minEdges[u]) continue;
        minEdges[u] = e;
        if (e === k + 1) continue;
        for (const [v, w] of adj[u]) push([cost + w, v, e + 1]);
    }
    return -1;
}

动态规划专题的其他题目

查看动态规划全部题目 →