strong text
Chef wants to make the paths from houses to restaurants more interesting in a city. The city has N buildings, numbered from 1 to N, where each building is either a house (H) or a restaurant (R). There are M two-way roads connecting these buildings, and each road has a cost associated with decorating it. Some costs may be negative, indicating that Chef receives a reward for decorating that road.
Chef’s goal is to decorate roads in such a way that from each house, there is at least one route to a restaurant using only the decorated roads. The task is to calculate the minimal cost of any satisfactory subset of roads. The total cost could be negative if Chef’s rewards for decorating some roads are greater than his spent money.
Input:
- T: the number of test cases
- For each test case:
- N and M: the number of buildings and roads
- A string of N letters, where “R” represents a restaurant and “H” represents a house
- M lines, each containing three integers Xi, Yi, and Zi, describing a road between buildings Xi and Yi with the cost of decorating equal to Zi
Output: For each test case, output the minimal cost of any satisfactory subset of roads.
In simpler terms, Chef wants to find a cost-effective way to decorate roads such that each house has a path to at least one restaurant, and the overall cost is minimized.