Gather
Vom calcula o matrice A[i][j] - distanta minima ca sa ajungem in celula i urmariti de detinutii care corespund cifrelor de 1 in reprezentarea binara a lui j. De fapt ne vor interesa doar valorile pentru celulele in care se afla detinuti, de aceea vom calcula doar aceste valori.
Pentru calcularea acestor valori vom construi un graf format din noduri de tipul (i,j) unde i este o celula in care se afla un detinut, iar j este un numar intre 0 si 2K. Vom avea muchie de la (i,j) la (t,j+2t) daca t nu apare in reprezentarea binara a lui j si exista un drum de la celula celula i la celula t astfel incat capacitatea minima a muchiilor de pe acest drum sa fie mai mare sau egala decat numarul de biti de 1 din descompunerea lui j(adica numarul de detinuti care il urmaresc pe Gigel). Costurile asociate acestei muchii va fi exact suma costurilor de pe drumul minim de la i la t care respecta conditia respectiva.
Pentru a calcula toate costurile muchiilor noului graf se aplica de k2 ori algoritmul lui Dijkstra. Vom calcula pentru fiecare i de la 1 la k si pentru fiecare j de la 1 la k drumurile minime de la nodul in care se afla detinutul i la toate nodurile folosind doar muchii ce au capcitate mai mare sau egala cu j.
Odata construit noul graf se poate aplica Dijkstra pe el pentru a calcula matricea A, sau se poate folosi programare dinamica datorita aciclicitatii grafului.
Complexitatea finala va fi O( K2*N2 + 2K*K2).
