787. Cheapest Flights Within K Stops - Medium

前往題目

思路

Bellman-ford

1. 用額外的array儲存從source到dest.的距離
2. 執行k+1次，因為題目的k是指幾個stop
3. 每輪都走一遍所有的flights，有更短的距離就更新，最後回傳，如果是MAX_VALUE就回傳-1

比較難理解的是用tempPrices儲存當前暫時的prices，走完flights後再給prices，這部分是因為如果不用temprices的話會不知道當前的source是MAX_VALUE，也就是unreachable，需要跳過

Code

class Solution {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        // Prices from source to the specific dst
        int[] prices = new int[n];
        Arrays.fill(prices, Integer.MAX_VALUE);
        prices[src] = 0;

        for (int i = 0; i < k + 1; ++i) {
            // Copy the prices into temp prices
            int[] tmpPrices = new int[prices.length];
            for (int j = 0; j < prices.length; ++j) {
                tmpPrices[j] = prices[j];
            }

            // source, dest., price
            for (int[] flight : flights) {
                int s = flight[0];
                int d = flight[1];
                int p = flight[2];
                
                // Not reachable
                if (prices[s] == Integer.MAX_VALUE) continue;
                if (prices[s] + p < tmpPrices[d]) {
                    tmpPrices[d] = prices[s] + p;
                }
            }
            prices = tmpPrices;
        }
        return prices[dst] == Integer.MAX_VALUE ? -1 : prices[dst];
    }
}