| Fişierul intrare/ieşire: | hektor.in, hektor.out | Sursă | Concursul National de Informatica "Adolescent Grigore Moisil" 16 |
| Autor | Patrick Sava | Adăugată de |  AGMInformatica •AGMinformatica |
| Timp execuţie pe test | 0.2 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate |   1/5 |
Vezi solutiile trimise | Statistici
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!"
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.
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.
Restricţii
- N <= 105
- M <= 2 * 105
- Costurile nodurilor sunt numere intregi, pe 32 de biti.
- Raspunsul se incadreaza pe tipul double, si este considerat corect daca
- 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.
Exemplu
| 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 |
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.
