|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|2 초||512 MB||3||2||2||100.000%|
You are running a farm which has N (1 ≤ N ≤ 100) animals. You went to the store and bought M = N pre-made pens that will house your animals. Pens satisfy the following conditions:
The animals, however, have a game they like to play called “Escape from the pen.” They assign a cost to each edge of the pen, and they determine the minimum cost for all of the animals to meet in the same area by trampling over the edge of various pens. The animals may meet inside a particular pen or outside of all the pens. Also note that once an edge has been trampled, any animal may pass over it without incurring any cost.
You will be given a description of the pens, along with the placement of animals, and you are to figure out what the smallest cost is to move all the animals into the same area.
The first line of input will be the integer M, the number of pens. On the next M lines, there will be a description of each pen, with one description per line. The description is composed of three components, with each component separated by one space, as follows:
For the corner and edge cost description, the descriptions are given in cyclical order. For example, the following description of a pen
3 1 2 3 7 4 6
means that there are three corners, and thus, three edges, where the edge (1, 2) has cost 7, the edge (2, 3) has cost 4 and the edge (3, 1) has cost 6.
On one line, output the minimal cost that will allow all the animals to gather in one pen or outside all of the pens.
4 3 1 2 3 7 4 6 4 1 2 4 5 7 7 2 6 4 4 7 6 5 4 8 9 2 5 3 2 4 7 8 4 7 4 7 7
The diagram below explains the input data:
where the circled numbers are the corners, and the numbers in italics are the edge costs. Notice that if the edges (2, 3), (4, 5) and (4, 7) are removed, all the animals can meet in the pen which has five sides.