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 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 sau -1 in caz ca nu exista solutie.

Restrictii si precizari

  • 1 < N < 75
  • 1 ≤ M < N
  • 1 ≤ K < N
  • Costurile drumurilor vor fi mai mici decat 1000.

Exemple

ktree.inktree.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).

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?