Woburn Challenge 1999 - Suicidal
The Star Wars franchise has been so secretive about the plot of the next movies that even their most die-hard fans have been fooled into thinking that Darth Vader uses the Force to track down the Jedi Knights. However, what they don't realize is that Star Wars is really an autobiography of George Lucas. If you don't want to know the plot of the movie, skip to the next problem because some shocking details will be revealed. First, George Lucas is really the Emperor of the Dark Side. Second, he will actually use his acquired wealth (from the first movies) to bribe weak-minded Jedi into revealing information leading to the capture of other Jedi. Lastly, being a greedy impresario, he obviously wants to minimize the total amount of bribes he hands out. So here is the situation he faces:
There are Jedi, each with knowledge that will reveal the location of or more other Jedi.
Some of these Jedi can be bribed into revealing the location of others. The Jedi are a little greedy and so each one has a price list that he will use to determine the price of bribery, i.e. each Jedi he can compromise has a price and for that price, only that one Jedi will be compromised. Say that Jedi knows the location of Jedi and . He will give up Jedi for and for . If you bribe him with , he will only give up . If you then want to reveal , you have to bribe him again with to reveal .
If you find out the location of a Jedi (by bribing somebody else), you can then use the persuasion powers of the Force to make the captured Jedi reveal everybody he knows about - obviously, these revelations will come at no cost.
Somehow, you have acquired a list of all Jedi and the prices they
charge. You want to come up with a bribery plan such that all Jedi can
be captured at a minimum cost. If all the Jedi can be caught, output the
minimum bribe required. However, if all the Jedi cannot be caught,
output IMPOSSIBLE
. Note that bribing a Jedi doesn't mean that he has
been captured. Note that there will be at most spies and at most
possible briberies to do.
Input Specification
Line : # of input sets
The next lines will contain each input set.
Each input set will terminate with a 0 0 0
.
st line of input set: # of spies.
Next few lines: X Y n
(means that can be bribed for to reveal )
Output Specification
For each test case, output the cheapest price for which all the Jedi can
be caught, and IMPOSSIBLE
if it can not be done.
Sample Input
1
4
1 2 1
2 3 1
3 4 1
4 1 1
0 0 0
Sample Output
1
Comments