906 . Power Grid
TopCoder
Description
onMouseDown="this.src='http://ontheroll.files.wordpress.com/2008/12/power-grid.jpg'"
onMouseUp="this.src='http://images.boardgamegeek.com/images/pic195014_md.jpg'">
Do you know the board game "Power Grid"?
In this board game, players mark routes between cities for connection,
and then bid against each other to purchase the power plants that they use to power their cities.
However, as plants are purchased, newer, more efficient plants become available, so by merely purchasing, you're potentially allowing others access to superior equipment.
Additionally, players must pay for the raw materials (coal, oil, garbage, and uranium) needed to power their plants except green power plants such as wind farm and solar plants.
Is it interesting? Ha, for this problem, lets consider a simpler situation.
You are an employee of a power company,
and your company already built a power transmission network.
There is a kernel in this network, the power plant.
The power is transmitted from this kernel to each city via several substations.
There are wires that connect cities, substations, and the kernel.
To prevent short circuits, each city and substation has only one route to the kernel.
One day after a typhoon, your boss wants you to check whether the network is still working, i.e., none of the wires are broken.
To show that you work very hard, you decide to walk along the wires and check them by yourself.
There are several limitations of your walk:
- Your walk starts and ends at the kernel, which your office is located in.
- During your walk, you can only walk along wires.
- After you walk along a wire from one end to another, you can check whether this wire works.
- You need to visit each city at least once.
- You move at constant speed, 1 meter per second.
- You should use least time to finish your walk.
It is a boring job, I know. But it is not that bad.
In each city, the local employees will serve you desserts when you visit them.
However, they start eating the desserts before you come!
They eat one unit of desserts per second.
At your arrival, they give you the remaining desserts.
How many desserts can you collect during your walk?
You can assume that picking up desserts takes 0 seconds.
Input Format
The first line in the input is an integer T, and T test cases follow.
Each test case starts with a line containing two integers C and S,
where C is the number of cities and S is the number of internal substations.
Cities are labeled from 1 to C, substations are labeled from C+1 to C+S, and
the kernel is labeled C+S+1.
Following this there will be C lines, each with three integers, p_i, l_i, and d_i.
For the i-th line,
p_i is the label of the substation/kernel that links to city i directly,
l_i is the length (in meter) of the wire connecting p_i and city i,
and d_i is the number of desserts at city i at the time when your walk starts.
Then S lines follow, each with two integers, s_j and l_j.
For the j-th line, s_j is the label of the substation/kernel that transmit power to substation j,
and l_j is the length of the wire between s_j and substation j.
There is one blank line between two consecutive test cases.
Output Format
For each test case, please output one line containing an integer V, which is the maximum number of desserts that you can collect during your walk.
0 <= C+S < 100000
C+1 <= p_i, s_j <= C+S+1
1 <= l_i <= 100
109 <= d_i <= 1013
Sample Input 1
2 1 1 2 1 1000000000 3 1 3 1 5 10 1000000000 4 5 1000000000 4 5 1000000000 5 100
Sample Output 1
999999998 2999999730
Hints
Problem Source
Migrated from old NTUJ.
Ferng
Subtasks
| No. | Testdata Range | Score |
|---|