Religious People

#1

I guess the sample output is wrong, the minimum cost can be 8 instead of 12. As 1 is connected to 2 and 3, and 4 is also connected to 2 and 3. So building the temple in any one of 2 or 3 and repairing roads between 1->2, 3->2, 4->2, which gives the total cost of 2+1+1+1 = 5. And there was an existing road between 5 and 6, repairing the road and building temple in any one will cost 2+1. Total cost = 5+3 = 8

#2

6 6 2 5
1 3
3 4
2 4
1 2
2 3
5 6

this is the graph
that will be formed
image

we need to build temple at each node to get minimum answer.

#3

Yep, so building in 2 or 3 and repairing 3 roads will cost 2 + 1 + 1 + 1 = 5. And building in 5 or 6 and repairing road will cost 2 + 1 = 3. Total cost = 5+3 = 8. Isn’t it?
People from every city must visit some temple is the question?

#4

cost for building temple -> 2
const of repairing a road-> 5

so if u build one temple and 3 road ,it will cost u 2 + 5*3 => 17

and for another graph it will cost u 2 + 5 => 7
which in total will cost u 24

#5

oops, my bad, sorry for disturbing for such a silly mistake. I was assuming cost of road = 1.

#6

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.