Diferente pentru problema/hektor intre reviziile #11 si #32

Diferente intre titluri:

hektor
Hektor

Diferente intre continut:

== include(page="template/taskheader" task_id="hektor") ==
**Elful**: "Ba, Patrick, de ce ai numit problema asta asa?"
**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...."
h2. Restricţii
* N <= 10^5
* 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 |raspuns_comisie-raspuns_participant| <= 0.000001
* 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
  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
  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
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 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") ==

Nu exista diferente intre securitate.

Topicul de forum nu a fost schimbat.