Cheapest Flights Within K Stops

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

func findCheapestPrice(n int, flights [][]int, src int, dst int, k int) int {
    const INF = math.MaxInt32
    dp := make([]int, n)
    for i := range dp {
        dp[i] = INF
    }
    dp[src] = 0
    for r := 0; r <= k; r++ {
        prev := make([]int, n)
        copy(prev, dp)
        for _, f := range flights {
            u, v, w := f[0], f[1], f[2]
            if prev[u] != INF && prev[u]+w < dp[v] {
                dp[v] = prev[u] + w
            }
        }
    }
    if dp[dst] == INF {
        return -1
    }
    return dp[dst]
}

from typing import List

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

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

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

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