Description
Neal is a karting rider. To win the competition, he practiced hard on the track every day. Each track has a designated path. Neal needs to find the best path from the starting point to the finish line to get a good score.
You will be given a directed weighted graph as the racetrack. The graph has n nodes, where each node represents a track record point, and the edge between two nodes indicates that there is a path between these two points. Each edge will have a weight representing the time it takes to passing the path.
Two nodes in the graph will be used as the starting point and the ending point respectively. Please find the shortest time Neal can run when passing through at most k nodes ( record points ). If such a path cannot be found, return -1.
Note that the node indices start from 1.
Take the above graph as example. Let node 3 be the starting point and node 4 be the finishing point, and we can only pass 2 record point at most.
Although the path with minimum time will be 3 -> 2 -> 1 -> 6 -> 4, but it has 3 record points. The answer therefore should be 3 ->2->6->4, and you need to print 29 as the output.
All STL library are forbidden.
Remember that the answer should be followed by a newline.
Input
The first line contains a pair of integers N and E, which are the numbers of nodes and edges, respectively.
The second line includes three integers, i.e., s, f, k, which specify the starting point, finish point, and the maximum number of nodes that can be passed, respectively.
The following E lines each contains a triplet u, v, w, which represents an edge between node u and node v with the time that it takes to pass, w (w is a positive integer).
1 <= N <= 10000
0 <= E <= N(N-1)/2
0<= s, f, k <= N
1 <= w <= 10000
Output
Return the minimum time from the start point to the finish point by passing through at most k record points. If there are no such route, return -1.