Fişierul intrare/ieşire:hektor.in, hektor.outSursăConcursul National de Informatica "Adolescent Grigore Moisil" 16
AutorPatrick SavaAdăugată deAGMinformaticaAGMInformatica AGMinformatica
Timp execuţie pe test0.2 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

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 |raspunscomisie-raspunsparticipant| <= 0.000001
  • 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.inhektor.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?