FastPrep
Problem · Graph

Cheapest Flights Within K Stops

Learn this problem
● MediumInMobi logoInMobiNEW GRADOA

Problem statement

There are n cities numbered from 0 through n - 1.

Each row [from, to, price] in flights describes a directed flight from city from to city to that costs price.

Return the lowest price of a route from src to dst that uses at most k intermediate stops. Equivalently, the route may use at most k + 1 flights. Return -1 if no such route exists.

Function

findCheapestPrice(n: int, flights: int[][], src: int, dst: int, k: int) → int

Examples

Example 1

n = 4flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]]src = 0dst = 3k = 1return = 700

The cheapest valid route is 0 -> 1 -> 3, which has one intermediate stop and costs 100 + 600 = 700. The cheaper route through cities 1 and 2 uses two stops and is therefore invalid.

Example 2

n = 3flights = [[0,1,100],[1,2,100],[0,2,500]]src = 0dst = 2k = 1return = 200

The route 0 -> 1 -> 2 uses one stop and costs 200, which is less than the direct flight cost of 500.

Example 3

n = 3flights = [[0,1,100],[1,2,100],[0,2,500]]src = 0dst = 2k = 0return = 500

With no intermediate stops allowed, only the direct flight from city 0 to city 2 is valid, so the answer is 500.

Constraints

  • 2 <= n <= 100
  • 0 <= flights.length <= n * (n - 1) / 2
  • flights[i].length == 3
  • 0 <= flights[i][0], flights[i][1] < n
  • flights[i][0] != flights[i][1]
  • 1 <= flights[i][2] <= 10^4
  • There is at most one directed flight from one city to another.
  • 0 <= src, dst, k < n
  • src != dst

More InMobi problems

drafts saved locally
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
  // write your code here.
}
n4
flights[[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]]
src0
dst3
k1
expected700
checking account