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

Vezi solutiile trimise | Statistici

Retea

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 2k 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.

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 1 000 000

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 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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content