Fişierul intrare/ieşire:traseu.in, traseu.outSursăpreONI 2004
AutorMircea Bogdan PasoiAdăugată de
Timp execuţie pe test0.1 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

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.

Cerinta

Scrieti un program care gaseste un traseu de lungime minima in orasul lui Gigel.

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.

Date de iesire

Pe prima linie din fisierul traseu.out se va afisa un singur numar natural reprezentand lungimea minima a traseului lui Gigel.

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

Exemplu

traseu.intraseu.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

Explicatii

Traseul ales este: (1,2,3,1,4,6,1,4,5,1).

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content