==Include(page="template/taskheader" task_id="traseu")==
== 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.
Poveste ...
h2. Cerinta
Scrieti un program care gaseste un traseu de lungime minima in orasul lui Gigel.
...
h2. Date de intrare
h2. Restrictii
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 intrare
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
h2. Date de iesire
* $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
| traseu.in | traseu.out |
| linia1
linia2
linia3
| linia1
linia2
|
Traseul ales este: $(1,2,3,1,4,6,1,4,5,1)$.
==Include(page="template/taskfooter" task_id="traseu")==
== include(page="template/taskfooter" task_id="traseu") ==
