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

0% completed

Vote For New Content
Cheapest Flights Within K Stops (medium)
Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

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!

Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible