Cheapest Flights Within K Stops

1package pkg5leetcode.interview150;2 3/*4 * Cheapest Flights Within K Stops | LC 7875 * APPROACH: Bellman-Ford style relax edges for k+1 iterations.6 * COMPLEXITY: Time O(k*E), Space O(n)7 */8public class interview150_LC787CheapestFlightsWithinKStops {9    static int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {10        int[] dist = new int[n];11        for (int i = 0; i < n; i++) dist[i] = Integer.MAX_VALUE / 2;12        dist[src] = 0;13        for (int i = 0; i <= k; i++) {14            int[] next = dist.clone();15            for (int[] f : flights) {16                if (dist[f[0]] + f[2] < next[f[1]])17                    next[f[1]] = dist[f[0]] + f[2];18            }19            dist = next;20        }21        return dist[dst] >= Integer.MAX_VALUE / 2 ? -1 : dist[dst];22    }23 24    public static void main(String[] args) {25        int[][] flights = {{0,1,100},{1,2,100},{2,0,100},{1,3,600},{2,3,200}};26        check(findCheapestPrice(4, flights, 0, 3, 1) == 700, "case1");27        check(findCheapestPrice(3, new int[][]{{0,1,100},{1,2,100},{0,2,500}}, 0, 2, 1) == 200, "case2");28        System.out.println("all tests passed");29    }30 31    static void check(boolean cond, String name) {32        if (!cond) throw new AssertionError("FAILED: " + name);33        System.out.println("  PASS " + name);34    }35}