The Christmas Cookies
All submissions for this problem are available.
CodeChef has prepared christmas cookies for everyone in the town. He gives the responsibility of distributing the cookies to Samosa Bhai.
There are N houses and E roads in the town. Each road starts from one house and ends at another and there are no other houses on the road. There can be more than one direct road between two houses. Each road has some road tax. Once you have paid the road tax for a road, you can travel on that road any number of times. The problem is, a Christmas tree has to be installed in the town. It can only be installed on one of the roads resulting in that road being blocked. As a result, Samosa Bhai will not be able to use that road for travelling.
Now, for each road, Samosa Bhai wants to know the minimum amount of road tax he will have to pay to distribute candies in all the houses, if the Christmas tree were to be placed on that road. Samosa Bhai can start his journey from any of the houses.
The first line contains T, the number of test cases to follow.
The first line of each test case contains the integers N and E separated by a space.
Next, E lines follow. Each line contains three space-separated integers — x, y, and the road tax of a direct road between house x and house y.
For each road (in the same order as input), output the value of the minimum road tax paid if the christmas tree is placed on that road and it is still possible to distribute cookies in all houses, otherwise output -1.
- 1 ≤ T ≤ 1000
- 1 ≤ N ≤ 105
- 1 ≤ E ≤ 2*105
- 1 ≤ Sum of E over all cases ≤ 2*105
- 1 ≤ Sum of N over all cases ≤ 105
- 1 ≤ Road Tax ≤ 108
Input: 1 5 7 1 2 2 1 4 4 2 3 6 2 5 8 3 5 10 4 3 12 1 5 14 Output: 30 28 24 22 20 20 20
Example case 1
- Road from House 1 to House 2 (i.e Road 1) is blocked:
Use Roads 2, 3, 4 and 6. Total Tax paid = 30
- Road from House 1 to House 4 (i.e Road 2) is blocked:
Use Roads 1, 3, 4 and 6. Total Tax paid = 28
- Road from House 2 to House 3 (i.e Road 3) is blocked:
Use Roads 1, 2, 4 and 5. Total Tax paid = 24
|Tags||acm15kol, decomposition, devuy11, heavy-light, range-queries, spanningtree|
|Time Limit:||1.5 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA|
Fetching successful submissions
If you are still having problems, see a sample solution here.