| Fişierul intrare/ieşire: | subarbore.in, subarbore.out | Sursă | Algoritmiada 2012, Runda 2 |
| Autor | Cosmin Silvestru Negruseri | Adăugată de |  Cezar Mocan •CezarMocan |
| Timp execuţie pe test | 0.9 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Subarbore
Se da un graf conex neorientat cu costuri, care are N noduri si M muchii. Se mai dau T noduri speciale. Sa se gaseasca un subarbore de cost minim, inclus in graful dat, care contine cele T noduri speciale.
Date de intrare
Pe prima linie a fişierului de intrare subarbore.in se gasesc N, numarul de noduri si M, numarul de muchii. Urmatoarele M linii vor contine cate 3 numere, a, b si c cu semnificatia ca exista o muchie intre nodurile a si b si ca aceasta are costul c. A M+2-a linie va contine numarul de noduri speciale, T. Pe ultima linie a fisierului se vor afla cele T noduri speciale.
Date de ieşire
În fişierul de ieşire subarbore.out se va afisa un singur numar, reprezentand costul subarborelui cu proprietatea din enunt.
Restricţii si precizari
- 1 ≤ N ≤ 40
- 1 ≤ M ≤ N * (N - 1) / 2
- 1 ≤ T ≤ 7
- Costurile muchiilor vor fi numere naturale cuprinse intre 1 si 1.000.000
- Pentru 30% din teste, N ≤ 20
Exemplu
| subarbore.in | subarbore.out |
|---|---|
| 5 5 2 1 1 3 1 2 5 2 10 4 3 6 4 5 6 3 4 2 5 | 15 |
Trebuie sa te autentifici pentru a trimite solutii. Click aici
remote content
