package leetcode;

/**
 * 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) {
        // TODO
        return 0;
    }

    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)); // 200
    }
}

@@ -12,16 +12,121 @@
 tcode;%0A%0A
+import java.util.ArrayList;%0Aimport java.util.LinkedList;%0Aimport java.util.List;%0Aimport java.util.Queue;%0A%0A
 /**%0A * h
@@ -313,33 +313,1889 @@
     
-// TODO%0A        return 0;
+List%3CEdge%3E%5B%5D graph = buildGraph(flights);%0A        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            NodeCount current = queue.remove();%0A            if (current.node == dst) %7B%0A                min = Math.min(min, current.weight);%0A            %7D%0A            List%3CEdge%3E neighbors = graph%5Bcurrent.node%5D;%0A            if (neighbors == null) %7B%0A                continue;%0A            %7D%0A            for (Edge edge : neighbors) %7B%0A                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%0A        %7D%0A        return min == Integer.MAX_VALUE ? -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            this.weight = weight;%0A        %7D%0A    %7D%0A%0A    private static List%3CEdge%3E%5B%5D buildGraph(int%5B%5D%5B%5D flights) %7B%0A        List%3CEdge%3E%5B%5D graph = new List%5B100%5D;%0A        for (int i = 0; i %3C flights.length; i++) %7B%0A            int u = flights%5Bi%5D%5B0%5D;%0A            int v = flights%5Bi%5D%5B1%5D;%0A            int w = flights%5Bi%5D%5B2%5D;%0A            if (graph%5Bu%5D == null) %7B%0A                List%3CEdge%3E list = new ArrayList%3C%3E();%0A                list.add(new Edge(v, w));%0A                graph%5Bu%5D = list;%0A            %7D else %7B%0A                graph%5Bu%5D.add(new Edge(v, w));%0A            %7D%0A        %7D%0A        return graph;%0A    %7D%0A%0A    private static class Edge %7B%0A        private final int to;%0A        private final int weight;%0A%0A        public Edge(int to, int weight) %7B%0A            this.to = to;%0A            this.weight = weight;%0A        %7D
 %0A   
@@ -2403,16 +2403,16 @@
 2, 500%7D%0A
-
         
@@ -2430,16 +2430,160 @@
 ); // 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)); // 50
 0%0A    %7D%0A

Update problem 787