

	BARIERE - REZOLVARE
       ---------------------

	Se observa usor ca nu e necesar sa se treaca de 2 ori printr-un acelasi nod, pt. o even-
tuala rearanjare a barierelor. Prin urmare, drumul minim va avea nodurile distincte. Din graful
dat obtinem un digraf, memorat cu ajutorul matricei costurilor drumurilor C, in felul urmator:
	Daca (v,w) este muchie in graful initial atunci:
- daca in w avem bariera indreptata catre v, atunci nu se pune arc de la v la w, deci C[v,w]=infi-
nit. deoarece mai intai trebuie sa ajungem intr-un nod si abia apoi putem muta bariera corespun-
zatoare acelui nod;
- daca in w nu avem bariera indreptata catre v, atunci sigur se va putea trece de la v la w, deci
se pune arc de la v la w, si apar 2 situatii:
	- bariera din v este indreptata catre w, deci pt. a ajunge in w va trebui mai intai mutata
din cale, deci C[v,w]=1+1=2;
	- bariera din v nu este indreptata catre w, deci in w se ajunge direct, C[v,w]=1.

	Rezulta ca problema determinarii grafului cu bariere se reduce la o problema de drum minim
intr-un digraf, in care costurile arcelor sunt fie 1, fie 2. Rezolvarea problemei foloseste algo-
ritmul lui Dijkstra, bazat pe tehnica Greedy.