==Include(page="template/taskheader" task_id="traseu")==
 
==Include(page="template/raw")==
 
Link: [1]File-List
 
Traseu
 
 
 
Gigel s-a mutat intr-un oras nou! Pentru a se familiariza cu noile imprejurimi a cumparat harta orasului si a observat ca este alcatuita din M strazi de diferite lungimi, cu sens unic si N intersectii de strazi. Gigel a luat harta si a inceput sa alcauiasca un traseu care porneste dintr-o intersectie anume, trece prin fiecare strada cel putin o data, si revine in intersectia de unde a pornit. Desi dorinta lui de explorare este mare, conditia lui fizica nu este tocmai buna, astfel ca vrea sa gasesasca un traseu in care suma lungimilor strazilor parcurse este minima.
 
h2. Cerinta
 
Scrieti un program care gaseste un traseu de lungime minima in orasul lui Gigel.
 
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.
 
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.
 
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
 
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)
 
2 3 1
 
3 1 2
 
1 4 4
 
4 6 2
 
6 1 5
 
4 5 1
 
5 1 6
 

==Include(page="template/taskheader" task_id="traseu")==
 
Gigel s-a mutat intr-un oras nou! Pentru a se familiariza cu noile imprejurimi a cumparat harta orasului si a observat ca este alcatuita din $M$ strazi de diferite lungimi, cu sens unic si $N$ intersectii de strazi. Gigel a luat harta si a inceput sa alcauiasca un traseu care porneste dintr-o intersectie anume, trece prin fiecare strada cel putin o data, si revine in intersectia de unde a pornit. Desi dorinta lui de explorare este mare, conditia lui fizica nu este tocmai buna, astfel ca vrea sa gasesasca un traseu in care suma lungimilor strazilor parcurse este minima.
 
h2. Cerinta
 
Scrieti un program care gaseste un traseu de lungime minima in orasul lui Gigel.
 
h2. Date de intrare
 
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
 
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
 
* $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
 
table(example). |_. traseu.in |_. traseu.out |
|6 8
1 2 3
2 3 1
3 1 2
1 4 4
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)$.
 
 
==Include(page="template/taskfooter" task_id="traseu")==

References
Visible links
1. file:///home/eval/eval/www/infoarena/docs/arhiva/traseu/enunt.files/filelist.xml
==Include(page="template/taskfooter" task_id="traseu")==

92