Fişierul intrare/ieşire:patrol.in, patrol.outSursăSummer Challenge 1
AutorFilip Cristian BuruianaAdăugată de
Timp execuţie pe test0.25 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

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

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

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content