Z36
Cheapest Flights Within K Stops
Problem Statement & Objective
There are n cities connected by some number of flights. Find the cheapest price from src to dst with at most k stops.
Function Signature (Python)
cheapest_flights_within_k_stops(n: int, flights: list[list[int]], source: int, target: int, k: int) -> intInput & Output Contract
Output Rule:Minimum uçuş ücreti veya -1.
System Constraints
1 <= n <= 100
0 <= ucuslar.length <= (n * (n - 1) / 2)
0 <= k < n
0 <= fiyat <= 10^4Example Execution Walkthrough
n = 4, ucuslar = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], kaynak = 0, hedef = 3, k = 1
0 -> 1 -> 3 maliyet 700 (1 durak). 0 -> 1 -> 2 -> 3 maliyet 400 ama 2 durak (k=1 aşıldı).
cevap: 700Example Test Scenarios (3)
Example 1
Input:
[4,[[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]],0,3,1]Expected Output:
700Example 2: 1 Durak Yeterli
Input:
[3,[[0,1,100],[1,2,100],[0,2,500]],0,2,1]Expected Output:
200Example 3: 0 Durak (Doğrudan)
Input:
[3,[[0,1,100],[1,2,100],[0,2,500]],0,2,0]Expected Output:
500