Fişierul intrare/ieşire:gather.in, gather.outSursăpreONI 2008 Runda 2
AutorAdrian DiaconuAdăugată deDITzoneCAdrian Diaconu DITzoneC
Timp execuţie pe test0.3 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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.ingather.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content