Un tânăr elf dorește să viziteze toate
satele locuite de elfi. El dorește să pornească
din satul său, să viziteze fiecare
sat o singură dată și să se întoarcă
în satul său.
Elful trebuie să își aleagă traseul astfel încât distanța totală a drumului său să fie minimă. El are la dispoziție o hartă pe care sunt specificate distanțele dintre oricare două sate, urmând cărările obișnuite. Elful nu se va abate de la aceste cărări din motive de siguranță. Cele n sate ale elfilor sunt identificate prin numere cuprinse între 1 și n, iar satul natal al elfului care va pleca în această călătorie este cel identificat prin 1.
Fișierul de intrare INPUT.TXT conține
pe prima linie numărul n al satelor
elfilor.
Fiecare dintre următoarele n linii va conține câte n numere. Aceste numere reprezintă distanțele dintre sate.
Fișierul de ieșire OUTPUT.TXT trebuie
să conțină pe prima linie lungimea
totală a traseului elfului.
Fiecare dintre următoarele n + 1 linii va conține numărul de ordine al unui sat. Ordinea liniilor va indica ordinea în care sunt parcurse satele de către elf. Evident, pe prima și pe ultima dintre aceste linii se va afla numărul 1.
INPUT.TXT
5 0 1 5 1 2 1 0 3 7 2 5 3 0 4 4 1 7 4 0 2 2 2 4 2 0 OUTPUT.TXT 11 1 4 5 3 2 1
|