National Olympiad in Informatics, China, 2002

Day 1, Problem 3 - The Greedy Kuzuryū

The mythical Kuzuryū (nine-headed dragon) is an incredibly greedy creature. Although it is called the "nine-headed dragon", this only refers to how it has nine heads when it is born. As it grows up, it will eventually sprout many new heads, totalling a number far greater than nine. Of course, there will always be old heads that fall off as a result of aging.

One day, a Kuzuryū with M heads witnesses a fruit tree containing N fruits. Ecstatic, it simply wants to eat them all in one bite. However it must take care of each head, so it needs to split the N fruits into M groups, one for each head to eat, with at least one fruit per group.

Among these M heads there exists a largest one, known as the "boss", and it serves as the leader of all the heads. This head would like to eat exactly K fruits, and these K fruits should naturally contain the one and only largest fruit. The fruits are joined using N−1 branches; due to the fruit tree being a whole, it is possible to start at a fruit and "arrive at" any other fruit by traveling along its branches.

Regarding each tree branch segment: If the two fruits it connects require different heads to eat, then the two heads together will break the branch and split up the fruits. If the two fruits are eaten by the same head, then this head will not be bothered to break the branch, and will consequently just eat the entire branch along with the fruits. Of course, eating branches is not too comfortable, so every branch possesses a "pain value" for being eaten. Furthermore, the pain that the Kuzuryū experiences is the sum of the pain values for all of the branches that it has eaten.

The Kuzuryū would like keep the pain that it experiences to a minimum. Can you help calculate this value?

In this example for N = 8, M = 2, and K = 4: there are 8 fruits, 7 branches, and the "pain value" of each branch is labeled besides the branch. The Kuzuryū has two heads. The boss needs to eat 4 fruits, one of which must be the largest fruit.

The larger head (boss) eats 4 fruits, depicted by the black dots.
The smaller head eats 4 fruits, depicted by the white dots.
The Kuzuryū experiences a pain of 4, since it eats the branch with a pain value of 4, denoted by a thin line.

The first diagram indicates the status of the fruit tree, while the second diagram illustrates the optimal eating strategy.

Input Format

The first line of contains three integers N (1 ≤ N ≤ 300), M (2 ≤ M ≤ N), and K (1 ≤ K ≤ N). N indicates the number of fruits, labeled 1, 2, … N. The largest fruit is always fruit number 1. Line 2 to line N describe the status of the fruit tree, with each line containing three integers a (1 ≤ a ≤ N), b (1 ≤ b ≤ N), and c (0 ≤ c ≤ 10⁵), indicating that the branch connecting fruit a and fruit b has a pain value of c.

Output Format

The output should consist of one line containing a single integer - the minimum possible pain that the Kuzuryū needs to experience under the conditions discussed above. If the conditions cannot be satisfied, output -1.

Sample Input

8 2 4
1 2 20
1 3 4
1 4 13
2 5 10
2 6 12
3 7 15
3 8 5

Sample Output

4

All Submissions
Best Solutions

Point Value: 25 (partial)
Time Limit: 2.00s
Memory Limit: 16M
Added: May 11, 2014

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)