h1(#trilant). 'Trilant':problema/trilant

Pentru doua noduri $P,Q$ din graf, vom defini $d(P,Q)$ ca fiind drumul de cost minim de la $P$ la $Q$. Pe noi ne intereseaza sa gasim un nod $X$ astfel incat suma $d(A,X)+d(B,X)+d(C,X)$ sa fie minima. Pentru a realiza acest lucru trebuie sa calculam pentru orice nod $K$ din graf $d(A,K),d(B,K) si d(C,K)$. Putem face acest lucru folsind 'Algoritmul lui Dijsktra':/problema/dijkstra. Nodul solutie va fi acel nod $X$ cu proprietatea ca suma $d(A,X)+d(B,X)+d(C,X)$ sa fie minima.

Vom noda distanta minima dintre doua noduri $P$ si $Q$ prin $d(P,Q)$. Trebuie sa gasim nodul $X$ din graf astfel incat suma $d(X,A)+d(X,B)+d(X,C)$ sa fie minima. Pentru aceasta calculam distanta minima pentru fiecare nod fata de $A$, $B$ si $C$, folosind 'Algoritmul lui Dijkstra':/problema/dijkstra. Nodul $X$ cautat este chiar nodul cu $d(X,A)+d(X,B)+d(X,C)$ minima.

Presupunem ca am ales nodul $X$ cu proprietatea de mai sus. Daca drumurile $(X,A)$ si $(X,B)$ nu ar fi disjuncte, atunci stim sigur ca exista un nod $K$ pe lantul de la $X$ la $A$, astfel incat drumurile $(K,A)$ si $(K,B)$ sunt disjuncte. Inseamna ca pe drumul de la $K$ la $X$, vom numara muchiile care apar de doua ori, rezulta ca $X$ nu ar avea proprietatea ca suma $d(A,X)+d(B,X)+d(C,X)$ sa fie minima. Analog daca $(X,A)$ si $(X,C)$ sau $(X,B)$ si $(X,C)$ nu ar fi disjuncte.
 
Complexitatea solutiei este O(MlogN).
 

De ce merge:
Pre