1079. Minimum Cost Path with At Most K Edges (DP+Graph)

Given a directed weighted graph with n nodes and edges [u, v, w] (w >= 0), return the minimum-cost path from src to dst using at most k edges, or -1 if unreachable within k edges. The input is JSON {n, edges, src, dst, k}.

Input: JSON {n, edges, src, dst, k}.

Output: Integer — the minimum cost, or -1.

Examples

Input: {"n":4,"edges":[[0,1,1],[1,2,1],[2,3,1],[0,3,10]],"src":0,"dst":3,"k":2}
Output: 10
Explanation: Only the direct edge fits in 2 edges.

Input: {"n":3,"edges":[[0,1,2],[1,2,3]],"src":0,"dst":2,"k":2}
Output: 5
Explanation: Two-edge path.

Input: {"n":2,"edges":[[0,1,5]],"src":0,"dst":1,"k":1}
Output: 5
Explanation: One edge.

Constraints

• 1<=n<=1000
• w>=0
• 1<=k<=n

Asked by