Find cheapest flight with at most K stops

Problem

You are given a directed weighted graph representing flights between cities.

Inputs

• An integer n: number of cities, labeled 0..n-1.
• A list flights, where each element is [from, to, price] meaning there is a flight from city from to city to that costs price.
• Two integers src and dst: the start and destination cities.
• An integer K: the maximum number of stops allowed, where a stop is an intermediate city between src and dst.
• Equivalently, you may take at most K+1 flights (edges).

Output

Return the minimum total cost to travel from src to dst using at most K stops. If it is not possible, return -1.

Notes / Clarifications

• You may assume all price values are non-negative integers.
• The route must follow the directed edges as given in flights.

Example

• n = 4
• flights = [[0,1,100],[1,2,100],[2,3,100],[0,3,500]]
• src = 0, dst = 3, K = 1

The cheapest valid route is 0 -> 1 -> 2 -> 3 is not allowed (2 stops), so the answer is 500 via 0 -> 3.