Hint 3

nave-bunicu-hint3

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$.

Scrie aici despre nave-bunicu-hint3