== 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!"
Poveste şi cerinţă...
h2. Date de intrare
În fişierul de intrare $hektor.in$ se vor gasi pe prima linie 4 numere intregi : N (numarul de noduri ale grafului), M (numarul de muchii ale grafului), A(nodul in care Hektor se afla initial), B(nodul in care Hektor trebuie sa ajunga). Urmatoarea linie va contine N intregi, cel de-al i-lea reprezentand costul nodului i.
Urmatoarele M linii vor contine cate 2 numere x si y, cu semnificatia ca exista muchie **orientata** de la nodul x, la nodul y.
Fişierul de intrare $hektor.in$ ...
h2. Date de ieşire
În fişierul de ieşire $hektor.out$ se va gasi un numar real, reprezentand costul mediu ca Hektor sa ajunga din nodul A in nodul B.
În fişierul de ieşire $hektor.out$ ...
h2. Restricţii
* N <= 10^5^
* M <= 2 * 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.
* $... ≤ ... ≤ ...$
h2. Exemplu
table(example). |_. hektor.in |_. hektor.out |
| 2 1 1 2
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
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
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
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.
...
== include(page="template/taskfooter" task_id="hektor") ==
