final Map<Integer, Character> map = new HashMap<>();

    public int shortestPathCost(final CitiCell[][] cityMap, final int sourceX, final int destinationX, final int flightsCount) {
        if (cityMap == null || cityMap.length == 0 || cityMap[0].length == 0)
            return 0;

        String[] path = "";

        int[] cost = {1000};


        for (int i = 0; i < cityMap.length; i++) {
            map.put(i, (char) (i + 65));
        }

        StringBuilder temp = new StringBuilder();
        temp.append(map.get(sourceX));

        shortestPathCost(cityMap, sourceX, destinationX, flightsCount, temp, path, cost, 0, 0);
        System.out.println("Best Path " + path[0]);
        return cost[0];
    }


    private void shortestPathCost(CitiCell[][] cityMap, int sourceX, int destinationX, int flightsCount, StringBuilder currentPath, String[] bestPath, int[] cost, int roadCost, int flightCost) {

        //2. Our constraint: a) we can only take a path if exist either vai road or flight . b) we can use at most number of given flight
        if (flightsCount < 0)
            return;

        //1. Our goal : to reach destination. Whenever we reach destination, we'll record least cost and best path
        if (sourceX == destinationX) {
            System.out.println("\npath :" + currentPath + " road cost :" + roadCost + " flight cost :" + flightCost);
            if (cost[0] > flightCost + roadCost) {
                cost[0] = flightCost + roadCost;
                bestPath[0] = currentPath.toString();
            }

            return;
        }

        //3. Our choices: we can try all the path that is connected either by road or flight or both.
        for (int i = 0; i < cityMap.length; i++) {
            CitiCell current = cityMap[sourceX][i];
            if (i == sourceX || (current.r == -1 && current.f == -1))
                continue;


            int length = currentPath.length();

            //By road
            if (current.r != -1) {
                currentPath.append("->(R:").append(current.r).append(")").append(map.get(i));

                shortestPathCost(cityMap, i, destinationX, flightsCount, currentPath, bestPath, cost, roadCost + current.r, flightCost);
                currentPath.setLength(length);
            }

            //By flight
            if (current.f != -1) {
                currentPath.append("->(F:").append(current.f).append(")").append(map.get(i));
                shortestPathCost(cityMap, i, destinationX, flightsCount - 1, currentPath, bestPath, cost, roadCost, flightCost + current.f);
                currentPath.setLength(length);
            }


        }
    }

 static class Distance {
        int withoutFlight, withFlight;

        public Distance() {
            this.withoutFlight = Integer.MAX_VALUE;
            this.withFlight = Integer.MAX_VALUE;

        }

        @Override
        public String toString() {
            return "Distance{" +
                    "withoutFlight=" + withoutFlight +
                    ", withFlight=" + withFlight +
                    '}';
        }
    }

    static class Node {
        int distance;
        int node;
        int flightCount;

        public Node(int distance, int node, int isFlight) {
            this.distance = distance;
            this.node = node;
            this.flightCount = isFlight;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "distance=" + distance +
                    ", node=" + node +
                    ", flightCount=" + flightCount +
                    '}';
        }
    }


    public int shortestPathCost(final CityCell[][] cityMap, final int sourceX, final int destinationX, final int flightsCount) {
        if (cityMap == null || cityMap.length == 0 || cityMap[0].length == 0)
            return 0;


        final Queue<Node> queue = new LinkedList<>();

        final Distance[] distance = new Distance[cityMap.length];
        for (int i = 0; i < cityMap.length; i++)
            distance[i] = new Distance();

        //Offer the start node in the queue with 0 distance and no flight
        queue.offer(new Node(0, sourceX, 0));
        distance[sourceX].withFlight = 0;
        distance[sourceX].withoutFlight = 0;


        //Process all paths
        while (!queue.isEmpty()) {

            //pull first path
            Node current = queue.poll();

            // all neighbours
            CityCell[] connectedCities = cityMap[current.node];

            for (int i = 0; i < connectedCities.length; i++) {
                CityCell cityCell = connectedCities[i];

                if (i == current.node || (cityCell.f == -1 && cityCell.r == -1))
                    continue;

                //See if this neighbour is gives minimum distance by road
                if (cityCell.r != -1 && distance[i].withoutFlight >= current.distance + cityCell.r) {
                    distance[i].withoutFlight = current.distance + cityCell.r;
                    queue.offer(new Node(distance[i].withoutFlight, i, current.flightCount));
                }


                //See if this neighbour is gives minimum distance by flight and we have 1 more flight left from current location so far
                if (cityCell.f != -1 && current.flightCount + 1 <= flightsCount && distance[i].withFlight >= current.distance + cityCell.f) {
                    distance[i].withFlight = current.distance + cityCell.f;
                    queue.offer(new Node(distance[i].withFlight, i, current.flightCount + 1));
                }

            }

        }
        //get minimum distance with/without flight
        return Math.min(distance[destinationX].withFlight, distance[destinationX].withoutFlight);


    }