Religious People - Unable to think of strategy

#1

RELIGIOUS PEOPLE
All the people living in our imaginary world Bitworld are very religious.
There are N cities in Bitworld numbered from 1 to N.
Due to a storm, every road in Bitworld was destroyed and now no temples are left.
There are 2 types of operations :

You can construct a temple by giving away A dollars in ith city.
You can repair an already existing road by giving away B dollars.

Your goal is to make temples such that people of every city have access to some temple.
People of the ith city can visit the temple only if :
A temple exists in that city.
OR
There is a path from that city to a city which contains a temple. ( the path should consist of repaired roads only )
You have to minimize the total cost such that people in every city can go to a temple and output this minimum cost.

NOTE : You can only repair the roads which existed and not build on your own.

Input Format:
The first line consists of number of test cases T. Each test case consists of 4 integers N,M,A,B. which denote number of cities, number of roads which existed , cost to build a temple , cost to repair a road. Next M lines contains M pairs denoted by U V which indicates a road existed between U and V.

Constraints:
1 <= T <= 10. 1 <= N <= 100000. 0 <= M <= 100000. 1 <= A,B <= 1000000000. 1 <= U,V <= N. Each road connects 2 distinct cities.

Output Format
Total minimum cost in dollars.

Sample Input
2
3 3 2 1
1 2
3 1
2 3
6 6 2 5
1 3
3 4
2 4
1 2
2 3
5 6
Sample Output
4
12

How can i proceed?

#2

here u have to altleast buld a temple therefore choose a starting point leat say choosen 1 in the first test case then:
make a array that contain value of points have temple now and make another array having the minimum distance cost between the cities (using simple dijikstra algo)
now check for each node min_cost=min(temple_cost,dist_cost(city A, to city B)) for this u have to iterated the whole array of cities containing temple and update the cost and if u have to build a temple then push the city in array of temple and at last just sum up all min_cost of all cities

HOPE this help

1 Like
#3

Hey Lakshay,
As you are not responding to this thread, I am marking your doubt as Resolved for now. Re-open it if required.

Please mark your doubts as resolved in your course’s “ Ask Doubt ” section, when your doubt is resolved.