1032. Cheapest Flights Within K Stops

Given n cities and directed flights [u, v, w] (price w), return the cheapest price to travel from src to dst using at most k intermediate stops, or -1 if there is no such route. The input is JSON {n, edges, src, dst, k}.

Input: JSON {n, edges, src, dst, k} with edges [u, v, w].

Output: Integer — the cheapest price, 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 costs 700 within 1 stop.

Input: {"n":3,"edges":[[0,1,100],[1,2,100],[0,2,500]],"src":0,"dst":2,"k":1}
Output: 200
Explanation: 0->1->2 within 1 stop.

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

Constraints

• 1<=n<=1000
• 0<=k<n
• directed

Asked by