patrol

Patrol

== include(page="template/taskheader" task_id="patrol") ==

==Include(page="template/taskheader" task_id="patrol")==

Poveste ...

O tara are $N$ orase si $M$ legaturi directe, bidirectionale, intre aceste orase. Fiecare oras percepe o taxa de sedere cunoscuta. Un infractor porneste din orasul numerotat cu $1$ si doreste sa ajunga in orasul numerotat cu $N$, folosind legaturile existente. Cum lucrurile nu sunt niciodata asa de simple, exista si $P$ politisti care il cauta. Un politist are un traseu de patrulare bine definit. Traseul sau este de fapt un drum simplu ( in care toate orasele sunt distincte ). El va parcurge un drum du-te vino, adica pleaca pe drumul stabilit, dupa care se intoarce pe acelasi drum, etc. De exemplu, daca traseul de patrulare al unui politist este $4 7 5$, el va merge intotdeuna pe $4 7 5 7 4 7 5 7 4...$. Parcurgerea unei legaturi intre oricare doua orase legate direct se realizeaza intr-o unitate de timp, pentru infractor si pentru oricare dintre politisti. Stationarea intr-un oras nu necesita timp suplimentar.
Infractorul porneste din orasul numerotat cu $1$ si doreste sa ajunga in orasul numerotat cu $N$, platind o taxa de sedere minima prin orasele prin care trece, evitand intalnirea cu vreun politist. O intalnire se poate realiza atunci cand infractorul si unul din politisti se afla in acelasi timp in acelasi oras, sau in acelasi timp pe o legatura intre orase. Plecarea din orasul $1$ se realizeaza la momentul $1$, cand toti politistii isi incep patrularea.

h2. Cerinta

...

Sa se determine costul total minim de sedere in orase astfel incat sa se indeplineasca conditiile precizate.

h2. Restrictii

h2. Date de intrare

...

Fisierul de intrare $patrol.in$ are urmatoarea structura:
 
table(example). | $N M P$
${@C[1] C[2]...C[n]@}$
${@A[1] B[1]@}$
${@A[2] B[2]@}$
$.......$
${@A[M] B[M]@}$
${@L[1] T[1,1]...T[1,L[1]]@}$
${@L[2] T[2,1]...T[2,L[2]]@}$
$.......$
${@L[P] T[P,1]...T[P,L[P]]@}$
| numarul de orase, de legaturi si de politisti
costurile de sedere, pentru fiecare oras in parte
 
linia ${@A[i] B[i]@}$ semnifica faptul ca exista o
legatura directa intre orasele ${@A[i]@}$ si ${@B[i]@}$
 
primul numar de pe linie indica lungimea
traseului de patrulare, dupa care urmeaza
descrierea traseului propriu-zis |

h2. Date de intrare
...

In total, fisierul de intrare contine M+P+2 linii.

h2. Date de iesire

...

Prima linie a fisierului de iesire $patrol.out$ contine costul minim platit. Se garanteaza ca intotdeauna exista solutie.
 
h2. Restrictii si precizari
 
* $3 < N &le; 1 024$
* $4 < M &le; 16 000$
* $P &le; 512$
* $2 &le; L[i] < 8$
* Costurile de sedere sunt numere naturale din $[1, 1 600]$
* In orice moment infractorul trebuie sa se deplaseze ( nu poate sta pe loc )
* La costul total se vor calcula si taxele percepute in orasul de plecare si cel de sosire
* Este posibil ca intr-un oras, in acelasi timp, sa fie mai mult de un politist

h2. Exemplu

| patrol.in | patrol.out |
| linia1
linia2
linia3
| linia1
linia2
|
== include(page="template/taskfooter" task_id="patrol") ==

table(example). |_. patrol.in |_. patrol.out |
| 7 6 1
10 4 9 1 2 5 2
1 2
2 3
2 4
2 6
4 5
6 7
5 7 6 2 4 5
| 34 |
 
h3. Explicatie
 
Drumul infractorului este 1 2 3 2 6 7. Se observa ca, de exemplu, la timpul 2, infractorul nu poate pleca spre orasul cu numarul 6 pentru ca s-ar intalni pe legatura dintre orasele 2 si 6 cu politistul. In plus, daca ar pleca spre orasul cu numarul 4, el ar fi prins in final de catre politist.
 
==Include(page="template/taskfooter" task_id="patrol")==
 
 

1155