Problem D
Meeting Prof. Miguel
Input: standard input
Output: standard output
Time Limit: 5 seconds
I have always thought that someday I will meet
Professor Miguel, who has allowed me to arrange so many contests. But I have
managed to miss all the opportunities in reality. At last with the help of a
magician I have managed to meet him in the magical City of Hope. The
city of hope has many roads. Some of them are bi-directional and others are
unidirectional. Another important property of these streets are that some of
the streets are for people whose age is less than thirty and rest are for the
others. This is to give the minors freedom in their activities. Each street has
a certain length. Given the description of such a city and our initial
positions, you will have to find the most suitable place where we can meet. The
most suitable place is the place where our combined effort of reaching is
minimum. You can assume that I am 25 years old and Prof. Miguel is 40+.
Input
The input contains several descriptions of cities. Each description of city is started by a integer N, which indicates how many streets are there. The next N lines contain the description of N streets.
The description of each street consists of four uppercase alphabets and an integer. The first alphabet is either ‘Y’ (indicates that the street is for young) or ‘M’ (indicates that the road is for people aged 30 or more) and the second character is either ‘U’ (indicates that the street is unidirectional) or ‘B’ (indicates that the street is bi-directional). The third and fourth characters, X and Y can be any uppercase alphabet and they indicate that place named X and Y of the city are connected (in case of unidirectional it means that there is a one-way street from X to Y) and the last non-negative integer C indicates the energy required to walk through the street. If we are in the same place we can meet each other in zero cost anyhow. Every energy value is less than 500.
After the description of the city the last line of each input contains two place names, which are the initial position of me and Prof. Miguel respectively.
A value zero for N indicates end of input.
Output
For each set of input, print the minimum energy cost and the place, which is most suitable for us to meet. If there is more than one place to meet print all of them in lexicographical order in the same line, separated by a single space. If there is no such places where we can meet then print the line “You will never meet.”
Sample Input:
0
Sample
Output
“All primes are odd except
2, which is the oddest of all.”