Submit Best Submissions All Submissions

320. Second Minimum-Maximum Edge


Problem Statement:
With the start of this year, Goodname Good started attending IFLHT (International Fegla's Local Home Training). Part of the training was explaining solutions to each other, with the Coach explaining as well for a fair amount of time. Although the Coach is specially famous for his patience and ability to repeat and to explain from different angles, Goodname as a reader of one chapter of an unexpectedly amusing mathematics book was dissatisfied with the way everyone talked. They'd use analogies and imaginary thinking instead of solid mathematical statements! This actually makes it more difficult to understand in Goodname's opinion. (You'll know how he feels when you read this chapter). So, it was decided that this problem be written in that way for the sake of Goodname's temper. Don't worry, no special notation will be used. Define a function F1 that takes as input an integer K, and a set of unique integers S and returns integer X, such that there are exactly K - 1 integers in the set greater than X. Of course, the function is undefined for some values such as when K is greater than the size of the set or non-positive. In this problem, you'll be given an integer K and an undirected weighted graph where costs of edges are unique. N is the number of nodes in the graph. There could be several paths P1, P2, ..Pl between node 1 and node N. Assume a function F2 that takes a path and returns the costs of its edges as a set. Output the minimum element of {F1(K, F2(P1)), F1(K, F2(P2)), .. ,F1(K, F2(Pl))}. There's always a path between node 1 and N. Consider only paths in which you don't visit a node more than once.


Input Format:
The input will start with an integer T which is the number of test cases where (1 ≤ T ≤ 100). Each test case start with a line with 3 integers N, E, and K representing the number of nodes, number of edges, and the described K respectively where (2 ≤ N ≤ 10, 000), (1 ≤ E ≤ 12, 500), and (1 ≤ K ≤ N - 1). Then follow E lines each of them has 3 integers U, V, and C, meaning that there's a path between nodes U and V with cost C where (1 ≤ U, V ≤ N), and (1 ≤ c ≤ 108).


Output Format:
For each test case you should output "Case X: Y" where X is the case number starting from 1, and Y is the minimum largest edge. In other words, minimum element of {F1(K, F2(P1)), F1(K, F2(P2)), .. ,F1(K, F2(Pl))}.


Sample Input:
1 5 8 1 2 5 6 1 2 9 2 4 7 2 3 7 3 1 9 1 5 8 5 3 3 4 1 10


Sample Output:
Case 1: 8





Added by: hossamyosef
Added at: 2014-11-11 15:32:31 UTC
Time Limit: 5 seconds
Partial score: No
Source:ACM Jordanian Collegiate Programming Contest 2014