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.
The following figure is a sample map of HackerLand where the dotted lines denote possible roads:
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.
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]: each contains two integers that represent cities that can be connected by a new road
- int: the minimal cost
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 .