Un BFS mai jmeker decat altele

[•hertzalau]

https://www.pbinfo.ro/?pagina=probleme&id=1825
Problema asta am primit-o la scoala ca tema si mi-a dat batai de cap.
Voi incerca sa explic cat de clar posibil, dar stiu din experienta ca nu o sa imi iasa, asa ca imi cer scuze din timp.
Prima solutie pe care am incercat-o a fost urmatoarea: pt fiecare prieten i aflam distanta pana la z, sa-i zicem d. Raspunsul era d[1]+d[2]+...+d[k].
Evident, solutia asta nu e corecta.
A doua solutie avea la baza ideea de la prima. Aflam pe rand suma distantelor de la fiecare prieten la fiecare nod. Apoi pt fiecare nod lansam un BFS modificat, in sensul ca conditia de extindere era urmatoarea: if(sol[nod_urmator] > sol[nod_curent]+1) ...
Acum, nici solutia asta nu este corecta.


Acum am incercat altceva. Gandindu-ma ca ordinea in care prietenii se intalnesc conteaza, am generat permutarile multimii 1, 2, 3, ..., k. Pentru fiecare permuare a multimii 1, 2, 3, ...k am aplicat algoritmul de mai sus. Sa zicem ca aveam permutarea 3, 1, 2, 4. Intai lansam BFS-ul pt vf-ul 3, apoi pt vf-ul 1, insumam valorile pt fiecare nod si apoi pt fiecare nod lansam BFS-ul modificat. Apoi din nou, lansam un BFS pt vf-ul 2, insumam valorile pt fiecare nod si lansam un BFS modificat care sa dea solutia multimii 3, 1, 2. Apoi BFS pt vf-ul 4, obtineam suma si lansam BFS-ul modificat si obtineam solutia finala.  Din pacate solutia asta nu este corecta, ma poate ajuta cineva sa imi spuna de ce obtin raspuns gresit?

[•florinel2102]

Pot sa iti spun 100% ca se foloseste programarea dinamica pentru punctaj de 80-100 . O sa revin cu un edit daca am timp(pentru explicatii)