h1(#djok). 'Solutia':algoritmiada-2019/runda-finala/solutii/djok problemei 'Djok':problema/djok

Multumim lui ==user(user="georgerapeanu" type="tiny")== pentru editorial!
 

h1. Solutie <tex> O(N^2logN) </tex> - 30p
Sa zicem ca Tanaka alege sa controleze monstruletul din nodul $i$. Atunci o strategie optima pentru el este sa atace tot timpul cel mai slab monstrulet din nodurile nevizitate in care poate ajunge. Strategia aceasta este optima pentru ca fie Tanaka poate bate monstruletul, caz in care vitejia monstrului controlat fie creste fie ramane la fel, fie nu il poate bate, dar atunci el nu va putea bate niciun alt monstrulet la care are acces. Asadar problema ne cere ca, pentru o multime de noduri vizitate, sa gasim nodul adiacent unuia dintre nodurile deja vizitate, care contine monstruletul cu cea mai mica vitejie. Asadar, pentru un nod de inceput $i$ fixat, putem sa il bagam intr-un heap. Acum vom face un algoritm asemanator celui de BFS/Dijkstra, si vom tot extrage din heap nodul cu cel mai mic cost, vom verifica daca putem bate monstruletul din nodul acela, si daca da il scoatem si ii adaugam in heap vecinii nevizitati, si eventual actualizam vitejia monstruletului nostru.