We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • Hackerrank Home
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Graph Theory
  4. Roads and Libraries

Roads and Libraries

Problem
Submissions
Leaderboard
Discussions
Editorial

Determine the minimum cost to provide library access to all citizens of HackerLand. There are cities numbered from to . Currently there are no libraries and the cities are not connected. Bidirectional roads may be built between any city pair listed in . 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.

Example

The following figure is a sample map of HackerLand where the dotted lines denote possible roads:

image



The cost of building any road is , and the cost to build a library in any city is . Build roads at a cost of and libraries for a cost of . One of the available roads in the cycle is not necessary.

There are queries, where each query consists of a map of HackerLand and value of and . For each query, find the minimum cost to make libraries accessible to all the citizens.

Function Description

Complete the function roadsAndLibraries in the editor below.
roadsAndLibraries has the following parameters:

  • int n: integer, the number of cities
  • int c_lib: integer, the cost to build a library
  • int c_road: integer, the cost to repair a road
  • int cities[m][2]: each contains two integers that represent cities that can be connected by a new road

Returns
- int: the minimal cost

Input Format

The first line contains a single integer , that denotes the number of queries.

The subsequent lines describe each query in the following format:
- The first line contains four space-separated integers that describe the respective values of , , and , the number of cities, number of roads, cost of a library and cost of a road.
- Each of the next lines contains two space-separated integers, and , that describe a bidirectional road that can be built to connect cities and .

Constraints

  • Each road connects two distinct cities.

Sample Input

STDIN       Function
-----       --------
2           q = 2
3 3 2 1     n = 3, cities[] size m = 3, c_lib = 2, c_road = 1
1 2         cities = [[1, 2], [3, 1], [2, 3]]
3 1
2 3
6 6 2 5     n = 6, cities[] size m = 6, c_lib = 2, c_road = 5
1 3         cities = [[1, 3], [3, 4],...]
3 4
2 4
1 2
2 3
5 6

Sample Output

4
12

Explanation

Perform the following queries:

  1. HackerLand contains cities and can be connected by bidirectional roads. The price of building a library is and the price for repairing a road is .
    image

    The cheapest way to make libraries accessible to all is to:

    • Build a library in city at a cost of .
    • Build the road between cities and at a cost of .
    • Build the road between cities and at a cost of .

    This gives a total cost of . Note that the road between cities and does not need to be built because each is connected to city .

  2. In this scenario it is optimal to build a library in each city because the cost to build a library is less than the cost to build a road.
    image

    There are cities, so the total cost is .

Author

torquecode

Difficulty

Medium

Max Score

30

Submitted By

52826

Need Help?


View discussions
View editorial
View top submissions

rate this challenge

MORE DETAILS

Download problem statement
Download sample test cases
Suggest Edits
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy