== include(page="template/taskheader" task_id="trilant") ==
Într-un graf neorientat $G(V,E)$, un lanţ reprezintă un set de noduri $S={x{~1~},x{~2~}...x{~k~}}$, astfel încât există muchie între oricare două noduri consecutive din lanţ. Costul unui lanţ este suma costurilor muchiilor alese pentru a uni x{~1~} cu x{~2~}, x{~2~} cu x{~3~} ... x{~k-1~} cu x{~k~}. Vom nota un lanţ $(x{~1~},x{~2~}...x{~k~})$ prin primul si ultimul său nod $(x1,xk)$.
Definim un trilanţ într-un graf neorientat $G(V,E)$ ca fiind reuniunea a trei lanţuri $(A,X),(B,X),(C,X); A,B,C,X ⊆ V$, $X$ fiind singurul nod comun celor trei. Costul unui trilanţ este suma costurilor celor trei lanturi care il formează.
Într-un graf neorientat $G=(V,E)$ cu costuri pe muchii, definim un lanţ ca fiind o succesiune de noduri $S={x{~1~},x{~2~}...x{~k~}}$, cu condiţia să existe muchie între oricare două noduri consecutive, si toate nodurile să fie diferite. Costul unui lanţ este reprezentat de suma costurilor muchiilor alese pentru a uni $x{~1~}$ cu $x{~2~}, x{~2~} cu x{~3~} ... x{~k-1~}$ cu $x{~k~}$. Vom nota un lanţ $(x{~1~},x{~2~}...x{~k~})$ prin primul si ultimul său nod, adică : $(x{~1~},x{~k~})$. Definim un trilanţ ca fiind reuniunea a trei lanţuri $(A,X),(B,X),(C,X); A,B,C,X ⊆ V$, $X$ fiind singurul nod comun celor trei. Costul unui trilanţ este egal cu suma costurilor celor trei lanţuri care îl formează. Vom nota un trilanţ prin $(A,B,C)$.
h2. Cerinţa
Dându-se un graf neorientat $G(V,E)$, si trei noduri $A,B,C ⊆ V$ determinaţi numărul de trilanţuri de cost minim cu varfurile in $A,B,C$.
Dându-se un graf neorientat $G=(V,E)$ şi trei noduri $A,B,C ⊆ V$, determinaţi costul minim al trilanţului $(A,B,C)$.
h2. Date de intrare
Pe prima linie a fişierului $trilant.in$ se află două numere naturale $N, M$ separate printr-un spaţiu, reprezentând numărul de noduri, respectiv numărul de muchii din graf. Pe a doua linie a fişierului de intrare se vor afla numerele naturale $A,B,C$ cu semnificaţia din enunţ.
Următoarele $M$ linii vor conţine câte trei numere $P,Q,X$ descriind faptul ca există muchie de la nodul $P$ la nodul $Q$ cu costul $X$.
Pe prima linie a fişierului $trilant.in$ se află două numere $N,M$ separate printr-un spaţiu, reprezentând numărul de noduri, respectiv numărul de muchii din graf. Pe a doua linie a fişierului de intrare se vor afla numerele $A,B,C$ cu semnificaţia din enunţ. Următoarele $M$ linii vor conţine câte trei numere naturale $P,Q,T$ descriind faptul ca există muchie de la nodul $P$ la nodul $Q$ cu costul $T$.
h2. Date de ieşire
Fişierul $trilant.out$ va conţine o singură linie pe care se vor găsi numărul de trilanţuri de cost minim si costul minim găsit.
Fişierul $trilant.out$ va conţine pe prima linie costul minim găsit. Fiecare din următoarele trei linii va avea urmatorul format: $K$, urmat de $K$ numere $x{~1~},x{~2~}...x{~k~}$, reprezentand unul din cele trei lanţuri ce formeză trilanţul cerut. Cele trei lanţuri vor fi afisate cu nodurile in ordine de la $X$ la $A$, de la $X$ la $B$ si de la $X$ la $C$. În cazul în care există mai multe soluţii, se poate afişa oricare.
h2. Restricţii
* $1 ≤ A,B ≤ N ≤ 1 000$
* $1 ≤ M ≤ 100 000$
* $-50 000 ≤ C ≤ 50 000$
* Nu vor exista cicluri de cost negativ de lungime $≥ 3$
* $1 ≤ A, B, C ≤ N ≤ 100 000$
* $1 ≤ M ≤ 250 000$
* $1 ≤ costul unei muchii ≤ 4 000 000$
* Pentru $50%$ din teste $N ≤ 1 000$
* Lanţurile care formează un trilanţ pot avea lungimi diferite
* Oricare trei lanţuri $(A,X),(B,X),(C,X)$ care formează un trilanţ vor fi disjuncte două cate două, mai puţin nodul $X$ (singurul nod comun pe care îl vor avea va fi $X$)
* Oricare trei lanţuri $(A,X),(B,X),(C,X)$ care formează un trilanţ vor avea lungime $≥ 2 (A ≠ X, B ≠ X, C ≠ X)$
* Intotdeauna va exista solutie
h2. Exemplu
table(example). |_. trilant.in |_. trilant.out |
| 4 3
1 2 3
1 4 1
2 4 1
3 4 1
| 1 3
| 3
2 4 1
2 4 2
2 4 3
|
== include(page="template/taskfooter" task_id="trilant") ==
