Java实现 LeetCode 787 K 站中转内最便宜的航班(两种DP)

Esta ·

更新时间:2024-11-10

· 751 次阅读

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

有 n 个城市通过 m 个航班连接。每个航班都从城市 u 开始，以价格 w 抵达 v。

现在给定所有的城市和航班，以及出发城市 src 和目的地 dst，你的任务是找到从 src 到 dst 最多经过 k 站中转的最便宜的价格。如果没有这样的路线，则输出 -1。

示例 1：

输入:
n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
src = 0, dst = 2, k = 1
输出: 200
解释:
城市航班图如下

从城市 0 到城市 2 在 1 站中转以内的最便宜价格是 200，如图中红色所示。
示例 2：

输入:
n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
src = 0, dst = 2, k = 0
输出: 500
解释:
城市航班图如下

从城市 0 到城市 2 在 0 站中转以内的最便宜价格是 500，如图中蓝色所示。

提示：

n 范围是 [1, 100]，城市标签从 0 到 n - 1.
航班数量范围是 [0, n * (n - 1) / 2].
每个航班的格式 (src, dst, price).
每个航班的价格范围是 [1, 10000].
k 范围是 [0, n - 1].
航班没有重复，且不存在环路

class Solution {
    //这个dp是第一个是到的目标的位置，第二个参数是步数
    //    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
    //     int dp[][]=new int[n][k+2];
    //     for(int i=0;i<n;i++)
    //         Arrays.fill(dp[i],Integer.MAX_VALUE);
    //     这里初始化了起始点的距离
    //     Arrays.fill(dp[src],0);
    //     for(int per=1;per<=k+1;per++)
    //     {
    //         for(int []num:flights)
    //         {
    //         int from=num[0];
    //         int to=num[1];
    //         int cost=num[2];
    //         //我当前的路程是不是存在路程，如果不存在就是MAX_VALUE
    //         //我当前路程的最小值就是
    //            if(dp[from][per-1]!=Integer.MAX_VALUE) dp[to][per]=Math.min(dp[to][per],dp[from][per-1]+cost);
    //         }
    //     }
    //     return dp[dst][k+1]==Integer.MAX_VALUE?-1:dp[dst][k+1];
    // }
    //这个dp第一个参数是起始位置，第二个参数是目标位置
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {
  int[][] dp = new int[n][K+2];
        for(int i = 0; i < n; ++i) Arrays.fill(dp[i], Integer.MAX_VALUE);
        for(int k = 0; k <= K+1; ++k) dp[src][k] = 0;
        for(int k = 1; k <= K+1; ++k) {
            for(int[] flight : flights) {
                if(dp[flight[0]][k-1] != Integer.MAX_VALUE)
                    dp[flight[1]][k] = Math.min(dp[flight[1]][k], dp[flight[0]][k-1] + flight[2]);
            }
        }
        return dp[dst][K+1] == Integer.MAX_VALUE ? -1 : dp[dst][K+1];
    }
}