| Fişierul intrare/ieşire: | camion2.in, camion2.out | Sursă | Lot 2006 Alba |
| Autor | Mugurel Ionut Andreica | Adăugată de |  Pripoae Teodor Anton •toni2007 |
| Timp execuţie pe test | 0.075 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/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
- n ≤ 1000 ; pentru 15% din teste n ≤ 20
- p ≤ 25
- 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.in | camion2.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
- 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 - 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
