== include(page="template/taskheader" task_id="retea") ==
Poveste şi cerinţă...
Aurora Flash e conectata la o retea de bloc cu $N$ calculatoare si $M$ conexiuni bidirectionale. Fiecare conexiune intre doua calculatoare $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 $2^k^$ ori. Aurora vrea sa instaleze cele $K$ acceleratoare pentru a minimiza timpul necesar calculatorului ei sa comunice cu serverul. Schimbul de informatii intre doua calculatoare se produce pe drumul de cost minim, ce uneste cele doua calculatoare. Costul unui drum este egal cu suma costurilor conexiunilor de pe acel drum. Ajutati-o pe Aurora Flash sa joace Starcraft 2.
h2. Date de intrare
Fişierul de intrare $retea.in$ ...
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$.
h2. Date de ieşire
h2. Date de iesire
În fişierul de ieşire $retea.out$ ...
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.
h2. Restricţii
h2. Restrictii
* $1 ≤ N ≤ 1 000$
* $1 ≤ M ≤ 100 000$
* $1 ≤ K ≤ 10$
* Costul oricarei conexiuni nu va depasi $1 000 000$
* $... ≤ ... ≤ ...$
h2. Exemplu
table(example). |_. retea.in |_. retea.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 5 5 2
1 2 1
2 3 9
3 5 1
1 4 5
4 5 5
| 4.2500
|
h3. Explicaţie
h3. Explicatie
...
Aurora instaleaza ambele acceleratoare pe conexiunea de cost 9 ceea ce produce un drum de cost $4.25$. Daca ar fi plasat cate un accelerator pe conexiunile de cost $5$ drumul minim ar fi fost egal cu $5$.
== include(page="template/taskfooter" task_id="retea") ==
