Roads and Libraries

The Ruler of HackerLand believes that every citizen of the country should have access to a library. Unfortunately, HackerLand was hit by a tornado that destroyed all of its libraries and obstructed its roads! As you are the greatest programmer of HackerLand, the ruler wants your help to repair the roads and build some new libraries efficiently.

HackerLand has A cities numbered from 1 to A. The cities are connected by bidirectional roads. A citizen has access to a library if:

  • Their city contains a library.
  • They can travel by road from their city to a city containing a library.

If Cost to build road is C and Cost to build library is D, find minimum cost of making libraries accessible to all the citizens.

Input Format:

    First argument of Input contains a single integer A denoting number of nodes.
    Second argument of Input contains M x 2 integer matrix B. Each row correspond to a road and both integer denote end points of road. 
    Third argument of Input contains single integer C denoting cost of building road.
    Fourth argument of Input contains single integer D denoting cost of building library.

Output Format:

    Return a single integer denoting minimum cost of making libraries accessible to all.


    1 <= A <= 100000
    0 <= M <= min(A*(A-1)/2 , 100000)
    1 <= B[1],B[2] <= A
    1 <= C,D <= 20000

For Example:

Input 1:
    A = 3, B = [[1, 2], [3, 1], [2, 3]], C = 1, D = 2
Output 1:
Explanation 1:
    one solution is to build library at city 1 and rebuild road 1-2 and 2-3. Cost of this is 2 + 1 + 1 = 4.
Input 2:
    A = 6, B = [[1, 2], [2, 4], [1, 3], [3, 4]], C = 5, D = 2
Output 2:
Explanation 2:
    Build 1 library ar each city.

NOTE: You only need to implement the given function. Do not read input, instead use the arguments to the function. Do not print the output, instead return values as specified. Still have a doubt? Checkout Sample Codes for more details.
Start solving Roads and Libraries on Interview Code Editor
Sign Up
to access hints and editorial solutions for Roads and Libraries


Click here to start solving coding interview questions