|
G |
Gentle
ping, to the old King |
All of you must have heard
the name of The Lord of the Rings. As
we know that the ring, that was said to be the lord of the rings, was destroyed
by Frodo Baggins in the mountain of
doom. And so, the evil spirit Sauron
was not able to capture the ring and was finally destroyed. After defeating Sauron’s army, Aragorn became the king and with his coronation the world moved
into the dominion of Men. And they lived happily ever after.
But that’s not actually the whole story. Defeating Sauron was not the final victory over
"evil" as such. Because the evil dark lord and Sauron’s master - Morgoth
can still recover, grow and take shape again.
After the death of Sauron, many years have passed. Aragorn
is old now and his son Eldarion is
the king. Things were going fine except one day they discovered the fact that Morgoth has recovered his powers and is
planning to take over the world. The whole middle Earth is again waiting for
another war.
Eldarion has made several plans with
the wise council to stop Morgoth.
They have the map, so they are aware of the fact that there are some
territories in Middle-Earth. Many two-way roads exist between some pairs of
territories. The times to travel all roads are known to them. To go from a
territory to another one, they can use one or more roads. And all territories
are reachable from any territory.
That’s why they have the fear that if Morgoth’s army enters to any territory
then they can invade any territory they want. To protect a road, huge number of
armies has to be placed there.
Eldarion is a man of honor like his
father. So, he doesn’t want to leave any territory unguarded or weak. But since
his armies are little in number compared to Morgoth’s,
he is at a loss. Cause if he sends armies to protect the roads then they may
win, but some territories might go down. But if he sends the armies to protect
the territories, then if any territory goes down, more will be in danger
because Morgoth’s army will forward
their march using the unguarded roads and of course they can capture roads and
can hamper the communication amongst territories. But if Eldarion places armies to protect both roads and territories then
both roads and territories will be weak since the number of armies protecting a
territory or a road will be too low to fight against Morgoth’s army.
After a long discussion, they have got many ideas,
but no idea fascinated Eldarion. So,
he went to his father, Aragorn - the
old king. Aragorn took a day to
think, and the next day he told his son about his idea. The idea is to keep as
fewer roads as possible such that the armies can still be sent from any
territory to all other territories. Rest of the roads will be destroyed. As
they have many trebuchets and catapults, they can destroy roads easily and
without heavy effort.
After that they will pick some territories that have
the higher chances to be attacked first. These territories will be selected by
Aragorn himself from his past experience in battles, and these are called the prime territories. All the armies will
be assigned to protect these territories only. When a territory is under
attack, either prime or non-prime, the informers in this territory will seek
help from a prime territory. This
helping territory will be randomly chosen. After the arrival of the armies, the
informers will seek help from another randomly chosen prime territory. And they will continue seeking help until armies
from all the prime territories come.
The informers will always choose a new prime
territory for seeking help. So, the estimated
time for a territory is the total required time for armies from all prime territories to reach this
territory. And the Total estimated time
is the summation of estimated times
of all territories. You can assume that the time to inform other territories is
negligible.
Now, they are planning to use Aragorn’s idea. So, they want to keep the roads such that the Total estimated time is as low as possible.
You are one of the head councilors and you know the map fully. Now you have to
find the minimum Total estimated time.
Remember that the whole middle earth is depending on you.
Input
The first line of the input will contain T (<= 100), denoting the number of
cases.
Each case starts with a blank line. The next line
will contain three integers n (2<=n
<= 16), m and k (1 <= k <= n), where n is the number of territories, m is the total number of roads and k is the number of prime territories. The territories are numbered from 0 to n – 1. The next line contains k
integers separated by spaces. These integers denote the prime territories. Each of the next m lines will contain three integers u, v (0 <= u, v < n and u != v) and w (1 <= w <= 1000) denoting that there is a two way road
between territory u and v and the time to cross this road is w minutes. You can assume that all the
roads are valid, no road is listed more than once and multiple roads between
same pair of territories don’t exist.
Output
For each case, print the case number and the minimum
Total estimated time.
|
Sample Input |
Sample Output |
|
2 3 2 1 0 0 1 2 1 2 5 3 3 2 0 2 0 1 2 1 2 5 0 2 50 |
Case 1: 9 Case 2: 21 |
Problemsetter: Jane Alam Jan Special Thanks: Md. Arifuzzaman
Arif