Grokking Graph Algorithms for Coding Interviews
Ask Author
Back to course home

0% completed

Vote For New Content
Cheapest Flights Within K Stops (medium)
On this page

Problem Statement

Examples

Problem Statement

There are n cities connected by flights. You are given an array flights where flights[i] = [from<sub>i</sub>, to<sub>i</sub>, price<sub>i</sub>] indicates that there is a flight from city from<sub>i</sub> to city to<sub>i</sub> with cost price<sub>i</sub>.

Find the cheapest flight price a src city to a dst city, but you are allowed to have at most k stops. If there is no such route, return -1.

Examples

Example 1:

  • Input: n = 5, flights = [[0, 1, 50], [1, 2, 50], [2, 3, 50], [3, 4, 50], [0, 4, 300]], src = 1, dst = 4, k = 2
  • Expected Output: 150
Image
  • Explanation: The cheapest flight route from city 1 to city 4 with at most 2 stops is 1 -> 2 -> 3 -> 4. The total cost is 50 + 50 + 50 = 150.

Example 2:

  • Input: n = 4, flights = [[0, 1, 100], [1, 2, 200], [2, 3, 300], [0, 3, 500]], src = 0, dst = 3, k = 1
  • Expected Output: 500
Image
  • Explanation: The cheapest flight route from city 0 to city 3 with at most 1 stop is 0 -> 3. The total cost is 500.

Example 3:

  • Input: n = 3, flights = [[0, 1, 100], [1, 2, 100], [0, 2, 500]], src = 0, dst = 2, k = 1
  • Expected Output: 200
Image
  • Explanation: The cheapest flight route from city 0 to city 2 with at most 1 stop is 0 -> 1 -> 2. The total cost is 100 + 100 = 200.

Constraints:

  • 1 <= n <= 100
  • 0 <= flights.length <= (n * (n - 1) / 2)
  • flights[i].length == 3
  • 0 <= from<sub>i</sub>, to<sub>i</sub> < n
  • from<sub>i</sub> != to<sub>i</sub>
  • 1 <= price<sub>i</sub> <= 104
  • There will not be any multiple flights between two cities.
  • 0 <= src, dst, k < n
  • src != dst
Python3
Python3
. . . .

.....

.....

.....

Like the course? Get enrolled and start learning!

On this page

Problem Statement

Examples