Aspergillus's blog

By Aspergillus, history, 6 weeks ago,

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.

• +2

 » 5 weeks ago, # |   0 I think we can solve in nlog(n) from below approch;-> You can make priority queue(min heap) for all nodes(pair ) 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)
•  » » 5 weeks ago, # ^ |   0 hmm sounds good, kind of like multi source bfs. This sounds like a good greedy.