package leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * https://leetcode.com/problems/cheapest-flights-within-k-stops/
 */
public class Problem787 {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {
        List<Edge>[] graph = buildGraph(flights);
        int price = findCheapestPrice(graph, src, dst, K, new Integer[100]);
        return price == Integer.MAX_VALUE ? - 1 : price;
    }

    private static int findCheapestPrice(List<Edge>[] graph, int src, int dst, int k,
                                         Integer[] memo) {
        if (src == dst && k >= -1) {
            return 0;
        }
        if (k < -1) {
            return Integer.MAX_VALUE;
        }
        if (memo[src] != null) {
            return memo[src];
        }
        List<Edge> neighbors = graph[src];
        if (neighbors == null) {
            return Integer.MAX_VALUE;
        }
        int min = Integer.MAX_VALUE;
        for (Edge neighbor : neighbors) {
            int price = findCheapestPrice(graph, neighbor.to, dst, k - 1, memo);
            if (price != Integer.MAX_VALUE) {
                min = Math.min(min, price + neighbor.price);
            }
        }
        memo[src] = min;
        return min;
    }

    private static List<Edge>[] buildGraph(int[][] flights) {
        List<Edge>[] graph = new List[100];
        for (int i = 0; i < flights.length; i++) {
            int u = flights[i][0];
            int v = flights[i][1];
            int w = flights[i][2];
            if (graph[u] == null) {
                List<Edge> list = new ArrayList<>();
                list.add(new Edge(v, w));
                graph[u] = list;
            } else {
                graph[u].add(new Edge(v, w));
            }
        }
        return graph;
    }

    private static class Edge {
        private final int to;
        private final int price;

        public Edge(int to, int price) {
            this.to = to;
            this.price = price;
        }
    }

    public static void main(String[] args) {
        Problem787 prob = new Problem787();
        System.out.println(prob.findCheapestPrice(3, new int[][]{
            {0, 1, 100}, {1, 2, 100}, {0, 2, 500}
        }, 0, 2, 1)); // 20
        System.out.println(prob.findCheapestPrice(3, new int[][]{
            {0, 1, 100}, {1, 2, 100}, {0, 2, 500}
        }, 0, 2, 0)); // 500
    }
}

@@ -354,16 +354,20 @@
 , dst, K
+ + 1
 , new In
@@ -376,16 +376,23 @@
 ger%5B100%5D
+%5BK + 2%5D
 );%0A     
@@ -586,16 +586,18 @@
 nteger%5B%5D
+%5B%5D
  memo) %7B
@@ -613,29 +613,13 @@
 if (
-src == dst && k %3E= -1
+k %3C 0
 ) %7B%0A
@@ -637,17 +637,33 @@
  return 
-0
+Integer.MAX_VALUE
 ;%0A      
@@ -682,14 +682,18 @@
 if (
-k %3C -1
+src == dst
 ) %7B%0A
@@ -711,33 +711,17 @@
  return 
-Integer.MAX_VALUE
+0
 ;%0A      
@@ -745,16 +745,19 @@
 emo%5Bsrc%5D
+%5Bk%5D
  != null
@@ -784,24 +784,27 @@
 rn memo%5Bsrc%5D
+%5Bk%5D
 ;%0A        %7D%0A
@@ -1210,32 +1210,76 @@
     %7D%0A        %7D%0A
+        if (min != Integer.MAX_VALUE) %7B%0A    
         memo%5Bsrc
@@ -1283,16 +1283,19 @@
 src%5D
+%5Bk%5D
  = min;%0A
     
@@ -1286,24 +1286,34 @@
 %5D%5Bk%5D = min;%0A
+        %7D%0A
         retu
@@ -2087,392 +2087,7 @@
    %7D
-%0A%0A    public static void main(String%5B%5D args) %7B%0A        Problem787 prob = new Problem787();%0A        System.out.println(prob.findCheapestPrice(3, new int%5B%5D%5B%5D%7B%0A            %7B0, 1, 100%7D, %7B1, 2, 100%7D, %7B0, 2, 500%7D%0A        %7D, 0, 2, 1)); // 20%0A        System.out.println(prob.findCheapestPrice(3, new int%5B%5D%5B%5D%7B%0A            %7B0, 1, 100%7D, %7B1, 2, 100%7D, %7B0, 2, 500%7D%0A        %7D, 0, 2, 0)); // 500%0A    %7D
 %0A%7D%0A

Solve problem 787