Ciclu

ciclu

==Include(page="template/taskheader" task_id="ciclu")==

== include(page="template/taskheader" task_id="ciclu") ==
 
Poveste ...
 
h2. Cerinta
 
...
 
h2. Restrictii
 
...
 
h2. Date de intrare
 
...
 
h2. Date de iesire
 
...
 
h2. Exemplu
 
| ciclu.in | ciclu.out |
| linia1
linia2
linia3
| linia1
linia2
|
 
== include(page="template/taskfooter" task_id="ciclu") ==

==Include(page="template/raw")==
 
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.
 
h2. Cerinta
 
Scrieti un program care determina costul mediu minim al unui ciclu de terase.
 
h2. 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)
 
h2. Date de Iesire
 
Sa se afiseze in fisierul ciclu.out costul mediu minim al ciclului gasit, cu o precizie de 2 zecimale.
 
h2. 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
 
h2. Exemplu
 
 
|ciclu.in |ciclu.out |
 
|4 5 |1.75 |
| | |
|1 2 1 | |
| | |
|2 3 1 | |
| | |
|1 3 1 | |
| | |
|3 4 2 | |
| | |
|4 1 3 | |
 
 
 
==Include(page="template/taskfooter" task_id="ciclu")==