Home Roadmap Courses Problems Dashboard Pricing

Home Roadmap Courses Problems Dashboard Pricing

Loading editor…

Problem 242

Cheapest Flights Within K Stops

MediumAdvanced Graphs

flights[i] = [from, to, price]. Return the cheapest price from src to dst with at most k stops, or -1.

Examples

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

Constraints

1 ≤ n ≤ 100

Target ComplexityNot required

O(V + E) Time · O(V) Space

Companies (6)

AmazonGoogleMetaMicrosoftAppleUber

Node 22.08.0

Loading editor…

Test casesRun to compare output

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

Expected700

Output—