Cheapest Flights Within K Stops

hard

Acceptance: 40%

GraphsBFSDFS

A network of n cities is connected by directed flights, each with an associated cost. Given a starting city, a destination city, and a limit of at most k intermediate stops, find the lowest-cost route. If no valid route exists within the stop constraint, return -1.

Examples

Example 1:

Input:n = 3, flights = [[0,1,200],[1,2,200],[0,2,500]], src = 0, dst = 2, k = 1

Output:400

Explanation: Route 0->1->2 costs 400 with 1 stop, cheaper than the direct flight at 500.

Example 2:

Input:n = 3, flights = [[0,1,200],[1,2,200],[0,2,500]], src = 0, dst = 2, k = 0

Output:500

Explanation: With zero intermediate stops, only the direct flight 0->2 at cost 500 qualifies.

Hints

1234567

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // Write your solution here
    }
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // Write your solution here
    }
}

Cheapest Flights Within K Stops

Examples

Hints

Related Problems