| 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={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.in | trilant.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 |
