Cheapest Flight with Limited Layovers

You are given a list of flights, where each flight is defined by its source city, destination city, and cost. Additionally, you are given a maximum number of layovers allowed. A layover is defined as a stop in between the starting city and the destination city. Your task is to determine the minimum cost required to travel from a given start city to a given destination city while using at most the specified number of layovers.

More formally, if you are allowed up to \(k\) layovers, then you can use at most \(k+1\) flights. If there is no valid route that satisfies the condition, output -1.

Note: Input is read from stdin and output should be printed to stdout.

inputFormat

The input will be provided via standard input (stdin) in the following format:

<start_city>
<destination_city>
<max_layovers>
<n>
<source_1> <destination_1> <cost_1>
<source_2> <destination_2> <cost_2>
... 
<source_n> <destination_n> <cost_n>

Where:

• start_city is the string representing the starting city.
• destination_city is the string representing the target city.
• max_layovers is an integer denoting the maximum number of layovers allowed.
• n is the number of flights available.
• Each of the next n lines contains three values: the source city, the destination city, and the cost of that flight.

outputFormat

Output a single integer representing the minimum cost to travel from the start city to the destination city using at most the allowed number of layovers. If no valid route exists, output -1. The result should be printed to standard output (stdout).

A
B
0
1
A B 100

100