You are given an undirected graph with n nodes labeled from 0 to n - 1. The graph consists of m edges represented by a 2D integer array edges, where edges[i] = [ui, vi, wi] indicates that there is an edge between nodes ui and vi with a repair cost of wi.
You are also given an integer k. Initially, all edges are damaged.
You may choose a non-negative integer money and repair all edges whose repair cost is less than or equal to money. All other edges remain damaged and cannot be used.
You want to travel from node 0 to node n - 1 using at most k edges.
Return an integer denoting the minimum amount of money required to make this possible, or return -1 if it is impossible.
Example 1:
Input: n = 3, edges = [[0,1,10],[1,2,10],[0,2,100]], k = 1
Output: 100
Explanation:
The only valid path using at most k = 1 edge is 0 -> 2, which requires repairing the edge with cost 100. Therefore, the minimum required amount of money is 100.
Example 2:
Input: n = 6, edges = [[0,2,5],[2,3,6],[3,4,7],[4,5,5],[0,1,10],[1,5,12],[0,3,9],[1,2,8],[2,4,11]], k = 2
Output: 12
Explanation:
money = 12, all edges with repair cost at most 12 become usable.0 -> 1 -> 5, which uses exactly 2 edges and reaches node 5.money < 12, there is no available path of length at most k = 2 from node 0 to node 5.Example 3:
Input: n = 3, edges = [[0,1,1]], k = 1
Output: -1
Explanation:
It is impossible to reach node 2 from node 0 using any amount of money. Therefore, the answer is -1.
Constraints:
2 <= n <= 5 * 1041 <= edges.length == m <= 105edges[i] = [ui, vi, wi]0 <= ui, vi < n1 <= wi <= 1091 <= k <= nLoading editor...
3 [[0,1,10],[1,2,10],[0,2,100]] 1