Cheapest Path With Node Limit

You are given a directed weighted graph with n nodes labeled 0 to n - 1. The array edges lists its edges: edges[i] = [u, v, w] is an edge from node u to node v with cost w.

You are also given three integers src, dst, and k. Return the minimum total cost of a path from src to dst that passes through at most k intermediate nodes (nodes other than src and dst; such a path uses at most k + 1 edges). If no such path exists, return -1.

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
Explanation: With at most 1 intermediate node the best path is 0 -> 1 -> 3
with cost 100 + 600 = 700. The path 0 -> 1 -> 2 -> 3 is cheaper (400) but
uses 2 intermediate nodes.

Example 2

Input: n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1
Output: 200
Explanation: With at most 1 intermediate node the best path is 0 -> 1 -> 2
with cost 100 + 100 = 200.

Example 3

Input: n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 0
Output: 500
Explanation: With no intermediate nodes allowed, only the direct edge
0 -> 2 can be used, at cost 500.