Revizia anterioară Revizia următoare
| 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 naţional de informatica se afla la Alba Iulia. Asa ca apeleaza la voi pentru a-i rezolva problema.
Date de intrare
Fisierul de intrare camion2.in ...
Date de iesire
In fisierul de iesire camion2.out ...
Restrictii
- ... ≤ ... ≤ ...
Exemplu
| camion2.in | camion2.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicatie
...
