Fişierul intrare/ieşire:camion2.in, camion2.outSursăLot 2006 Alba
AutorMugurel Ionut AndreicaAdăugată detoni2007Pripoae Teodor Anton toni2007
Timp execuţie pe test0.15 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Camion2

In judetul Alba sunt n localitati numerotate de la 1 la n. Intre aceste localitati exista o retea de drumuri cu dublu sens (bidirectionale) conceputa astfel incat intre oricare doua localitati exista un singur drum care, fie e direct, fie trece prin alte localitati. Exista n-1 perechi de localitati cu proprietatea ca intre localitatile ce formeaza o pereche exista un drum direct. Lungimea acestor drumuri directe este cunoscuta.

Firma TOL produce bunuri de larg consum; are o fabrica in resedinta judetului care este localitatea numerotata 1 si n-1 magazine, cate unul in fiecare dintre celelalte n-1 localitati din judet. Pentru a transporta produsele de la fabrica la cele n-1 magazine, TOL are la dispozitie p camioane. Deoarece produsele fabricii nu sunt voluminoase si nici nu cantaresc prea mult, capacitatea camioanelor este practic nelimitata, astfel incat orice camion ar putea aproviziona intr-o singura cursa toate magazinele din judet. O cursa a unui camion incepe obligatoriu la fabrica (adica in localitatea 1), poate trece de mai multe ori printr-o localitate si se poate termina in oricare localitate a judetului; nu este obligatoriu ca din cursa camionul sa revina la localitatea 1.

Costul unei astfel de curse este direct proportional cu distanta parcursa. Camioanele fiind cam vechi, ele nu pot efectua decat o singura cursa (indiferent de lungimea acesteia).

Programatorul firmei TOL primeste ca sarcina de serviciu elaborarea unei planificari care sa stabileasca traseele a cel mult p curse prin care sa fie aprovizionate toate localitatile judetului, iar suma distantelor parcurse de camioane in aceste curse sa fie minima. El nu se prea descurca cu programarea, dar e bine informat si stie ca lotul national de informatica se afla la Alba Iulia. Asa ca apeleaza la voi pentru a-i rezolva problema.

Cerinta

Scrieti un program care determina o planificare a traseelor pentru cel mult p curse astfel incat prin aceste curse sa fie aprovizionate toate cele n-1 magazine, iar suma distantelor parcurse de camioanele plecate in aceste curse sa fie minima.

Date de intrare

Fisierul de intrare camion2.in contine:

  • pe prima linie doua valori numerice naturale pozitive n si p cu semnificatia din enunt;
  • pe fiecare dintre urmatoarele n-1 linii, 3 valori numerice naturale pozitive v1, v2, d (v1 ≠ v2) separate printr-un spatiu, cu semnificatia: intre localitatile v1 si v2 este un drum direct de lungime d.

Date de iesire

Fisierul de iesire camion2.out va contine o singura linie care va contine suma distantelor parcurse de camioane.

Restrictii

  • n1000 ; pentru 15% din teste n20
  • p25
  • Nu exista doua localitati intre care sa existe doua drumuri directe.
  • Lungimea unui drum direct nu depaseste 100 si este un numar nenul.

Exemplu

camion2.incamion2.out
5 1
1 2 10
3 1 7
4 3 1
3 5 2
30
5 3
1 2 10
3 1 7
4 3 1
3 5 2
21

Explicatie

  1. Se foloseste un singur camion. Cursa are urmatorul traseu: 1-3-4-3-5-3-1-2.
    Suma distantelor este: 7+1+1+2+2+7+10=30
  2. Se folosesc doua camioane. Cele doua curse sunt: 1-3-4-3-5 si 1-2.
    Suma distantelor este: 7+1+1+2+10=21
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content