Metro circular
Estamos desarrollando un app para planificar rutas en metro. Ya la tenemos casi lista, pero hay algunas líneas que son circulares y nos traen de cabeza.
En estas líneas de metro circulares hay trenes dando vueltas en los dos sentidos. Así que si un pasajero quiere ir de una estación A a otra estación B, puede viajar en cualquiera de los dos sentidos. Claro está que en un sentido el viaje puede ser más corto que en el otro.
Nuestra app, debe informar cuál es la ruta más corta entre las estaciones de origen y destino seleccionadas por el usuario, informando del tiempo total de viaje y de todas las paradas intermedias.
Input Format
El primer número indica la cantidad de estaciones.
A continuación vienen los nombres de cada estación (una palabra).
A continuación vienen los tiempos de trayecto entre estaciones (en segundos): El primer tiempo corresponde al tiempo de viaje entre la primera y la segunda estación, y así sucesivamente, de forma que el último tiempo corresponde al tiempo entre la última y la primera. Los tiempos de viajes entre las estaciones son los mismos en ambos sentidos.
Por último vienen los nombres de las estaciones de origen y destino.
Constraints
Se garantiza que los tiempos de viaje en ambos sentidos entre origen y destino son distintos.
Output Format
Se imprimirán los nombres de las estaciones de la ruta más corta, cada una en una nueva línea.
Al final se imprimirá el tiempo total de viaje (en segundos).
Sample Input 0
7
A B C D E F G
100 300 200 100 400 100 200
B E
Sample Output 0
B
C
D
E
600
Explanation 0
Sample Input 1
5
A B C D E
100 300 400 200 500
A D
Sample Output 1
A
E
D
700
Explanation 1
Sample Input 2
4
A B C D
100 100 100 100
A D
Sample Output 2
A
D
100
Explanation 2
Sample Input 3
4
A B C D
100 100 100 400
A D
Sample Output 3
A
B
C
D
300
Explanation 3
Sample Input 4
7
A B C D E F G
100 300 200 100 400 100 200
E B
Sample Output 4
E
D
C
B
600
Explanation 4
Sample Input 5
5
A B C D E
100 300 400 200 500
D A
Sample Output 5
D
E
A
700
Explanation 5
Sample Input 6
4
A B C D
100 100 100 100
D A
Sample Output 6
D
A
100
Explanation 6
Sample Input 7
4
A B C D
100 100 100 400
D A
Sample Output 7
D
C
B
A
300
Explanation 7
Sample Input 8
10
Laguna Carpetana Oporto Usera Legazpi Arganzuela Pacifico Conde Baranda ODonell
300 400 350 220 550 430 290 190 400 100
Carpetana Pacifico
Sample Output 8
Carpetana
Laguna
ODonell
Baranda
Conde
Pacifico
1280
Sample Input 9
10
Laguna Carpetana Oporto Usera Legazpi Arganzuela Pacifico Conde Baranda ODonell
300 400 350 220 550 430 290 190 400 100
Pacifico Carpetana
Sample Output 9
Pacifico
Conde
Baranda
ODonell
Laguna
Carpetana
1280
Sample Input 10
10
Laguna Carpetana Oporto Usera Legazpi Arganzuela Pacifico Conde Baranda ODonell
300 400 350 220 550 430 290 190 400 100
Arganzuela ODonell
Sample Output 10
Arganzuela
Pacifico
Conde
Baranda
ODonell
1310
Autoria: Gerard Falcó
CC BY-NC-SA 4.0