| Fişierul intrare/ieşire: | gather.in, gather.out | Sursă | preONI 2008 Runda 2 |
| Autor | Adrian Diaconu | Adăugată de |  Adrian Diaconu •DITzoneC |
| Timp execuţie pe test | 0.15 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Gather
Bunul nostru prieten Gigel a ajuns la inchisoare. Inchisoarea are N celule legate intre ele prin M coridoare ce pot fi parcurse in ambele sensuri. In inchisoare se afla in total K detinuti. Foarte inteligent si practic Gigel are deja un plan de evadare, dar pentru asta are nevoie de toti detinutii. Initial Gigel se afla in celula 1, iar modul in care ii poate aduna pe detinuti este urmatorul: el se plimba prin coridoarele inchisorii si cand intalneste un nou detinut ii spune planul si in continuare acesta va trebui sa il urmeze(Gigel vrea sa se asigure ca nici un detinut nu il va trada, de aceea nu scapa din ochi nici un detinut care stie de planul sau). Problema este ca daca pe anumite coridoare sunt vazuti mai multi detinuti mergand impreuna, paznicii inchisorii vor intra la banuieli, iar planul lui Gigel va esua. Deoarece vrea ca toti sa fie cat mai odihniti pentru a maximiza sansele de reusita ale planului Gigel trebuie sa minimizeze suma totala parcursa de toti detinutii si de el. Detinutii stau pe loc pana in momentul in care Gigel vine la ei, apoi il vor urma intotdeauna.
Cerinta
Calculati suma minima a distanelor parcurse de detinuti si de Gigel pentru a-i aduna pe toti intr-o celula.
Date de intrare
Fisierul de intrare gather.in contine pe prima linie trei numere naturale K, N, M. Pe urmatoarele K linii se afla cate un numar reprezentand celulele in care se afla initial detinutii. In continuare vor urma M linii fiecare continand cate patru numere naturale A B C D cu urmatoare semnificatie: intre celulele A si B se afla un coridor de lungime C pe care nu pot merge mai mult de D detinuti(exceptandu-l pe Gigel).
Date de iesire
In fisierul de iesire gather.out se va afla o singura linie care contine distanta minima ceruta.
Restrictii
- 1 ≤ N ≤ 750
- 1 ≤ K ≤ 15
- 1 ≤ M ≤ 1250
- C si D se vor incadra pe 32 de biti pentru fiecare muchie
- Rezultatul se va incadra pe 32 de biti
- Nu vor exista mai multi detinuti in aceeasi celula
- Gigel poate trece prin celule cu prizonieri fara a le spune de planul sau in acest moment, urmand sa ii viziteze din nou mai tarziu
- Va exista mereu solutie
Exemplu
| gather.in | gather.out |
|---|---|
| 2 4 5 4 2 1 2 50 1 2 3 75 2 2 4 25 1 3 4 100 2 3 1 10 2 | 100 |
Explicatie
Gigel merge din celula 1 in celula 2 parcurgand o distanta de 50. Aici ii spune detinutului 2 de planul sau.
Gigel merge apoi impreuna cu detinutul 2 in celula 4 parcurgand impreuna distanta 2*25. Aici este informat si detinutul 1 de plan.
