Conociendo a Miguel

Submit solution
Points: 100 (partial)
Time limit: 2.0s
Java 8 4.0s
Python 6.0s
Memory limit: 256M
Java 8 2G
Author:
ymondelo
Problem type
Allowed languages
Ada, Assembly, Awk, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Lua, Pascal, Perl, Prolog, Python, Scala, Swift, VB

Description

Siempre he pensado que algún día conoceré al profesor Miguel, que me ha permitido organizar tantos concursos. Pero he logrado perder todas las oportunidades en la realidad. Finalmente, con la ayuda de un mago, logré encontrarme con él en la mágica Ciudad de la Esperanza. La ciudad de la esperanza tiene muchos caminos. Algunos de ellos son bidireccionales y otros son unidireccionales. Otra propiedad importante de estas calles es que algunas de ellas son para personas cuya edad es menor de treinta años y el resto son para otras. Esto es para dar libertad a los menores en sus actividades. Cada calle tiene una cierta longitud. Dada la descripción de dicha ciudad y nuestras posiciones iniciales, tendrá que encontrar el lugar más adecuado donde podamos encontrarnos. El lugar más adecuado es el lugar donde nuestro esfuerzo combinado de alcance es mínimo. Puedes asumir que tengo 25 años y el profesor Miguel tiene más de 40 años.

First meeting after five years of collaboration (Shanghai, 2005)...

Input specification

La entrada contiene varias descripciones de ciudades. Cada descripción de ciudad se inicia con un entero N, que indica cuántas calles hay. Las siguientes N líneas contienen la descripción de N calles.

La descripción de cada calle consta de cuatro alfabetos en mayúsculas y un entero. El primer alfabeto es 'Y' (indica que la calle es para jóvenes) o 'M' (indica que el camino es para personas de 30 años o más) y el segundo carácter es 'U' (indica que la calle es unidireccional ) o 'B' (indica que la calle es bidireccional). Los caracteres tercero y cuarto, X e Y pueden ser cualquier alfabeto en mayúsculas e indican que los lugares denominados X e Y de la ciudad están conectados (en caso de unidireccional, significa que hay una calle de un solo sentido de X a Y) y el el último entero no negativo C indica la energía requerida para caminar por la calle. Si estamos en el mismo lugar, podemos encontrarnos sin costo alguno. Cada valor energético es inferior a 500.

Después de la descripción de la ciudad, la última línea de cada entrada contiene dos nombres de lugares, que son la posición inicial de mí y del profesor Miguel respectivamente. Un valor cero para N indica el final de la entrada.

Output specification

Para cada conjunto de entrada, imprima el costo mínimo de energía y el lugar, que es el más adecuado para nosotros. Si hay más de un lugar para reunirse, imprímalos todos en orden lexicográfico en la misma línea, separados por un solo espacio. Si no hay lugares donde podamos reunirnos, imprima la línea "You will never meet.".

Sample input

4
Y U A B 4
Y U C A 1
M U D B 6
M B C D 2
A D
2
Y U A B 10
M U C D 20
A D
0

Sample output

10 B
You will never meet.

Comments