Fişierul intrare/ieşire:	team.in, team.out	Sursă	lot 2006
Autor	Rodica Pintea	Adăugată de	Airinei Adrian •astronomy
Timp execuţie pe test	0.1 sec	Limită de memorie	20096 kbytes
Scorul tău	N/A	Dificultate	4/5

Vezi solutiile trimise | Statistici

Team

Sambata o petrec cu prietenii la discoteca "Why not" din centrul orasului. De acolo plecam in zori p persoane, in gasca, si trebuie sa ajungem fiecare acasa. Atat la discoteca, la punctele de destinatie ale membrilor gastii, precum si in alte puncte ale orasului se afla statii de Team-Taxi pe care le putem folosi in drumul spre casa, platind frateste pe fiecare segment de drum o suma fixa pe care o pretinde soferul masinii (in functie de lungimea drumului si nu in functie de numarul de pasageri). In orice statie pot parasi gasca numai cei care au ajuns la destinatie, in acest caz grupurile omogene formate urmand sa se desparta (pentru ca au disparut oamenii de legatura) si sa ia in continuare taxiuri cu diferite destinatii. Doua grupuri omogene diferite pot merge in aceeasi destinatie, dar utilizand taxiuri diferite. Numim grup omogen o formatie de persoane cu numere de ordine consecutive. De exemplu, pentru p=6, de la discoteca porneste gasca in formatia 1 2 3 4 5 6. Daca la o statie se opreste persoana numarul 3, atunci se formeaza doua grupuri omogene 1 2 si 4 5 6. Ei se despart luand doua taxiuri diferite. Doua grupe formate din 1 4 5 si 2 6 nu sunt omogene. Atata timp cat k persoane merg cu un taxi pe un segment pe care orice sofer cere invariabil suma c, contributia fiecaruia pe acel segment este c/k. Daca o persoana merge singura cu un taxi pe segmentul respectiv, ea va trebui sa plateasca singura intreaga suma.

Cerinta

Stiind numarul de persoane, reteaua de statii de taxiuri, costurile de transport pe fiecare segment al retelei si punctele de destinatie ale fiecarui membru al gastii, se cere sa se determine costul minim pe care il pot plati in total membrii gastii astfel incat, utilizand taxiurile in maniera descrisa, fiecare sa ajunga acasa.

Date de intrare

Din fisierul team.in se citesc:

• p numarul de persoane din gasca ce pleaca de la discoteca, de pe linia 1
• n numarul de statii de taxi din oras, de pe linia 2; statiile sunt numerotate de la 1 la n
• m numarul de segmente ce leaga direct cate doua statii, de pe linia 3
• m triplete de forma i j c ( i si j sunt statiile intre care se considera segmentul, iar c costul de transport pe segmentul respectiv), de pe urmatoarele m linii
• d₁ d₂ ... d_p statiile de destinatie ale membrilor gastii (nu neaparat distincte), de pe ultima linie.

Date de iesire

Fisierul team.out va contine o singura linie cu un numar reprezentand costul minim determinat.

Restrictii

• 1 ≤ p ≤ 50
• 2 ≤ n ≤ 500
• 1 ≤ i, j ≤ n
• 0 ≤ c ≤ 1000
• 1 ≤ d₁, d₂ ... d_p ≤ n
• se considera statia 1 ca punct de plecare (discoteca)
• pe toate strazile se poate circula in ambele sensuri
• pentru datele de test exista intotdeauna solutie
• toate datele de intrare sunt numere naturale

Exemplu

Cum se trimit solutii?