Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2010-03-11 22:05:21.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:retea.in, retea.outSursăAlgoritmiada 2010, Runda 4
AutorCosmin GheorgheAdăugată degcosminGheorghe Cosmin gcosmin
Timp execuţie pe test0.3 secLimită de memorie36096 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Retea

Aurora face parte dintr-o retea de bloc cu N calculatoare si M conexiuni bidirectionale. Fiecare conexiune intre doua noduri x, y are un cost asociat care reprezinta timpul necesar informatiei pentru a parcurge conexiunea respectiva. Calculatorul 1 este calculatorul Aurorei si calculatorul N este serverul. Aurora s-a saturat de atata lag (nu poate juca linistita Starcraft 2) asa ca si-a cumparat K acceleratoare. Un accelerator poate fi instalat pe o anumita conexiune pentru a injumatati costul acelei conexiuni. Daca pe o conexiune sunt instalate k acceleratoare costul conexiunii scade de 2k ori. Aurora vrea sa instaleze cele K acceleratoare pentru a minimiza timpul necesar calculatorului ei sa comunice cu serverul. Schimbul de informatii intre calculatoarele 1 si N se produce pe drumul din graf de cost minim. Costul unui drum este egal cu suma costurilor conexiunilor de pe acel drum. Ajutati-o pe Aurora sa joace Starcraft 2.

Date de intrare

Fisierul de intrare retea.in va contine pe prima linie numerele N, M si K reprezentand numarul de calculatoare din retea, numarul de conexiuni intre cele N calculatoare si respectiv, numarul de acceleratoare cumparate de Aurora. Urmatoarele M linii vor contine fiecare cate 3 numere naturale x, y si c reprezentand faptul ca exista o conexiune bidirectionala de cost c intre calculatoarele x si y.

Date de iesire

In fisierul de iesire retea.out veti afisa un singur numar C cu exact 4 zecimale, reprezentand costul minim al unui drum intre calculatoarele 1 si N dupa instalarea celor K acceleratoare.

Restrictii

  • 1 ≤ N ≤ 1 000
  • 1 ≤ M ≤ 100 000
  • 1 ≤ K ≤ 10
  • Costul oricarei conexiuni nu va depasi 106

Exemplu

retea.inretea.out
5 5 2
1 2 1
2 3 9
3 5 1
1 4 5
4 5 5
4.2500

Explicatie

Aurora instaleaza ambele acceleratoare pe muchia de cost 9 ceea ce produce un drum de cost 4.25. Daca ar fi plasat cate un accelerator pe muchiile de cost 5 drumul minim ar fi fost egal cu 5.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?