Apophis dorește să viziteze toate cele N planete pe care le stăpânește. Oricare două dintre acestea sunt conectate prin intermediul unor porți stelare. El cunoaște care este cantitatea de energia necesară deplasării de la o planetă la alta și dorește să viziteze toate planetele consumând cât mai puțină energie.
Planetele aflate sub dominația lui Apophis sunt numerotate de la 1 la N. Inițial el se află pe planeta sa de reședință (identificată prin 1) și, după vizitarea tuturor planetelor el trebuie să se întoarcă aici. Pentru ca locuitorii nici uneia dintre planete să nu se simtă favorizați, Apophis a decis că va vizita fiecare planetă (cu excepția celei de reședință) exact o dată.
Prima linie a fișierului de intrare STARGATE.IN conține numărul N al planetelor care îl recunosc pe Apophis ca zeu.
Pe următoarele linii, până la sfârșitul fișierului, se află câte trei numere întregi x, y și c cu semnificația: pentru deplasarea între planetele x și y este necesară o cantitate de energie c.
Prima linie a fișierului de ieșire STARGATE.OUT va conține cantitatea totală de energie de care are nevoie Apophis pentru a vizita (pornind din planeta de reședință) toate planetele pe care le stăpânește și a reveni pe planeta de reședință.
Pe următoarea linie se vor afla numerele de ordine ale planetelor (separate prin spații), în ordinea în care vor fi vizitate.
3 <= N <= 500;
cantitatea de energie necesară trecerii de la o planetă la alta este un număr întreg cuprins între 1 și 255; cantitatea de energie necesară trecerii de la planeta x la planeta y este egală cu cea necesară trecerii de la planeta y la planeta x.
STARGATE.IN
Vom considera că pentru fiecare test, se vor putea obține cel mult X puncte.
Concurenții care vor obține cea mică valoare CMin pentru cantitatea totală de energie necesară vor primi X puncte pentru testul respectiv.4 1 2 2 1 3 3 1 4 4 2 3 6 2 4 8 3 4 12 STARGATE.OUT 21 1 3 2 4 1
Ceilalți concurenți, care au furnizat un traseu valid pentru care este necesară o cantitate de energie C, vor obține X * CMin / C puncte pentru testul respectiv. Această valoare va fi aproximată cu două zecimale exacte. Punctajul final va fi obținut prin adunarea punctajelor de la fiecare test și rotunjirea acestuia la cel mai apropiat număr întreg. Dacă traseul nu este valid, concurenții nu vor primi nici un punct pentru testul respectiv. De exemplu, dacă pentru un test se pot obține cel mult 5 puncte, cel mai bun rezultat obținut de un concurent constă într-un traseu pentru care cantitatea necesară de energie este 89, iar un alt concurent obține o soluție pentru care cantitatea necesară de energie este 145, atunci, pentru testul respectiv, punctajul concurentului va fi de 5 * 89 / 145 = 3.06 puncte. |