Atenţie! Aceasta este ultima versiune a paginii, scrisă la 2020-10-04 14:54:04.
Revizia anterioară Revizia următoare
Revizia anterioară Revizia următoare
Observatie: Perechile X, Y posibile la un moment dat sunt cel mult O(valori distincte).
Putem deci sa mentinem toate aceste potentiale drumuri cu costul corespunzator, si la fiecare pas sa alegem pe cel cu cost minim.
La fiecare pas vom satura o muchie S-X sau o muchie Y-D, deci avem cel mult O(N) pasi. Iar o data aleasa o pereche se updateaza cel mult 3 alte perechi (pot disparea 2 vechi, si sa apara una noua).
Problema e cum putem calcula eficient care e costul unei perechi X, Y.
