Diwali Offer!Flat 20% OFF
Enroll Now
PrakalpanaLive online tech training

155. Cheapest Flights Within K Stops

MediumDay 45 of 60Graphs

There are n cities and a list of one-way flights where flights[i] = [from, to, price]. Find the cheapest price to travel from src to dst using at most `k` stops (a stop is an intermediate city, so at most k + 1 flights). Return -1 if no such route exists.

Example 1
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
0 to 1 to 3 costs 700 with one stop. The cheaper 0 to 1 to 2 to 3 (400) needs two stops.
Example 2
Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 0
Output: 500
Constraints
  • 1 <= n <= 100
  • 0 <= flights.length <= n * (n - 1) / 2
  • 1 <= price <= 10^4
  • No duplicate flights
  • 0 <= src, dst, k < n, src != dst
Hints
Frequently asked at: Amazon, Google, Atlassian, Uber
Ctrl + Enter runs the examples

Not sure what to learn next?

A 1-on-1 session with an industry mentor and a roadmap built for you. How it works

  1. 1Discuss your goals
  2. 2Get a personal plan
  3. 3Start learning
Book for β‚Ή200/ 30 min