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.