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

Vezi solutiile trimise | Statistici

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 100.000)

Date de Iesire

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

Restrictii si precizari

  • 2 ≤ N ≤ 1000
  • 2 ≤ M ≤ 4000
  • Se garanteaza ca exista cel putin un ciclu
  • Rezultatul se va verifica cu o precizie de 0.1

Exemplu

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

Cum se trimit solutii?

remote content