1076. Dijkstra with State — Minimum Cost with K Stops

Given a directed weighted graph with n nodes and edges [u, v, w], return the minimum cost to travel from src to dst using at most k intermediate stops (at most k+1 edges), or -1 if no such route exists. Use a state-augmented Dijkstra tracking (node, edges used). 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,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]],"src":0,"dst":3,"k":1}
Output: 700
Explanation: 0->1->3 within one stop.

Input: {"n":3,"edges":[[0,1,5],[1,2,5],[0,2,20]],"src":0,"dst":2,"k":0}
Output: 20
Explanation: Direct only with 0 stops.

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

Constraints

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

Asked by