==Include(page="template/taskheader" task_id="patrol")==
==Include(page="template/raw")==
patrol
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. Date de Intrare
Fisierul de intrare patrol.in are urmatoarea structura:
N M P ]numarul de orase, numarul de legaturi si numarul de politisti
C[1] C[2] ... C[n cele N costuri de sedere, pentru fiecare oras in parte
]A[1] B[1
]A[2] B[2 linia A[i] B[i] semnifica faptul ca exista o legatura directa
]....... intre orasele A[i] si B[i
A[M] B[M ]
]L[1] T[1,1]... T[1,L[1]
]L[2] T[2,1]... T[2,L[2] primul numar de pe linie indica lungimea traseului de
]....... patrulare, dupa care urmeaza descrierea traseului propriu-zis
L[P] T[P,1]... T[P,L[P]
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
o 3 < N <= 1 024
o 4 < M <= 16 000
o P <= 512
o 2 <= L[i] < 8
o Costurile de sedere sunt numere naturale din [1, 1 600]
o In orice moment infractorul trebuie sa se deplaseze ( nu poate sta pe loc )
o La costul total se vor calcula si taxele percepute in orasul de plecare si cel de sosire
o Este posibil ca intr-un oras, in acelasi timp, sa fie mai mult de un politist
h2. Exemplu
|patrol.in |patrol.out |
|7 6 1 |34 |
| | |
|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 | |
==Include(page="template/taskheader" task_id="patrol")==
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. 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 |
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 ≤ 1 024$
* $4 < M ≤ 16 000$
* $P ≤ 512$
* $2 ≤ 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
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")==
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")==
