Fişierul intrare/ieşire:trilant.in, trilant.outSursă.com 2009, Runda 1
AutorSerban Andrei StanAdăugată desavimSerban Andrei Stan savim
Timp execuţie pe test1.1 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/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={x1,x2...xk}, 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 x1 cu x2, x2 cu x3 ... xk-1 cu xk. Vom nota un lanţ (x1,x2...xk) prin primul si ultimul său nod, adică : (x1,xk). 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,T descriind faptul ca există muchie de la nodul P la nodul Q cu costul T.

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 x1,x2...xk, 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.

Restricţii

  • 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)
  • Intotdeauna va exista solutie

Exemplu

trilant.intrilant.out
4 3
1 2 3
1 4 1
2 4 1
3 4 1
3
2 4 1
2 4 2
2 4 3
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content