All submissions for this problem are available.
A district in a state has K villages (numbered from 1 to K). In order to provide better road connectivity in the district, the government has connected all the villages with two-lane paved roads, However, to reduce costs, the roads are constructed such that while it is possible to go from any village to any other village using the paved roads, there is exactly one route between any two villages. In addition, M of these villages are also connected to the district headquarter directly using two-lane roads.
Elections are round the corner and a leader of a political party wishes to hold road shows in the villages. Since he does not have time to visit all the villages, he decides to go from the district headquarter to one of the villages that is connected to it, and then follow a path using the roads between the villages only, holding one road show at each village in the path as and when he reaches that village. Since he has to return to the district headquarter, he wishes to hold the last road show in a village that is again connected to the district headquarter. To save time, he also does not want to go through any village more than once.
Obviously, he cannot go through all the villages. To ensure that people in other villages (not on the path) are not deterred from coming to his road shows, he asks his assistant to chalk a route such that the sum total of the distances of any village from its closest village in the path is minimized. The road show being still a week off, he asks his assistant to take all the time he wants, but make sure that he finds the correct path.
The assistant sets off to do this, trying to write a program to try out one-by-one all the different paths the leader can take and calculating the total distances people have to travel if a person in a village goes to the road show nearest to his village. Help him write this program.
The first line contains the number of test cases N.
For each test case, the first line contains the number of villages K. This is followed by K lines, with the j-th line containing the information about village j. The information for each village consists of (in this order): an integer F (0 if the village is not connected to the district headquarter, 1 if it is), an integer D indicating the number of other villages this village is directly linked to by road, followed by D pairs of integers (total 2D integers), with each pair containing the id (from 1 to K) of a village it is connected to and the distance (positive integer) from that village.
For each test case, print the case number, followed by a colon, followed by a single space, followed by a single integer indicating the sum total of distance of all the villages from their closest village in the path chosen.
0 < N ≤ 3
0 < K ≤ 50
Input: 2 5 0 3 2 10 3 8 4 15 1 1 1 10 1 1 1 8 1 2 1 15 5 12 0 1 4 12 7 0 2 2 5 6 20 0 3 1 5 4 10 5 5 1 1 6 3 1 1 2 10 0 1 2 5 1 3 1 20 7 10 3 3 1 1 6 10 Output: Case 1: 20 Case 2: 8
|Tags||floyd-warshall, kgp13acm, shangjingbo, tree|
|Time Limit:||0.943333 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.