The people of District 13 have just learn that the villain Rose is planning an attack to cut the communication between certain districts to incapacitate Katniss Everdeen and her team. They also posses the name of these districts, however they do not know that which lines the villain will attack. But Katniss senses that, since Rose would desire to finish the job quickly, he will cut the minimum number of lines and he wants to cut the ones that would take less time to cut.
As a valuable team member of Katniss Everdeen, your job is to detect the lines that Rose would attack and calculate the minimum time needed to cut these lines to report how much time left and deploy your army to the correct locations.
2 Input & Output
As usual you are going to use files whose names are specified through terminal for input and output. The files will be in the following format:
The First line: Two integers N and D, number of districts and the number of the districts Rose will try to cut the communication between.
The following N-1 lines: 3 integers, the specifications of communication lines, two integers to specify the id of the cities and one integer to specify time needed to cut the line, respectively. The following D lines: Integers that are the IDs of the districts that Rose will try to cut the communication between.
As output you are going to print just one integer, that is the minimum amount of time needed to cut the communication. You are NOT going to print the lines since the ordering of the lines and the lines themselves may differ between implementations (i.e. There may have been multiple answers for this case).
Here is a sample input and output:
|12 30 1 30 2 102 3 82 5 92 4 124 7 174 6 156 9 69 8 58 11 1310 11 19 2611
Table 1: Sample Input and Output
Figure 1: Representation of the sample test case.
Explanation of the sample test case
Note that according to the input file, it is known that Rose wants to cut the communication between the districts 2, 6 and 11. According to Katniss’ anticipation he will attack to the line between 2 and 4 and the line between 8 and 11 since cutting these lines will be the quickest and sufficient way of blocking the communication. Since time needed to cut these lines will be 12 + 5 = 17, you are expected to print 17 in this case.
- The input graph will always be a tree and contain N-1 edges.
- Did you notice that when the red edges above are removed, the graph has 3 components left – and 3 is a part of the input?
Think about using a cool data structure you learned in this semester