package leetcode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 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);
        Queue<NodeCount> queue = new LinkedList<>();
        queue.add(new NodeCount(src, -1, 0));
        int min = Integer.MAX_VALUE;
        while (!queue.isEmpty()) {
            NodeCount current = queue.remove();
            if (current.node == dst) {
                min = Math.min(min, current.weight);
            }
            List<Edge> neighbors = graph[current.node];
            if (neighbors == null) {
                continue;
            }
            for (Edge edge : neighbors) {
                if (current.count + 1 <= K) {
                    queue.add(new NodeCount(edge.to, current.count + 1,
                        current.weight + edge.weight));
                }
            }
        }
        return min == Integer.MAX_VALUE ? -1 : min;
    }

    private static class NodeCount {
        private final int node;
        private final int count;
        private final int weight;

        public NodeCount(int node, int count, int weight) {
            this.node = node;
            this.count = count;
            this.weight = weight;
        }
    }

    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 weight;

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

    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
    }
}

@@ -63,63 +63,10 @@
 l.Li
-nkedList;%0Aimport java.util.List;%0Aimport java.util.Queue
+st
 ;%0A%0A/
@@ -310,311 +310,246 @@
     
-Queue%3CNodeCount%3E queue = new LinkedList%3C%3E();%0A        queue.add(new NodeCount(src, -1, 0));%0A        int min = Integer.MAX_VALUE;%0A        while (!queue.isEmpty()) %7B%0A  
+int price = findCheapestPrice(graph, src, dst, K, new Integer%5B100%5D);%0A        return price == Integer.MAX_VALUE ? - 1 : price;%0A
     
- 
+%7D%0A%0A
     
- NodeCount current = queue.remove();%0A            if (current.node == dst) %7B%0A                min = Math.min(min, current.weight);%0A
+private static int findCheapestPrice(List%3CEdge%3E%5B%5D graph, int src, int dst, int k,%0A                   
     
@@ -548,34 +548,32 @@
                 
-%7D%0A
             List
@@ -570,172 +570,154 @@
     
-  List%3CEdge%3E neighbors = graph%5Bcurrent.node%5D;%0A            if (neighbors == null) %7B%0A                continue;%0A            %7D%0A            for (Edge edge : neighbors) %7B
+Integer%5B%5D memo) %7B%0A        if (src == dst && k %3E= -1) %7B%0A            return 0;%0A        %7D%0A        if (k %3C -1) %7B%0A            return Integer.MAX_VALUE;
 %0A   
@@ -713,32 +713,34 @@
 _VALUE;%0A        
+%7D%0A
         if (curr
@@ -739,193 +739,182 @@
 if (
-current.count + 1 %3C= K) %7B%0A                    queue.add(new NodeCount(edge.to, current.count + 1,%0A                        current.weight + edge.weight));%0A                %7D%0A            %7D
+memo%5Bsrc%5D != null) %7B%0A            return memo%5Bsrc%5D;%0A        %7D%0A        List%3CEdge%3E neighbors = graph%5Bsrc%5D;%0A        if (neighbors == null) %7B%0A            return Integer.MAX_VALUE;
 %0A   
@@ -932,21 +932,17 @@
     
-return
+int
  min =
-=
  Int
@@ -959,299 +959,272 @@
 ALUE
- ? -1 : min
 ;%0A    
-%7D%0A%0A
     
-private static class NodeCount %7B%0A        private final int node;%0A        private final int count;%0A        private final int weight;%0A%0A        public NodeCount(int node, int count, int weight) %7B%0A            this.node = node;%0A            this.count = count;%0A
+for (Edge neighbor : neighbors) %7B%0A            int price = findCheapestPrice(graph, neighbor.to, dst, k - 1, memo);%0A            if (price != Integer.MAX_VALUE) %7B%0A                min = Math.min(min, price + neighbor.price);%0A            %7D%0A    
     
+%7D%0A
         
 this
@@ -1223,39 +1223,44 @@
     
-this.weight = weight;%0A        %7D
+memo%5Bsrc%5D = min;%0A        return min;
 %0A   
@@ -1897,22 +1897,21 @@
 nal int 
-weight
+price
 ;%0A%0A     
@@ -1937,22 +1937,21 @@
 to, int 
-weight
+price
 ) %7B%0A    
@@ -1993,23 +1993,21 @@
 his.
-weight = weight
+price = price
 ;%0A  

Update problem 787