gather

Gather

== include(page="template/taskheader" task_id="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 Gigel doreste 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.

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.

h2. Cerinta

h2. 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.

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*}).

h2. Date de iesire

* $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

h2. Exemplu

2 4 25 1
3 4 100 2
3 1 10 2

| 400

| 100

|
h3. 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 $3$ parcurgand impreuna distanta {$2*75$}.
Gigel merge apoi impreuna cu detinutul $2$ in celula $4$ parcurgand impreuna distanta {$2*100$}. Aici este informat si detinutul $2$ de plan.

Gigel merge apoi impreuna cu detinutul $2$ in celula $4$ parcurgand impreuna distanta {$2*25$}. Aici este informat si detinutul $1$ de plan.

== include(page="template/taskfooter" task_id="gather") ==

2494