IITWPC4I - Petya and Repairment of Roads
Petya live in a city named Mayapur. As the in the morning, everybody likes to drink hot tea in bed. So the citizens needs milk to produce tea. For this purpose, they want that they should be able to go to atleast some milkmen using bi-directoinal roads. There are m roads in the city but all of them are currently unrepaired, hence not a state of use.
As Petya cares about his city a lot. He got a project about reparing these roads. So he has to select some roads to repair such that every citizen is connected to atleast one milkman. For reparing each road he needs to pay a cost. As he does not want to spend a lot of money in it, He wants to minimize the cost needed in this project. Note that a milkmen does not need to go to some other milkmen for milk as he can take milk from his own home.
Help Petya in finding out minimum cost needed to repair the roads in the above given way. If it is not possible for a citizen to connect to any of the milkmen, output "impossible" (without quotes).
First line contains T : number of test cases. (1 <= T <= 100)
For each test case, First line contains two space seperated number n, m: number of citizens in Mayapur and m denotes number of unrepaired roads.
Next line contains n space integers either 0 or 1 which indices that citizen is milkmen or not[1 means he is a milkman]. (1 <= n <= 10^5)
Then For each of the next m lines, each line contains three space seperated integers u, v and c, denoting that there exists a unrepaired road between u and v such that cost of repairing of road is c. (1 <= u, v <= n and u != v)
(1 <= m <= min (n * (n - 1) / 2, 2 * 10^5). 1 <= c <= 10^9.)
For each test case output the cost as required.
0 1 0 1 0
1 2 11
1 3 1
1 5 17
2 3 1
3 5 18
4 5 3
2 4 5
A must do problem. It made my day. Try with disjoint sets and you will learn a lot :)
Read the question carefully.
Watch out for blanklines in input when solving with Python.
AC in one go:-)
kruskal rocks as usual
is the city connected or not ??
Good question with tricky test case!!
Its a classic Prim's algorithm question...
Strong and tricky test cases..!!