Fase final

Exercici 2

En una comarca hi ha un conjunt de n estacions de ferrocarril que anomenarem per simplificar: 1,2,....,n. Entre aquestes estacions hi ha trams de via que connecten estacions contigües. Els trams de via es poden fer servir en tots dos sentits.

Posarem un exemple:

Imaginem que hi ha 12 estacions: 1,2,3,4,5,6,7,8,9,10,11 i 12 que estan comunicades pels següents trams:

Podem fer un esquema d’aquesta infrastructura ferroviària:

Escriviu un programa que, llegit el nombre d’estacions i els trams que les uneixen, ens permeti determinar el trajecte més curt (en nombre d’estacions) que hi ha entre dos estacions determinades. Per exemple, amb la infrastructura anterior, per anar de l’estació 2 a l’estació 12 podem fer el trajecte: 2 3 10 11 12 ó 2 3 9 12. El primer trajecte té quatre trams mentre que el segon només en té tres. El programa trobaria aquest segon trajecte.

El fitxer d’entrada s’anomenarà tren.in i serà un fitxer de text amb les següents dades:

1. el nombre d’estacions de la comarca: n. (Màxim 50 estacions)
2. el nombre de trams que uneixen les estacions. (Màxim 1225 trams)
3. els trams connectats. Apareixerà cada tram en una línia diferent. Cada tram consta de dues estacions separades per un espai. No s’assegura cap ordre en l’entrada de trams, és a dir, el fitxer d’entrada pot tenir ‘1 2’ ó ‘2 1’ indistintament pel tram que uneix aquestes dos estacions, no obstant, s’assegura que no hi haurà redundància, és a dir, no apareixerà repetit cap tram.
4. l’estació origen i l’estació de destí. Aquestes apareixeran en la mateixa línia i separats també per un espai.

El fitxer de sortida s’anomenarà tren.out i contindrà el trajecte més curt o, en cas que hi hagi més d’un de la mateixa mida, un qualsevol d’aquests trajectes. Les estacions del trajecte apareixeran totes en la mateixa línia i separades per un espai. Començarà per l’estació origen i acabarà per l’estació de destí. Si no és possible la comunicació entre dos estacions, el fitxer de sortida contindrà només un 0.

Exemple: