I have n nodes and some edges connecting them. There are a few colored nodes (it is mentioned which ones) on some of these nodes. My task is to spread this color to the remaining computers.
I can spread a color from node i to j if j is adjacent to i, i already has an antivirus installed, either directly or has it installed previously from some other computer, at a cost of cost[i]. The cost array is given to us as input as well.
what is the minimum cost for spreading the antivirus? The constraints allow for an O(n^2) solution. (sorry for bad format, I am typing on my phone)
My friend asked me this problem which was asked to him in a recent Interview. Can anyone explain what topics i should learn to solve this problem? From the looks of it it seemz like i have to read MST, but I am not sure since the cost is node dependent and not edge so it is difficuly for me.
I think we can solve in nlog(n) from below approch;
-> You can make priority queue(min heap) for all nodes(pair <val,node>) that already have antivirus and repeat following operation till PQ gets empty.
-> take minimum value node and check for all adjacent node(i.e U->V) if V does not have antivirus add antivirus from U with cost cost[U] and add V to the PQ and remove U from priority queue. -> Time complexity — O(nlogn).
Let me know if you think it is incorrect.(I am assuming cost[i]>=0; else answer would be -infinity)
hmm sounds good, kind of like multi source bfs. This sounds like a good greedy.