Woburn Challenge 2016-17 Round 1 - Senior Division

Problem 2: Alucard's Quest

What a horrible night to have a curse! Alucard has returned to the ancient castle of his evil father, Dracula, determined to wake him from his slumber and then destroy him once and for all. However, something tells him that it won't be easy - though Dracula remains fast asleep in his coffin for now, his monstrous servants are scattered throughout the castle, armed to the teeth and hungry for blood.

The castle consists of N (1 ≤ N ≤ 200,000) chambers, with N − 1 passageways running between them. The i-th passageway connects distinct chambers Ai and Bi (1 ≤ Ai, Bi ≤ N), and has Mi (1 ≤ Mi ≤ 5000) monsters in it. It's possible to reach any chamber from any other chamber by following a sequence of one or more passageways – in other words, the system of chambers and passageways forms a tree structure when modelled as a graph.

Dracula's resting place is in the 1st chamber, and fortunately for Alucard, he's already infiltrated the castle and also finds himself in the 1st chamber! However, he's realized that he's not quite ready to battle Dracula yet. In order to stand a chance, Alucard will surely need some holy water, stronger weapons (a whip should come in handy), a wider range of magical spells to cast, and of course an oak stake to plunge into his father's heart and finish him off permanently. In particular, Alucard will first need to gather K (1 ≤ K < N) items. Conveniently, all of these items can be found in distinct chambers of Dracula's castle, with the i-th item in chamber Ci (2 ≤ Ci ≤ N).

Alucard will need to travel around the castle through its passageways, starting from the 1st chamber, visiting all K chambers that contain his required items (in any order), and arriving back in the 1st chamber to finally wake and confront Dracula. If he chooses to travel through a passageway that contains m monsters, he'll first need to destroy them by casting a spell and using up m of his "magic points". That passageway will then be permanently cleared of monsters, so he'll be able to freely travel through it any number of times afterwards.

Conserving magic points for his battle with Dracula is vital, so Alucard will need to carefully plan out a route through the castle which will allow him to collect all K items while requiring him to use as few magic points as possible. Can you help him?

In test cases worth 3/20 of the points, N ≤ 1000 and K = 1.
In test cases worth another 7/20 of the points, N ≤ 1000.

Input Format

The first line of input consists of two space-separated integers N and K.
N − 1 lines follow, with the i-th of these lines consisting of three space-separated integers Ai, Bi, and Mi (for i = 1..N − 1).
K lines follow, with the i-th of these lines consisting of a single integer Ci (for i = 1..K).

Output Format

Output one line consisting of a single integer – the minimum number of magic points required for Alucard to collect all K items and return to Dracula's chamber.

Sample Input

7 4
1 2 5
1 7 2
2 4 3
2 5 8
5 6 1
7 3 10
4
5
3
7

Sample Output

28

Sample Explanation

One optimal route that Alucard can take, passing through all 4 chambers that contain items and then returning to the 1st chamber, is as follows:

  • 1 → 7 (2 magic points)
  • 7 → 3 (10 magic points)
  • 3 → 7 (already cleared)
  • 7 → 1 (already cleared)
  • 1 → 2 (5 magic points)
  • 2 → 4 (3 magic points)
  • 4 → 2 (already cleared)
  • 2 → 5 (8 magic points)
  • 5 → 2 (already cleared)
  • 2 → 1 (already cleared)

The total number of magic points required on this route is 2 + 10 + 5 + 3 + 8 = 28.

All Submissions
Best Solutions


Point Value: 10 (partial)
Time Limit: 4.00s
Memory Limit: 64M
Added: Oct 16, 2016
Author: SourSpinach

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

Comments (Search)

It's quiet in here...