All submissions for this problem are available.
There are N cities in the country and some of them are connected by bidirectional roads. To handle
any emergency situation, they need a emergency cell to be set up at some cities such that, in case of any
emergency in a city, the fire engine, the ambulance etc., can reach that city. Setting up a emergency
cell is expensive and as occurrence of a emergency situation is very rare, its just enough to have each city
connected ( possibly through other cities, by a path ) to a city which has an emergency cell.
Given the cost to setup emergency cell in each of the cities and the map of the country,
find the minimum amount of money government needs to spend. In other words, the Government needs to select
a set of cities S to set up emergency cells such that, every city in the country is connected to at least one
city in S.
The first line contains the number of test cases T. T cases follow. Each test case starts with a line
containing N M, N is the number of cities numbered 1 to N and M is the number of bidirectional roads.
Next line contains N integers, the ith integer is the cost of setting up emergency cell in the ith city.
Each of the next M lines contains, x y , meaning x and y are directly connected by a bidirectional road.
There can be multiple roads between a pair of cities and some roads may even connect a city with itself.
Output T lines, one for each case containing the required answer.
1 <= T <= 5
1 <= N <= 100000
0 <= M <= 100000
0 <= cost_i <= 10000
0 <= x,y < N
Input: 1 4 3 2 4 1 5 1 2 2 3 4 4 Output: 6
Minimum cost is 6, by selecting city 3 and city 4
|Time Limit:||0.403846 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, GO, NODEJS, PYP3|
Fetching successful submissions
If you are still having problems, see a sample solution here.