Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | retea.in, retea.out | Sursă | Algoritmiada 2010, Runda 4 |
| Autor | Cosmin Gheorghe | Adăugată de |  Gheorghe Cosmin •gcosmin |
| Timp execuţie pe test | 0.15 sec | Limită de memorie | 36096 kbytes |
| Scorul tău | N/A | Dificultate | N/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.in | retea.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.
