Roads and Libraries - Hackerrank Problem Solution in Python

Roads and Libraries
Hackerrank Problem Solution
Roads and Libraries - Hackerrank Problem Solution

PROBLEM STATEMENT

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 .



SOLUTION IN PYTHON

SHARE If you find this useful, please share with your friends and Community.
CODE TOGETHER..GROW TOGETHER.

More posts

Comments

Post a Comment

Sponsored Content