Interesting Graph problem asked in an Interview recently.

Revision en1, by Aspergillus, 2024-08-04 23:26:50

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.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English Aspergillus 2024-08-04 23:26:50 944 help (published)