Cheapest Route Within K Hops
A service-routing layer can forward a request through at most k intermediate relays before it must reach the destination service. Each directed link has a cost. Find the cheapest route from the source to the destination using no more than k relays in between.
Problem
Given n nodes and a list of directed edges [u, v, cost], find the cheapest total cost to travel from src to dst using at most k intermediate nodes (so at most k+1 edges). Return -1 if no such route exists.
Input
Integer n, an edges list (each [u, v, cost], 1 ≤ cost ≤ 10^4), and integers src, dst, k. 1 ≤ n ≤ 100.
Output
A single integer — the minimum cost, or -1.
Constraints
- 1 ≤ n ≤ 100; nodes are 0-indexed
- At most k intermediate nodes (k+1 edges)
- Edges are directed
Examples
Example 1
Input
n = 4, edges = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src = 0, dst = 3, k = 1
Output
700
0→1→3 costs 700 using one relay (node 1); the cheaper-per-edge 0→1→2→3 needs two relays, exceeding k.
Example 2
Input
n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1
Output
200
0→1→2 costs 200 with one relay, beating the direct 0→2 of 500.