Fişierul intrare/ieşire:tero.in, tero.outSursăWinter Challenge 2008, Runda 1
AutorBogdan Alexandru Stoica, Mugurel Ionut AndreicaAdăugată defireatmyselfBogdan-Alexandru Stoica fireatmyself
Timp execuţie pe test0.1 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Tero

Dupa ce a reusit sa-si indeplineasca, cu succes, toate indatoririle de primar, Dubluveu este ales Presedintele Romaniei. La prima intalnire cu Serviciul Roman de Informatii, este informat de un atac terorist care ar urma sa aiba loc foarte curand. Din fericire, SRI cunoaste planurile teroristilor. Conform raportului, raufacatorii doresc sa atace Capitala si Orasul-port de la Marea Neagra. Romania are N orase numerotate de la 1 la N, legate prin M drumuri bidirectionate de diferite lungimi. Capitala are numarul de ordine 1, iar Orasul-port are numarul de ordine N. O solutie propusa de catre seful SRI este ca, toate drumurile dintre obiectivele vizate sa fie pazite de cei S soldati ai armatei. Astfel, Presedintele ar putea cere plasarea soldatilor pe un drum, oricat de aprope de unul dintre orasele ce-l marginesc, dar nu in orase (pentru a evita panica). Fiind o persoana care gandeste situatia in profunzime, Dubluveu si-a pus urmatoarea problema: Daca teroristii reusesc, totusi, sa atace unul dintre orasele tinta, soldatii ar trebui mobilizati in cel mai scurt timp in orasul atacat. Din fericire, toti militarii au viteza constanta de 1m/s, iar timpul necesar mobilizarii unui soldat este egal cu maximul distantelor pana la cele doua orase. Din pacate, planul trebuie intai realizat teoretic si, cum timpul este foarte scurt, va fi nevoie de un programator cu experienta care s-o faca.

Cerinta

Presedinitiea v-a insarcinat pe dumneavoastra sa va ocupati cu implementarea planului contra teroristilor. Deci, trebuie sa gasiti o aranjare a celor S soldati, astfel incat oricare drum de la 1 la N sa fie pazit, soldatii sa nu fie plasati in oras, iar mobilizarea totala a acestora sa fie minima.

Date de intrare

Pe prima linie a fisierului de intrare tero.in se vor afla 3 numere N, M, si S cu semnificatiile din enunt. Urmeaza apoi M linii cu cate trei numere intregi i, j si dist, avand semnificatia ca de intre orasul i si orasul j exista un drum de lungime dist.

Date de iesire

In fisierul de iesire tero.out se va scrie, pe o singura linie, un numar real cu o zecimala exacta, reprezentand mobilizarea minima.

Restrictii

  • 1 ≤ N ≤ 700
  • 1 ≤ M ≤ 131 072
  • 1 ≤ S ≤ M
  • numarul de soldati este suficient de mare pentru a bloca toate drumurile de la 1 la N
  • pe un drum pot fi plasati oricati soldati
  • lungimea unui drum nu depaseste 100 000
  • punctajul se va acorda in functie de diferenta absoluta dintre raspunsul dumneavoastra si raspunsul comisiei:
    • 10 puncte/test daca diferenta ≤ 0.1
    • 5 puncte/test daca 0.1 < diferenta ≤ 34.5
    • 3 puncte/test daca 34.5 < diferenta ≤ 69
    • 1 punct/test daca 69 < diferenta ≤ 103.5
    • 0 puncte/test daca diferenta este > 103.5

Exemplu

tero.intero.out
5 6 3
1 2 2
1 3 1
1 4 1
3 4 3
2 5 1
4 5 2
1.5

Explicatie

Daca primul soldat este plasat pe muchia de la 1 la 2, la distanta 1.5 de 1 si 0.5 de 2, atunci distanta de la 1 la soldat este 1.5, iar distanta de la 5 la soldat este tot 1.5. Maximul dintre distante este 1.5. Daca plasez ceilaiti soldati pe muchia de la 4 la 5, la distanta 1.5 de 5 si, respectiv, 0.5 de 4, distanta de la 1 la soldati este de 1.5 si distanta de la 5 este tot 1.5. Maximul dintre distante este 1.5. Aceasta este mobilizarea minima, din oricare alta asezare rezultand o valoare mai mare.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content