Solvarch
DSA ProblemsProgressPlanRoadmapsReviewCheat SheetsCompaniesSystem DesignCS FundamentalsQuestion Bank
Theme
Problems

Cheapest Flights Within K Stops

Medium
graphbellman-fordshortest-pathdynamic-programming

There are n cities (0…n−1) and directed flights u v w (from u to v costing w). Find the cheapest price from src to dst using at most k stops (i.e. at most k intermediate cities), or -1 if impossible.

Input

  • Line 1: n m
  • Next m lines: u v w
  • Last line: three integers src dst k

Output: the cheapest price, or -1.

Example 1
Input:
4 5
0 1 100
1 2 100
2 0 100
1 3 600
2 3 200
0 3 1
Output:
700

0→1→3; the cheaper 0→1→2→3 needs 2 stops.

Example 2
Input:
3 3
0 1 100
1 2 100
0 2 500
0 2 1
Output:
200
Example 3
Input:
3 3
0 1 100
1 2 100
0 2 500
0 2 0
Output:
500

Constraints

  • 1 ≤ n ≤ 100
  • 0 ≤ k < n
  • 1 ≤ w ≤ 10^4
Watch a video walkthrough

Run your code against the sample tests, or Submit to run the full suite.