Hektor

hektor

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

**Elful**: "Ba, Cristi, de ce ai numit problema asta asa?"

**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...."

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 1
  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

|
table(example). |_. hektor.in |_. hektor.out |
 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

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") ==