-Alireza-'s blog

By -Alireza-, history, 3 months ago, In English

__hi! can somebody help me in this problem please? we have a graph and 2 type of reporters: 1 — can report the news to vertices with distance at most 1(from the reporter vertex) the price of this type is 1. 2 — can report to vertices with distance at most 2 . the price of this type is 2. what is the minimum total price to make sure that all vertices will receive the news.

for example in the graph above we can put a reporter of type 2 in the marked vertex and the total price will be 2.

I have a naive solution with O(3^n) time but that's not so good.

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it