Fondo
La Policía ha intentado capturar a un ladrón que comete sus fechorías en las estaciones de Transmilenio. Sin
embargo, en los cuatro intentos que ha llevado a cabo han fracasado. Se le ha dado a usted la misión de
capturar al ladrón en el próximo intento. Se sabe que el ladrón siempre está en una de las estaciones de
Transmilenio y está listo para desplazarse a cualquier otro destino.
El problema
El sistema Transmilenio consta de una serie de troncales. Cada troncal va entre dos estaciones diferentes y
tiene algunas estaciones intermedias distribuidas uniformemente.
Los buses viajan en
... leer más ambas direcciones. El tiempo de viaje de una estación a la siguiente (o anterior) estación
de la Troncal es siempre de 5 minutos. En el sistema existen estaciones en las que se puede hacer
transbordo a otras troncales -- estaciones principales-- , mientras que otras estaciones solo son utilizadas
por una Troncal -- estaciones secundarias-- . Este sería un ejemplo donde hay 3 Troncales, 13 estaciones y de
ellas 5 son principales.
Según investigaciones, el ladrón se encuentra en una estación principal donde puede viajar más rápido a
cualquier otra estación. Se asume que no hay pérdida de tiempo para cambiar de una Troncal a otra en
una estación.
El objetivo es encontrar y capturar al ladrón.
Para probar el algoritmo, se pedirán dos datos de tipo entero, N y S, donde N es el número total de
estaciones y S es el número de Troncales. Las estaciones están numeradas del 1 al N (asuma que N no es
mayor 1000 y S no es mayor que 100). A continuación, tenemos Troncales S , una para cada Troncal. Estas
Troncales consisten en una lista de estaciones, separadas por espacios en blanco, que terminan en 0. Habrá
entre 1 y 100 estaciones principales, inclusive. Siempre hay un camino entre cualquier par de estaciones. El
programa debe decir en cuál estación se encuentra el ladrón. retraer
Plazo de Entrega: 31 Mayo, 2023