Coding - Cheapest Flights Within K Stops

Problem Statement

You are given n cities and m flights. The cities are labeled from 0 to n-1, and the flights are represented by flights, where flights[i] = [from_i, to_i, price_i] indicates a flight from city from_i to city to_i with cost price_i. You are also given three integers: src, dst, and k. Your task is to find the cheapest price from src to dst with at most k stops. If there is no possible route, return -1.

Examples

1. Example 1: plaintext Input: n = 4, flights = [[0,1,100],[2,1,100],[1,2,100],[0,3,200],[1,3,200]], src = 0, dst = 3, k = 1 Output: 700 Explanation: The cheapest price from city 0 to city 3 with at most 1 stop is 700. The path is 0 -> 1 -> 3 with a price of 100 + 600 = 700.

2. Example 2: plaintext Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1 Output: 200 Explanation: The cheapest price from city 0 to city 2 with at most 1 stop is 200. The path is 0 -> 1 -> 2 with a price of 100 + 100 = 200.

3. Example 3: plaintext Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 0 Output: 500 Explanation: The cheapest price from city 0 to city 2 with at most 0 stops is 500. The path is 0 -> 2 with a price of 500.

Constraints

• 1 <= n <= 100
• 0 <= m <= 100
• 0 <= src, dst, k <= n-1
• 0 <= price_i <= 10^5
• m flights are given.
• Each flight has a unique from_i and to_i pair.

Hints

• This problem can be solved using a breadth-first search (BFS) algorithm.
• Consider using a min-heap to keep track of the cheapest prices.
• Use a 3D array to store the prices for each city at each stop count.