Leetcode 787. K 站中转内最便宜的航班(中等) 动态规划

labuladong讲解

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

题目:

现在有 n 个城市,分别用 01…, n - 1 这些序号表示,城市之间的航线用三元组 [from, to, price] 来表示,比如说三元组 [0,1,100] 就表示,从城市 0 到城市 1 之间的机票价格是 100 元。

题目会给你输入若干参数:正整数 n 代表城市个数,数组 flights 装着若干三元组代表城市间的航线及价格,城市编号 src 代表你所在的城市,城市编号 dst 代表你要去的目标城市,整数 K 代表你最多经过的中转站个数。

请你的算法计算,在 K 次中转之内,从 src 到 dst 所需的最小花费是多少钱,如果无法到达,则返回 -1。

比方说题目给的例子:

n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, K = 1

Leetcode 787. K 站中转内最便宜的航班(中等) 动态规划

 

 

出发点是 0,到达点是 2,允许的最大中转次数 K 为 1,所以最小的开销就是图中红色的两条边,从 0 出发,经过中转城市 1 到达目标城市 2,所以算法的返回值应该是 200。

注意这个中转次数的上限 K 是比较棘手的,如果上述题目将 K 改为 0,也就是不允许中转,那么我们的算法只能返回 500 了,也就是直接从 0 飞到 2

很明显,这题就是个加权有向图中求最短路径的问题。

说白了,就是给你一幅加权有向图,让你求 src 到 dst 权重最小的一条路径,同时要满足,这条路径最多不能超过 K + 1 条边(经过 K 个节点相当于经过 K + 1 条边)。

 

思路:

使用动态规划思想

先对flights遍历构成graph,graph为3维数组,graph[to].push_back({from,price})

然后使用dp,默认值都为n*n*price,也就是最大值100000000

base case为dp[src][k+1]=0,因为k=0时意味着没有中转,只能走一步,所以我们能走的边数为k+1

然后遍历dp,对每个节点遍历求dp

最后对于dp[dst] 从0到k+1遍历取最小值。如果最小值>=100000000,意味着没能走到,返回-1

 

class Solution {
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
        //n*n*price的最大值
        int max_price=100000000;
        //构建图,这里以to到达为key构建
        vector<vector<vector<int>>> graph(n);
        for(int i=0;i<flights.size();++i){
            int from=flights[i][0];
            int to=flights[i][1];
            int price=flights[i][2];
            graph[to].push_back({from,price});
        }
        //表示还剩j步就走到i节点花费的价格
        vector<vector<int>> dp(n,vector<int>(k+2,max_price));
        //k表示最大中转数,所以能走的步数最大是k+1
        dp[src][k+1]=0;
        //从步数=k开始遍历,一直遍历到k=0
        for(int j=k;j>=0;--j){
            for(int i=0;i<n;++i){
                for(int m=0;m<graph[i].size();++m){
                    int from=graph[i][m][0];
                    int price=graph[i][m][1];
                    dp[i][j]=min(dp[i][j],dp[from][j+1]+price);
                }
            }
        }
        //因为最大走k+1步,对dp[dst]从0到k+1遍历,取最小值
        //如果都没走到,返回-1
        int ret=INT_MAX;
        for(int i=0;i<k+2;++i){
            ret=min(ret,dp[dst][i]);
        }
        return ret>=max_price?-1:ret;
    }
};

 

上一篇:leetcode [102. 二叉树的层序遍历](https://leetcode-cn.com/problems/binary-tree-level-order-traversal/)


下一篇:leetcode[剑指offer 03数组中重复的数字]