Cheapest Flights Within K Stops
Shortest Path Algorithms DSA practice problem on Onlearn.
Difficulty: hard.
Topics: Find the cheapest flight from a source to a destination city with at most k stops, Graph, Adjacency List, Queue, Shortest Path, Weighted Graph, Time Complexity, Space Complexity, Breadth-First Search, Dijkstra's Algorithm, graph representation, visited tracking, dijkstra's algorithm, queue, shortest path algorithms, bfs, Shortest Path (Dijkstra's Algorithm), Shortest Path Utilities.
Problem: Cheapest Flights Within K Stops There are n cities and m flights. You are given an array of flights where flights[i] = [from i, to i, price i] indicates a flight from city from i to city to i with a cost of 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 such route, return 1. Input The input consists of: An integer n, representing the number of cities. A 2D integer array flights, where each flights[i] = [u, v, w] denotes a flight from city u to city v with cost w. An integer src, representing the starting city. An integer dst, representing the destination city. An integer k, representing the maximum number of stops allowed. Output Return an integer representing the cheapest price from src to dst with at most k stops. If no such route exists, return 1. 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 with at most 1 stop from city 0 to 3 is 0 1 3, which has a cost of 100 + 600 = 700. The path 0 1 2 3 has a cost of 100 + 100 + 200 = 400 but uses 2 stops, which is invalid. Example 2: Input: n = 3 flights = [[0,1,100],[1,2,100],[0,2,500]] src = 0 dst = 2 k = 1 Output: 200 Explanation: The optimal path with at most 1 stop from city 0 to 2 is 0 1 2, which has a cost of 100 + 100 = 200.