Fişierul intrare/ieşire: | patrol.in, patrol.out | Sursă | Summer Challenge 1 |
Autor | Filip Cristian Buruiana | Adăugată de | |
Timp execuţie pe test | 0.25 sec | Limită de memorie | 65536 kbytes |
Scorul tău | N/A | Dificultate |
Vezi solutiile trimise | Statistici
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.
Cerinta
Sa se determine costul total minim de sedere in orase astfel incat sa se indeplineasca conditiile precizate.
Date de intrare
Fisierul de intrare patrol.in are urmatoarea structura:
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 olegatura 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.
Date de iesire
Prima linie a fisierului de iesire patrol.out contine costul minim platit. Se garanteaza ca intotdeauna exista solutie.
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
Exemplu
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 |
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.