[Flipkart][LeetCode] Cheapest Flights Within K Stops

Problem: There are n cities connected by some number of flights. You are given an array flights where flights[i] = [fromi, toi, pricei] indicates that there is a flight from city fromi to city toi with cost pricei.

You are also given three integers src, dst, and k, return the cheapest price from src to dst with at most k stops. If there is no such route, return -1.

Example:

Input: n = 4, flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src = 0, dst = 3, k = 1
Output: 700
Explanation:
The graph is shown above.
The optimal path with at most 1 stop from city 0 to 3 is marked in red and has cost 100 + 600 = 700.
Note that the path through cities [0,1,2,3] is cheaper but is invalid because it uses 2 stops.

Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1
Output: 200
Explanation:
The graph is shown above.
The optimal path with at most 1 stop from city 0 to 2 is marked in red and has cost 100 + 100 = 200.

Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 0
Output: 500
Explanation:
The graph is shown above.
The optimal path with no stops from city 0 to 2 is marked in red and has cost 500.

Approach: We can use BFS here with little modifications:

1. Number of levels will be limited by k.
2. Can visit the same node multiple times.

We can then put an optimization here which is we will revisit the same node again only if the price of current visit is less than of the price of previous visit. 

Implementation in C#:

public class GraphLink

{

    public int Node { get; set; }

    public int Price { get; set; }

    public GraphLink(int node, int price)

    {

        this.Node = node;

        this.Price = price;

    }

}

public class QueueElement

{

    public int Node {get; set;}

    public int Price {get; set;}

    public QueueElement(int node, int price)

    {

        this.Node = node;

        this.Price = price;

    }

}

public class Solution {

    public int FindCheapestPrice(int n, int[][] flights, int src, int dst, int k) 

    {

        int length = flights?.Length ?? 0;

        if (length == 0)

        {

            return 0;

        }        

        var graph = this.BuildGraph(n, flights);

        int stops = 0;

        Queue<QueueElement> queue = new Queue<QueueElement>();

        queue.Enqueue(new QueueElement(src, 0));

        int[] prices = new int[n];

        Array.Fill(prices, int.MaxValue);

        while (stops <= k && queue.Count > 0)

        {

            int size = queue.Count;

            for (int i = 0; i < size; ++i)

            {

                QueueElement elem = queue.Dequeue();

                if (graph[elem.Node] == null)

                {

                    continue;

                }

                int currPrice = elem.Price;

                foreach (var link in graph[elem.Node])

                {

                    int nextPrice = currPrice + link.Price;

                    if (nextPrice >= prices[link.Node])

                    {

                        continue;

                    }

                    prices[link.Node] = nextPrice;

                    queue.Enqueue(new QueueElement(link.Node, nextPrice));

                }

            }

            ++stops;

        }

        return prices[dst] == int.MaxValue ? -1 : prices[dst];

    }

    

    private List<GraphLink>[] BuildGraph(int n, int[][] flights)

    {

        List<GraphLink>[] graph = new List<GraphLink>[n];

        foreach (var flight in flights)

        {

            if (graph[flight[0]] == null)

            {

                graph[flight[0]] = new List<GraphLink>();

            }

            graph[flight[0]].Add(new GraphLink(flight[1], flight[2]));

        }

        return graph;

    }

}

Complexity: (n + m + m * k) where m is the length of flights which is basically number of edges in the graph.