

		LINII DE METROU
	       -----------------	

	Intre oricare doua statii ale celor n linii de metrou dintr-un oras exista o legatura bi-
directionala, fie directa, fie prin schimbari de linii. Sa se realizeze un program de informare
generala a publicului calator asupra modalitatii de transport intre doua statii specificate prin
nume, indicandu-se pentru fiecare portiune de drum statiile prin care se poate ajunge de la statia
de pornire la cea de sosire.
	Se va alege traseul cu numar minim de schimbari de linii. In cazul in care exista trasee
cu acelasi numar de schimbari de linii, se va alege cel cu mai putine statii.

	Datele de intrare se citesc din fisierul "RUT.TXT" cu urmatoarea structura:

	- numarul de linii de metrou pe prima linie a fisierului
	- pt.fiecare linie de metrou: numarul de statii de pe linie, urmate de numele statiilor
(un caracter), separate prin spatiu
	- linii continand perechi de statii intre care se cer trasee.

EXEMPLU:
	Mai jos apar o structura si fisierul de intrare corespunzator

3
3			C--\		    -----H	
A B C			    --		   /
3			      \-B-------E--	
D B E			       / \     /
4			    /--	  \   /
G A E H			   D	   \ /
H C				    A---------G
G B

SOLUTIE:
--------

	Ideea de rezolvare consta in gasirea unui drum minim in graful atasat retelei, construit
in felul urmator: pt. fiecare statie consideram un numar de noduri egal cu nr. de linii de metrou
care trec prin statia respectiva si un nod suplimentar. Intre oricare 2 noduri exista o muchie
care are costul mai mare decat nr. maxim de statii de pe oricare linie (in program am ales valoa-
rea 200). Am adugat fiecarei linii cate o muchie de cost 1 corespunzatoare statiilor vecine de pe
acea linie, muchie care uneste nodurile atasate liniei respective.
	Pt. a gasi drumul minim intre 2 statii date, vom genera drumul minim intre nodurile adau-
gate suplimentar atasate nodurilor de pe drumul optim.

iar solutiile sunt:
H E A B C
G A B