Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2007-10-25 07:24:15.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:ktree.in, ktree.outSursăAll You Can Code 2008
AutorAndrei GrigoreanAdăugată dewefgefAndrei Grigorean wefgef
Timp execuţie pe test0.05 secLimită de memorie80000 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Ktree

Miruna a ajuns in Tara Minunilor. Acest taram fermecat este alcatuit din N orase legate intre ele prin N-1 drumuri astfel incat din orice oras se poate ajunge in oricare altul folosind reteaua de drumuri existenta. Deoarece s-a saturat sa fie tratata ca o printesa cuminte, Miruna vrea sa detoneze exact K drumuri. Unele drumuri sunt construite mai bine decat altele, de aceea Miruna are nevoie de mai mult explozibil pentru a-si atinge obiectivul malefic. Pentru fiecare drum se cunoaste pretul care trebuie platit pentru a achizitiona explozibilul necesar detonarii lui. Dupa ce drumurile alese vor fi distruse, Miruna doreste totusi sa poate circurla pornind din orasul 1 in exact M orase folosind ceea ce a ramas din reteaua stradala pentru a putea jefui negustorii veniti de peste mari si tari.
Ajutati-o pe fetita ajunsa in Tara Minunilor sa cheltuie cat mai putin!

Date de intrare

Pe prima linie a fisierului de intrare ktree.in se vor afla 3 numere intregi N, M, si K avand semnificatia din enunt. Pe urmatoarele N-1 linii se vor afla cate 3 numere A, B, C, semnificand faptul ca intre orasul A si orasul B exista un drum bidirectional pentru care costul detonarii este C.

Date de iesire

Fisierul ktree.out va contine un singur numar intreg reprezentand costul minim cerut.

Restrictii

  • 1 < N < 200
  • 1 ≤ M < N
  • 1 ≤ K < N
  • M + K ≤ N

Exemplu

ktree.inktree.out
2 1 1
1 2 3
3 ( wow ce exemplu tare )

Explicatie
like duuh e singura muchie :))

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?