Fişierul intrare/ieşire:lianyu.in, lianyu.outSursăConcursul National de Informatica "Adolescent Grigore Moisil" 16
AutorChichirim George, Patrick SavaAdăugată deAGMinformaticaAGMInformatica AGMinformatica
Timp execuţie pe test0.2 secLimită de memorie131072 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Lian Yu

Pe insula Lian Yu sunt N asezari, numerotate de la 1 la N, conectate prin M drumuri bidirectionale. Pe aceasta insula renumitul Slade Wilson creste cel mai periculos drog si de asemena cea mai periculoasa arma, Mirakuru. A.R.G.U.S a aflat de aceasta operatiune si vrea sa trimita K echipaje de soldati sa investigheze si sa obtina informatii esentiale. Totusi acest lucru nu este chiar atat de simplu si prin urmare A.R.G.U.S v-a angajat pe voi trei sa le spuneti costul minim pentru a trimite K echpaje de soldati pe insula tinand cont de urmatoarele conditii:

  • datorita structurii insulei, in fiecare asezare i poate fi lasat, de catre avioane, maxim un echipaj de soldati cu costul costi.
  • dupa aterizarea echipajelor acestea vor trebui sa se intalneasca intr-o asezare ca sa continue planul. Datorita interventiei bruste a echipajului si a suportului aerian, soldatii vor putea elimina toti mercenarii lui Slade Wilson care se vor afla in asezarile unde vor ateriza acestia. De indata ce soldatii vor ateriza, se va da alarma in toata insula si toti mercenarii vor lua cat mai mult Mirakuru si se vor aduna intr-una din asezari ca sa-l protejeze (si cel mai probabil daca soldatii vor trece prin aceasta asezare vor fi omorati, cea ce este total exclus).

Asadar echipajele trebuie lasate in asezari astfel incat in oricare din cele ramase s-ar strange mercenarii lui Slade Wilson, soldatii sa poata sa se intalneasca intr-o asezare fara sa treaca prin cea aleasa de de Slade Wilson si echipa sa.

Date de intrare

Fişierul de intrare lianyu.in contine pe prima linie trei numere naturale N (numarul de asezari), M (numarul de drumuri) si K (numarul de echipaje ce trebuie trimise). Pe urmatoarea linie se afla N numere naturale despartite printr-un spatiu, al i-lea fiind costi. Pe urmatoarele M linii se afla cate doua numere naturale x si y cu semnificatia ca exista un drum bidirectional intre asezarile x si y.

Date de ieşire

În fişierul de ieşire lianyu.out se va afisa un singur numar natural reprezentand costul minim pentru a trimite K echipaje pe insula cu restrictiile de mai sus.

Restricţii

  • 1 ≤ K ≤ N ≤ 3000
  • 1 ≤ M ≤ 5000
  • 1 ≤ costi ≤ 105
  • Se poate ajunge de la oricare asezare la oricare alta mergand pe cele M drumuri
  • Intre oricare doua asezari exista maxim un drum si nu exista drum de la o asezare la ea insasi

Exemplu

lianyu.inlianyu.out
5 5 2
2 4 1 4 1
1 2
2 3
3 4
1 4
4 5
3

Explicaţie

Se trimit echipaje in asezarile 1 si 3.
Un cost mai bun se poate obtine daca am trimite echipaje in asezarile 3 si 5, dar daca mercenarii se vor strange in asezarea 4 atunci echipajul din asezarea 5 nu se va mai putea intalni cu cel din asezarea 3.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?