Fişierul intrare/ieşire:	trilant.in, trilant.out	Sursă	.com 2009, Runda 1
Autor	Serban Andrei Stan	Adăugată de	Serban Andrei Stan •savim
Timp execuţie pe test	0.55 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Trilant

Într-un graf neorientat G=(V,E) cu costuri pe muchii, definim un lanţ ca fiind o succesiune de noduri S={x₁,x₂...x_k}, cu condiţia să existe muchie între oricare două noduri consecutive. Costul unui lanţ este reprezentat de suma costurilor muchiilor alese pentru a uni x₁ cu x₂, x₂ cu x₃ ... x_k-1 cu x_k. Vom nota un lanţ (x₁,x₂...x_k) prin primul si ultimul său nod, adică : (x₁,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).

Cerinţa

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).

Date de intrare

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,X descriind faptul ca există muchie de la nodul P la nodul Q cu costul X.

Date de ieşire

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₁,x₂...x_k, reprezentand unul din cele trei lanţuri ce formeză trilanţul cerut. Cele trei lanţuri pot fi afişate îm orice ordine. În cazul în care există mai multe soluţii, se poate afişa oricare.

Restricţii

• 1 ≤ A, B ≤ N ≤ 100 000
• 1 ≤ M ≤ 100 000
• 0 ≤ C ≤ 50 000
• Pentru 50% din teste N ≤ 1 000
• Gradul maxim al unui nod din graf este 10
• 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)

Exemplu

Cum se trimit solutii?