#0272

Cheapest Flights Within K Stops

MediumDSA28 min20 XP

Problem

Given flights [from, to, price], n cities, source, destination, and k stops, return the cheapest price using at most k stops, or -1 if impossible.

Why This Matters

This problem prevents blindly using ordinary Dijkstra when the path has an extra constraint.

Function Signature

def cheapest_flight(n, flights, src, dst, k):

Examples

Example 1

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

Output200

0 -> 1 -> 2 costs 200 and uses one stop.

Constraints

Return the exact requested value.
Handle edge cases cleanly.
Use the intended DSA pattern when brute force would scale poorly.

CodePython

def cheapest_flight(n, flights, src, dst, k):
    """
    Input example: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1
    Return: 200
    Return the value from the function so the tests can compare it. Do not print unless the prompt asks.
    """
    # write your code here
    return -1

def cheapest_flight(n, flights, src, dst, k):
    """
    Input example: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1
    Return: 200
    Return the value from the function so the tests can compare it. Do not print unless the prompt asks.
    """
    # write your code here
    return -1

Visible browser tests run here when available.

Testcases2 visible / 3 hidden categories

One stop allowed

Input0 to 2 with k = 1

Expected200

The cheaper path through city 1 is allowed.

No stop allowed

Input0 to 2 with k = 0

Expected500

Only the direct flight can be used.

Hidden Test Categories

unreachable destinationcheaper route with too many stopssource equals destination