Scrieti un program care gaseste un traseu de lungime minima in orasul lui Gigel.
h2. Date de Intrare
h2. Date de intrare
Pe prima linie din fisierul traseu.in se gasesc numerele N si M separate prin cate un spatiu. Pe urmatoarele M linii se vor gasi triplete de numere i j k cu semnificatia ca exista o strada de la intersectia cu numar i la intersectia cu numar j de lungime k.
Pe prima linie a fisierului $traseu.in$ se gasesc numerele $N$ si $M$ separate prin cate un spatiu. Pe urmatoarele $M$ linii se vor gasi triplete de numere $i j k$ cu semnificatia ca exista o strada de la intersectia cu numar $i$ la intersectia cu numar $j$ de lungime $k$.
h2. Date de Iesire
h2. Date de iesire
Pe prima linie din fisierul traseu.out se va afisa un singur numar natural reprezentand lungimea minima a traseului lui Gigel.
Pe prima linie din fisierul $traseu.out$ se va afisa un singur numar natural reprezentand lungimea minima a traseului lui Gigel.
h2. Restrictii si precizari
S 1 <= N <= 60
S Lungimile strazilor sunt numere naturale din intervalul [1, 10.000]
S Daca intre doua intersectii i si j exista o strada, atunci cu singuranta nu va exista o strada intre intersectiile j si i
S Se garanteaza ca exista cel putin un traseu in oras care trece prin fiecare strada cel putin o data si incepe si se termina in aceeasi intersectie
* $1 ≤ N ≤ 60$
* Lungimile strazilor sunt numere naturale din intervalul $[1, 10 000]$
* Daca intre doua intersectii $i$ si $j$ exista o strada, atunci cu singuranta nu va exista o strada si intre intersectiile $j$ si $i$
* Se garanteaza ca exista cel putin un traseu in oras care trece prin fiecare strada cel putin o data si incepe si se termina in aceeasi intersectie
h2. Exemplu
traseu.in traseu.out Explicatie
6 8 28 Traseul ales este:
1 2 3 (1,2,3,1,4,6,1,4,5,1)
table(example). |_. traseu.in |_. traseu.out |
|6 8
1 2 3
2 3 1
3 1 2
1 4 4
4 6 2
4 6 2
6 1 5
4 5 1
5 1 6
|28 |
h3. Explicatii
Traseul ales este: $(1,2,3,1,4,6,1,4,5,1)$.
References
Visible links
1. file:///home/eval/eval/www/infoarena/docs/arhiva/traseu/enunt.files/filelist.xml
==Include(page="template/taskfooter" task_id="traseu")==
