Problem O
Lost in Translation
The word is out that you’ve just finished writing a book
entitled How to Ensure Victory at a
Programming Contest and requests are flying in. Not
surprisingly, many of these requests are from foreign
countries, and while you are versed in many programming
languages, most spoken languages are Greek to you. You’ve done
some investigating and have found several people who can
translate between languages, but at various costs. In some
cases multiple translations might be needed. For example, if
you can’t find a person who can translate your book from
English to Swedish, but have one person who can translate from
English to French and another from French to Swedish, then
you’re set. While minimizing the total cost of all these
translations is important to you, the most important condition
is to minimize each target language’s distance (in
translations) from English, since this cuts down on the errors
that typically crop up during any translation. Fortunately, the
method to solve this problem is in Chapter
Input
Input starts with a line containing two integers
Output
Display the minimum cost to translate your book to all of
the target languages, subject to the constraints described
above, or Impossible if it is not possible.
You may assume that the minimum cost can be represented by a
signed
Sample Input 1 | Sample Output 1 |
---|---|
4 6 Pashto French Amheric Swedish English Pashto 1 English French 1 English Amheric 5 Pashto Amheric 1 Amheric Swedish 5 French Swedish 1 |
8 |
Sample Input 2 | Sample Output 2 |
---|---|
2 1 A B English B 1 |
Impossible |