|
I I U P C 2 0 1 3 |
|
|
Problem C: The Twin Head Dragon |
|
|
|
|
|
The Scourge are marching South-West with the biggest army ever seen, and they're marching fast. All the Sentinel towers are in ruins. There's chaos all over their base. Whatever they have to do, they have to do it by tonight or they will be terminated from the face of the earth tomorrow.
A secret meeting is being conducted by Zeus, the lord of Olympus and the father of gods. "The end is near." dreads Sven. "Careful child. Sentinel will not be doomed before my eyes." says Zeus. "Send Riki to explore the enemy camps. Then we can come up with a plan."
Riki comes with the information that there are N enemy camps and N-1 bi-directional roads, each road connecting two camps. The lengths of the roads are different. Riki also found that there exists a path between any pair of camps.
"That's enough information!" says Zeus with excitement, "We have to burn down all the roads, so the enemies will be isolated from each other. Then we will strike. Summon Jakiro, he'll know what to do."
Jakiro, the Twin Head Dragon is summoned. He will use his ultimate spell, Macropyre to burn all the roads down. To do this he will follow these steps:
1) Select 2 different camps such that the shortest path between them doesn't include any burned road. 2) Prepare the spell with required mana. The mana cost for this spell is equal to the average of the lengths of roads in the path. 3) Burn all roads in the selected path.
He will keep burning this way until all the roads are burning. It is important that he uses minimum total mana for this task, as he needs mana for the battle afterwards. Now write a program to calculate the least mana required by Jakiro to burn all the roads down. Remember, you dont need to minimize the number times the spell is used.
|
|
|
Input |
|
|
The input will contain multiple test cases and number of test cases ≤ 50. Each case starts with an integer N (2 ≤ N ≤ 14) denoting the number of enemy camps. The camps are numbered from 0 to N-1. Each of the next N-1 lines contain three integers A B C (0 ≤ A, B < N, A ≠ B, 1 ≤ C ≤ 10000) denoting that camp A and B are connected by a road whose length is C units. You may assume that all pairs of A & B are unique. The input terminates with a value 0 for N.
|
|
|
Output |
|
|
For each case, print on a line the least total mana required by Jakiro rounded upto exactly 4 decimal points.
|
|
|
Sample Input |
Output for Sample Input |
|
4 0 2 1 1 2 2 2 3 3 6 0 1 10000 0 2 10000 0 3 1 0 4 1 0 5 10000 0
|
3.5000 15001.5000
|
|
|
|
|
|
|
|
Output Explanation |
|
In sample test 1, if we first select camps 1 & 3 and use spell on the path 1 2 3, the required mana would be (2+3)/2 = 2.5 . Then we select camps 0 & 2 and use spell on the path 0 2 which would require 1/1 = 1 mana. So the total mana required to burn all the roads is 2.5 + 1 = 3.5, which is the minimum value possible.
In sample test 2, we can use spell on paths 1 0 2, 0 3 and 4 0 5. It would cost mana (10000+10000)/2 = 10000, 1/1 = 1 and (10000+1)/2 = 5000.5 respectively. In total it would cost 10000 + 1 + 5000.5 = 15001.5 mana, which is the optimal value.
|
|
|
|
Problem Setter : Sakib Hasan Sauro Alternate Solution : Ashiqul Mostofa |