:orphan:

Cheapest Flights Within K Stops
===============================

.. highlight:: none

Problem
-------
https://leetcode.com/problems/cheapest-flights-within-k-stops/

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

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 1:**

|image1|

::


   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.

**Example 2:**

|image2|

::


   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.

**Example 3:**

|image3|

::


   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.

 

**Constraints:**

- ``2 <= n <= 100``
- ``0 <= flights.length <= (n * (n - 1) / 2)``
- ``flights[i].length == 3``
- ``0 <= from``\ :sub:```i```\ ``, to``\ :sub:```i```\ ``< n``
- ``from``\ :sub:```i```\ ``!= to``\ :sub:```i```
- ``1 <= price``\ :sub:```i```\ ``<= 10``\ :sup:```4```
- There will not be any multiple flights between two cities.
- ``0 <= src, dst, k < n``
- ``src != dst``

.. |image1| image:: https://assets.leetcode.com/uploads/2022/03/18/cheapest-flights-within-k-stops-3drawio.png
.. |image2| image:: https://assets.leetcode.com/uploads/2022/03/18/cheapest-flights-within-k-stops-1drawio.png
.. |image3| image:: https://assets.leetcode.com/uploads/2022/03/18/cheapest-flights-within-k-stops-2drawio.png

.. highlight:: python

Pattern
-------
Dynamic Programming, Depth-First Search, Breadth-First Search, Graph Theory, Heap (Priority Queue)

Approaches
----------

.. tab-set::

    .. tab-item:: Modified Dijkstra

        **Code**

        .. literalinclude:: ../problems/medium/cheapest-flights-within-k-stops/cheapest_flights_within_k_stops__modified_dijkstra.py
            :language: python
            :lines: 11-

        **Test**

        >>> from cheapest_flights_within_k_stops__modified_dijkstra import findCheapestPrice
        >>> findCheapestPrice(4, [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], 0, 3, 1)
        700
        >>> findCheapestPrice(3, [[0,1,100],[1,2,100],[0,2,500]], 0, 2, 1)
        200
        >>> findCheapestPrice(3, [[0,1,100],[1,2,100],[0,2,500]], 0, 2, 0)
        500

        .. autofunction:: cheapest_flights_within_k_stops__modified_dijkstra.findCheapestPrice