Hektor

hektor

== include(page="template/taskheader" task_id="hektor") ==

**Elful**: "Ba, Cristi, de ce ai numit problema asta asa?"
**Patrick**: "Am numit-o dupa autorul cartii "Singur pe Lume""
**Elful**: "Te-a tampit de tot BAC-ul asta...pai si cum fac enuntul la ea?"
**Patrick**: "Pai Hektor se simtea singur pe lume asa ca....s-a gandit sa se simta singur pe lume pe un graf orientat aciclic, cu costuri pe cele $N$ noduri ale sale...."
**Elful**: "Asa, si ? ce faci mai departe ?"
**Patrick**: "Pai acum pleaca dintr-un nod A catre un nod B, alegand cu **probabilitate uniforma** atunci cand este intr-un nod X(cu X,evident,intre nodul A si nodul B, sau chiar nodul A), o muchie care conduce spre cel putin un drum spre nodul B....si ideea e ca am vrea sa vedem cu ce cost mediu poate ajunge in nodul B!"
**Elful**: "Macar daca e singur, bani sa aibe!"

**Elful**:"Ba, Patrick, de ce ai numit problema asta asa?"
**Patrick**:"Am numit-o dupa autorul cartii "Singur pe Lume""
**Elful**:"Te-a tampit de tot BAC-ul asta...pai si cum fac enuntul la ea?"
**Patrick**:"Pai Hektor se simtea singur pe lume asa ca....s-a gandit sa se simta singur pe lume pe un graf orientat aciclic, cu costuri pe cele $N$ noduri ale sale...."
**Elful**:"Asa, si ? ce faci mai departe ?"
**Patrick**:"Pai acum pleaca dintr-un nod A catre un nod B, alegand cu **probabilitate uniforma** atunci cand este intr-un nod X, o muchie care conduce spre cel putin un drum spre nodul B....si ideea e ca am vrea sa vedem cu ce cost mediu poate ajunge in nodul B!"
**Elful**:"Macar daca e singur, bani sa aibe!"

h2. Date de intrare

h2. Restricţii

* N <= 10^5^
* M <= 2 * 10^5^

* N <= 10^5

* Costurile nodurilor sunt numere intregi, pe 32 de biti.

* Raspunsul se incadreaza pe tipul double, si este considerat corect daca <tex>|raspunscomisie-raspunsparticipant| <= 0.000001</tex>
* Pentru ca Hektor sa mearga pe o muchie, trebuie sa existe minim un drum de la A la B care sa treaca prin muchia respectiva. In caz contrar, Hektor va ignora muchia aceea.

* Raspunsul se incadreaza pe tipul double, si este considerat corect daca |raspuns_comisie-raspuns_participant| <= 0.000001

h2. Exemplu

  1 2
| 2.00000
|

| 10 11 4 7
  5 9 11 7 3 17 31 13 23 21
  1 2
  1 3
  3 4
  2 4
  4 9
  9 10
  4 8
  8 7
  4 5
  5 6
  6 7
| 54.50000
|
| 13 14 1 2
  1 1 1 1 1 1 1 1 1 1 1 1 1
  10 12
  10 11
  12 13
  11 13
  13 1
  1 3
  1 4
  3 5
  3 8
  4 6
  5 9
  9 7
  7 2
  8 7
| 5.50000
|

h3. Explicaţie

In primul exemplu, oricat de uniforma ar fi probabilitatea, avem o singura varianta de a ajunge din nodul A=1 in nodul B=2, si anume mergand pe muchia 1->2.
In al doilea exemplu, din 4, Hektor poate merge doar spre nodul 8 sau spre nodul 5. Acesta nu poate merge spre nodul 9 deoarece acest nod nu genereaza nici macar un drum spre nodul 7.

Oricat de uniforma ar fi probabilitatea, avem o singura varianta de a ajunge din nodul A=1 in nodul B=2, si anume mergand pe muchia 1->2.

== include(page="template/taskfooter" task_id="hektor") ==