Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | ktree.in, ktree.out | Sursă | All You Can Code 2008 |
| Autor | Andrei Grigorean | Adăugată de |  Andrei Grigorean •wefgef |
| Timp execuţie pe test | 0.025 sec | Limită de memorie | 80000 kbytes |
| Scorul tău | N/A | Dificultate |   4/5 |
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 M 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 K 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
- Costurile drumurilor vor fi mai mici decat 1000
Exemple
| ktree.in | ktree.out |
|---|---|
| 2 1 1 1 2 3 | 3 |
| 10 4 3 1 2 10 1 3 21 1 4 4 2 7 2 3 5 5 3 6 12 6 8 7 6 9 6 6 10 3 | 23 |
Explicatie
In primul exemplu Miruna va detona singurul drum, care are costul 3. In al doilea exemplu, va distruge drumurile dintre urmatoarele perechi de orase: (2, 7), (3, 5), (3, 6), (1, 4).
