Fişierul intrare/ieşire:subarbore.in, subarbore.outSursăAlgoritmiada 2012, Runda 2
AutorCosmin Silvestru NegruseriAdăugată deCezarMocanCezar Mocan CezarMocan
Timp execuţie pe test1.8 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/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.insubarbore.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

Cum se trimit solutii?

remote content