There is a small kingdom. The kingdom consists of N towns and each town has
some residents.
Some pairs of towns are connected by bidirectional highways such that there is
exactly one highway path between each pair of towns. The king wants to select M
towns to build super squares in them so that the residents in the kingdom can gather in
these super squares to celebrate new years together. For some security reason, the
selected M towns must satisfies the condition that starting from any selected town,
someone can reach any other selected town by highways without passing through any
town which is not selected.
Each highway has a length. People always travel to the nearest town with a super
square to celebrate new years.
The king wants to make the total distance people have to travel to celebrate every
new year as small as possible. You are to help the king. The total distance is the
summation of distance every resident travel.
The input consists of multiple test cases. Each test case starts with a line
containing two integers N(2<=N<=2,000) and M (1<=M<=N, M<=500).
The following line contains N positive integers, the i-th of which is the number of
resident in the i-th town and will not be greater than 1000.
Each of the next N-1 lines contains three integers a, b and c (1<=a<b<=n,
1<=c<=1,000), which means there is a bidirectional highway between the a-th town
and the b-th town and the length of the highway is c kilometers.
The last test case is followed by a line containing two zeros.
For each test case, print a line containing the test case number( beginning with 1)
followed by the minimum total distance people has to travel.
3 1 1 2 3 1 2 2 1 3 3 3 2 100 10 100 1 2 1 2 3 1 0 0
Case 1: 13 Case 2: 100
Migrated from old NTUJ.
2009Hefei
| No. | Testdata Range | Score |
|---|