Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2006-11-11 11:23:46.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:ciclu.in, ciclu.outSursăStelele Informaticii 2003
AutorRadu BerindeAdăugată de
Timp execuţie pe test0.75 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Ciclu

Aceasta pagina a fost importata din infoarena1 si nu este inca prelucrata.
Sterge ==Include(file="template/raw")== cand esti multumit cu continutul paginii.

Ciclu

Acarie, fericit ca a trecut examenul la algebra pleaca in oras sa sarbatoreasca. Este atat de fericit, incat nu se multumeste cu un simplu traseu intre terase, ci vrea un ciclu pentru a fi sigur ca poate continua sa petreaca cat timp doreste. Din pacate, drumurile dintre terase au costuri diferite si nu sunt bidirectionale. Acarie nu este interesat neaparat sa minimizeze costul acestui ciclu, ci doreste sa minimizeze costul mediu al ciclului (evident, vrea sa mearga cat mai putin intre terase, adica costul ciclului imparit la numarul de terase sa fie minim).

Ajutati-l si de aceasta data pe Acarie si va va cinsti toata ziua.

Cerinta

Scrieti un program care determina costul mediu minim al unui ciclu de terase.

Date de Intrare

Din fisierul ciclu.in se citesc N (numarul de terase), M (numarul de drumuri unidirectionale) si cele M drumuri directe dintre terase. Acestea sunt date fiecare pe cate o linie, reprezentate de trei intregi - terasa de unde porneste drumul, terasa unde ajunge drumul (numere intre 1 si N) si costul drumului (intreg strict pozitiv mai mic decat 100000)

Date de Iesire

Sa se afiseze in fisierul ciclu.out costul mediu minim al ciclului gasit, cu o precizie de 2 zecimale.

Restrictii

. 2 <= N <= 1000

. 2 <= M <= 4000

Observatii

. Se garanteaza ca exista cel putin un ciclu

. Rezultatul se va verifica cu o precizie de 0.1

Exemplu

ciclu.inciclu.out
4 51.75
1 2 1
2 3 1
1 3 1
3 4 2
4 1 3
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?