Practice/Meta/Leetcode 787. Cheapest Flights Within K Stops

Leetcode 787. Cheapest Flights Within K Stops

CodingOptional

Problem

You are planning a trip through a network of cities connected by flights. Each flight has an associated cost. Your goal is to find the cheapest way to travel from a starting city to a destination city, but there's a catch: you can make at most a certain number of layovers (intermediate stops).

Given:

• n: the total number of cities (numbered from 0 to n-1)
• flights: an array where each element [from, to, price] represents a direct flight from city from to city to with cost price
• src: the starting city
• dst: the destination city
• k: the maximum number of intermediate stops allowed

Return the minimum cost to travel from src to dst with at most k stops. If no such route exists, return -1.

Note: A direct flight from source to destination counts as 0 stops. A route like src → city1 → dst has 1 stop (at city1).

Requirements

1. Handle cases where multiple paths exist with different costs and stop counts
2. Return -1 if no valid path exists within the stop limit
3. Consider that the same city might be reachable through different paths
4. Handle the edge case where source equals destination (cost should be 0)
5. Process only paths that respect the maximum stop constraint

Constraints

• 1 ≤ n ≤ 100
• 0 ≤ flights.length ≤ n * (n - 1) / 2
• flights[i].length == 3
• 0 ≤ from, to < n
• from != to
• 1 ≤ price ≤ 10^4
• There will not be duplicate flights
• 0 ≤ src, dst, k < n
• src != dst

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 Explanation: The optimal path is 0 → 1 → 3 with cost 700 and exactly 1 stop. Although the path 0 → 1 → 2 → 3 has a lower cost (400), it requires 2 stops which exceeds the limit.

Example 2:

Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 0 Output: 500 Explanation: With k = 0 stops allowed, only direct flights are valid. The direct flight 0 → 2 costs 500.

Example 3:

Input: n = 3, flights = [[0,1,100],[1,2,100]], src = 0, dst = 2, k = 0 Output: -1 Explanation: Reaching city 2 from city 0 requires going through city 1 (1 stop), but k = 0 allows no stops.