| [Home|Training|Problems|Contests|C Language] | [Login|Register] |
|
Problems Status Rank |
Problem 1133
Super squares
Time Limit: 3000ms
Memory Limit: 65536kb Description
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. Input
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<=1000).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. Output
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.
Sample Input
3 1 1 2 3 1 2 2 1 3 3 3 2 100 10 100 1 2 1 2 3 1 0 0 Sample Output
Case 1: 13 Case 2: 100 |