Skip to content

787.cheapest-flights-within-k-stops.md

Latest commit

 

History

History
100 lines (82 loc) · 3.03 KB

787.cheapest-flights-within-k-stops.md

File metadata and controls

100 lines (82 loc) · 3.03 KB

787. Cheapest Flights Within K Stops

Key Insights

At most k stops (as transfer stops) means that we have to go to k + 1 stops to destination, we might go without any transfer stop, so we iterate from 0 to k + 1 stops to find the cheapest cost. (0 means that we're at source and can't go to anywhere, 1 means that we can go from source to destination without any transfer stop)

We can use dynamic programming to solve this problem, suppose dp[t][j] represents that we go by t stops to j stop, then we can transit the state from the minimum of all dp[t - 1][i] for all i can reach j

// Previous to current
              [x] --> 
              [y] --> [j]      
              [z] --> 
// Stops
            t - 1      t

// Find the minimum among dp[t - 1][i] + cost(i, j)
min(dp[t - 1][i] + cost(i, j)) = dp[t][j]

Then, we have to find the minimum amoung t = 1 to k + 1 of dp[t][destination] as answer.

Bellman-Ford Algorithm

fun findCheapestPrice(n: Int, flights: Array<IntArray>, src: Int, dst: Int, k: Int): Int {
    val infinite = Int.MAX_VALUE / 2
    val dp = Array(k + 2) { _ -> IntArray(n) { _ -> infinite } }
    // Base case, for 0 stops, the only destination we can reach is the source.
    dp[0][src] = 0

    for (t in 1..k + 1) {
        for (flight in flights) {
            val source = flight[0]
            val destination = flight[1]
            val cost = flight[2]
            dp[t][destination] = min(dp[t][destination], dp[t - 1][source] + cost)
        }
    }

    var result = infinite
    for (t in 1..k + 1) {
        result = min(result, dp[t][dst])
    }
    return if (result == infinite) -1 else result
}

Or

fun findCheapestPrice(n: Int, flights: Array<IntArray>, src: Int, dst: Int, k: Int): Int {
    val infinite = Int.MAX_VALUE / 2
    val dp = Array(k + 1) { _ -> IntArray(n) { _ -> infinite } }
    
    // k is 0, the destination we can reach without any transfer stops is from `src`
    for (flight in flights) {
        val source = flight[0]
        val destination = flight[1]
        val cost = flight[2]
        if (source == src)
            dp[0][destination] = cost
    }

    for (t in 1..k) {
        for (flight in flights) {
            val source = flight[0]
            val destination = flight[1]
            val cost = flight[2]
            dp[t][destination] = min(dp[t][destination], dp[t - 1][source] + cost)
        }
    }

    var result = infinite
    for (t in 0..k) {
        result = min(result, dp[t][dst])
    }
    return if (result == infinite) -1 else result
}

Dijkstra



BFS


WA: https://leetcode.com/problems/cheapest-flights-within-k-stops/submissions/1390858317




AC: https://leetcode.com/problems/cheapest-flights-within-k-stops/submissions/1391049985, understand why? and what's the difference?




k = 1
graph = {
    0: [0,1,1], [0,2,5],
    1: [1,2,1],
    2: [2,3,1]
}
[0] -> 5 -> [2] -> 1 -> [3]
[0] -> 1 -> [1] -> 1 -> [2] -> 1 -> [3]