Retos de programación - 014: Ruta más rápida

Muchas ciudades ofrecen un sistema integral de transporte público, a menudo la integración de rutas de autobuses, servicios suburbanos de trenes de cercanías y ferrocarriles subterráneos. Las rutas en estos sistemas se pueden clasificar de acuerdo a las estaciones o paradas a lo largo de ellas. Normalmente pensamos en ellos como líneas (donde los vehículos van de un extremo de la ruta al opuesto y vuelven), bucles (donde los dos extremos de la "rama" son los mismos y los vehículos recorren el sistema en ambas direcciones ) y las conexiones, donde un punto de la ruta se conecta con otra ruta. Nótese que los vehículos pueden viajar en ambas direcciones a lo largo de todas las rutas, y que sólo es posible cambiar entre rutas en las estaciones de conexión.

Para simplificar las cosas, cada ruta se designará con una letra de la 'A' a la 'Z', y cada estación de una ruta por otra letra de la 'a' (minúscula) a la 'z'. Las estaciones de conexión tendrán más de una designación. Así, un ejemplo podría ser:

Un problema común en tales sistemas es encontrar una ruta entre dos estaciones dadas. A partir de ello, queremos encontrar la "mejor ruta", donde "mejor" se refiera a "de menor tiempo".

Escriba un programa que lea los detalles de este sistema y, a continuación enccuentre las rutas más rápidas entre los pares de estaciones indicados. Se puede asumir que el viaje entre las estaciones siempre tiene una unidad de tiempo y que el cambio entre las rutas en una estación de conexión es de 3 unidades de tiempo.

Entrada

La entrada se compone de dos partes. La primera constará de una descripción de un sistema; la seguda constará de pares de estaciones. La descripción se iniciará con un número entre 1 y 26 que indica cuántas rutas hay en el sistema. A continuación, habrá esa cantidad de líneas, cada una de las cuales describe una sola ruta. Cada línea se iniciará con el identificador de la ruta seguida por una ':' seguido de las estaciones a lo largo de esa ruta, en orden. Las conexiones se indicarán con un signo '=' seguido por la designación alternativa completa. Todas las conexiones se identifican al menos una vez, y si hay más de dos líneas reunidos en una conexión, algunas o todas las designaciones alternativas se pueden identificar juntas. Es decir, puede haber secuencias como '...hc=Bg=Cc=Abd...". Si la ruta forma un bucle, la última estación serála misma que la primera. Esta es la única situación en la que letras de una estación se pueden repetir. El siguiente fragmento del archivo de entrada consistirá en una secuencia de líneas, cada uno con dos estaciones escritas juntas. El archivo termina con una línea que consiste en una sola "almohadilla" (#).

Salida

La salida consistirá en una serie de líneas de texto, una para cada par de estaciones indicadas en la entrada. Cada línea consistirá en la duración de la ruta más rápida que une las dos estaciones, justificado a la derecha en un campo de anchura 3, seguido de dos puntos, un espacio y la secuencia de las estaciones que representan el viaje más corto. Siga el ejemplo que se muestra a continuación. Tenga en cuenta que siempre habrá un solo camino más rápido para cualquier par dado de estaciones y que la ruta debe comenzar y terminar en las citadas estaciones (no en ninguno de sus sinónimos); por lo tanto, el tiempo de ruta debe incluir la duración de cualquier transbordo de estación. La siguiente entrada de ejemplo se refiere al diagrama mostrado anteriormente:

(Asegúrate de que has leído las preguntas frecuentes antes de plantear tu solución)