ZBLOG

class Solution { public: int findCheapestPrice(int N, vector& flights, int src, int dst, int K) { vector dp(N, vector(K + 1, INT_MAX)); K = min(K, N - 2); // Base case direct flight ...

class Solution {

public int findCheapestPrice(int N, int[][] flights, int src, int dst, int K) {
    long[][] dp = new long[N][K + 1];
    for (int i = 0; i < N; i++) {
        Arrays.fill(dp[i], Integer.MAX_VALUE);
    }
    K = Math.min(K, N - 2);
    dp[src][0] = 0;
    for (int[] flight : flights) {
        int start = flight[0];
        int end = flight[1];
        int price = flight[2];
        if (start == src) {
            dp[end][0] = Math.min(dp[end][0], price);
        }
    }
    for (int k = 1; k <= K; k++) {
        for (int[] flight : flights) {
            int u = flight[0];
            int v = flight[1];
            int w = flight[2];
            dp[v][k] = Math.min(Math.min(dp[v][k - 1], dp[v][k]), dp[u][k - 1] + w);
        }
    }
    return dp[dst][K] == Integer.MAX_VALUE ? -1 : (int)dp[dst][K];
}

}

本站部分文章来源于网络,版权归原作者所有,如有侵权请联系站长删除。
转载请注明出处:https://golang.0voice.com/?id=1452

分享:
扫描分享到社交APP
上一篇
下一篇
发表列表
游客 游客
此处应有掌声~
评论列表

还没有评论,快来说点什么吧~

联系我们

在线咨询: 点击这里给我发消息

微信号:3007537140

上班时间: 10:30-22:30

关注我们
x

注册

已经有帐号?