Cheapest Flight Within K Stops

You are given a network of cities and flights connecting them. The task is to find the cheapest price to travel from a source city to a destination city with at most k stops. Each flight is represented as a triple (u, v, p), where u is the departure city, v is the arrival city, and p is the flight cost. The total cost of a route is the sum of the costs of individual flights, i.e. \( cost = p_1 + p_2 + \cdots + p_n \).

If there exists no route from the source to the destination satisfying the stop constraint, output -1. Note that if the source and destination are the same, the cost is 0.

This problem can be effectively solved using a modified Dijkstra algorithm or a Bellman-Ford approach to account for the maximum number of stops.

inputFormat

The input is given from standard input (stdin) in the following format:

n m
u1 v1 p1
u2 v2 p2
... (m lines total)
src dst k

Where:

• n is the number of cities (indexed from 0 to n-1).
• m is the number of flights.
• Each of the next m lines contains three integers u, v, and p, representing a flight from city u to city v with price p.
• The last line contains three integers: src (starting city), dst (destination city), and k (maximum number of stops allowed).

outputFormat

Output a single integer to standard output (stdout) representing the minimum cost to travel from src to dst with at most k stops. If no such route exists, output -1.

3 3
0 1 100
1 2 100
0 2 500
0 2 1

200