Revizia anterioară Revizia următoare
| 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), un lanţ reprezintă o succesiune de noduri S={x1, x2, ..., xk}, astfel încât există muchie între oricare două noduri consecutive. Costul unui lanţ este 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ă astfel: (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 lanţuri care îl formează.
Cerinţa
Dându-se un graf neorientat G = (V,E) şi trei noduri A, B, C ⊆ V, determinaţi costul minim al unui trilanţ cu vârfurile in A, B, C, precum şi acest trilanţ.
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.
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ă un trilanţ. Cele trei lanţuri pot fi afişate oricum. În caz că există mai multe trilanţuri de cost minim se va afişa oricare dintre ele.
Restricţii
- 1 ≤ A, B ≤ N ≤ 100 000
- 1 ≤ M ≤ 100 000
- 1 ≤ C ≤ 50 000
- Pentru 30% 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
| trilant.in | trilant.out |
|---|---|
| 4 3 1 4 1 2 4 1 3 4 1 | 3 2 1 4 2 2 4 2 3 4 |
