Farmer John has bought property in the Caribbean and is going to try to raise dairy cows on a big farm composed of islands. Set in his ways, he wants to surround all the islands with fence. 농부 존은 캐리비언에 땅을 사서 섬을 이루어진 큰 농장에 소들을 키우려고 한다. 그러기 위해 먼저 그느 섬주위를 둘러싸는 울타리을 만들려고 한다. Each island in the farm has the shape of a polygon. 농장에 있는 도는 섬은 다각셩 형태를 가지고 있다. He fences the islands one side at a time 그는 한 번에 하나의 면에 울타리를 친다. (between a consecutive pair of vertices) 연속적인 정점 사이에 and proceeds clockwise around a given island with his fencing operations. 그리고 그의 펜싱 작업으로 주어진 섬 주위에 시계 방향으로 진행해 간다. Since he wants to fence all the islands, 왜냐하면 그는 모든 섬을 울타니를 치기를 원한다. he must at some point travel to any other islands using a boat. 그는 어떤 한 지짐에서 보트를 사용해서 다른 섬으로 이동해야 한다. He can start fencing at any vertex and, at any vertex he encounters, 그는 그가 만나는 어떤 정점에서도 울타리치기 시작을 할수 있다. travel to some vertex on another island, 어떤 정점에서 다른 섬으로 간다 fence all the way around it, and 그 주위에 모든 방법ㅇ로 울타리를 친다, 그리고 then IMMEDIATELY return back to the same vertex on the original island using the same path he traveled before. Each boat trip has a cost defined by a supplied matrix. 그리고 즉시 돌아온다. 처음 정점으로 그 전에 여행한 같은 길을 사용해서 매 보트 비용은 배열로 주어진다. The islands are described by a set of N (3 <= N <= 500) pairs of vertices V1,V2 (1 <= V1 <= N; 1 <= V2 <= N) 섬들은 N 개의 쌍으로 주어진다. ( 3 <= N <= 500 , 1 <= V1,v2 <= N ) although you must figure out how to assemble them into islands. 당신은 그들을 섬으로 어떻게 모으는가를 이해해야만 할지라도 The vertices are conveniently numbered 1..N. 정점은 편의상 1 .. N 으로 명명한다. The cost of traveling by boat between each pair of vertices is given by a symmetric cost matrix 섬들 사이에 이동 비용은 대칭 비용 행렬로 주어진다. whose elements fall in the range 0..1000. 이는 0 .. 1000 이다. What is the minimum cost of surrounding the islands with the fence? 펜스를 치는데 필요한 최소 비용을 구하는 것이 문제이다.
입력
12
1 7
7 3
3 6
6 10
10 1
2 12
2 9
8 9
8 12
11 5
5 4
11 4
0 15 9 20 25 8 10 13 17 8 8 7
15 0 12 12 10 10 8 15 15 8 8 9
9 12 0 25 20 18 16 14 13 7 12 12
20 12 25 0 8 13 14 15 15 10 10 10
25 10 20 8 0 16 20 18 17 18 9 11
8 10 18 13 16 0 10 9 11 10 8 12
10 8 16 14 20 10 0 18 20 6 16 15
13 15 14 15 18 9 18 0 5 12 12 13
17 15 13 15 17 11 20 5 0 22 8 10
8 8 7 10 18 10 6 12 22 0 11 12
8 8 12 10 9 8 16 12 8 11 0 9
7 9 12 10 11 12 15 13 10 12 9 0
INPUT DETAILS:
1 10 4
xxxxxxx x
xxxxxxxxx xxxx
7 xxxxxxxxxxx 6 xxxxxxx
xxxxxxxxxxx 11 xxxxxxxxxx 5
xxxxxxx
xxx
3 12 xxxxxxx 2
xxxxxxxx
xxxxxxxx
xxxxxxxxx
xxxxxxxxx
xxxxxxxxxx
xxxxxxxxxx
8 xxxxxxxxxx 9
The example describes three islands: {1,7,3,6,10}, {4,5,11} and
{2,9,8,12}. The travel costs are provided as a matrix. For example,
the travel cost from vertex 1 to 2 is 15.
출력
30
OUTPUT DETAILS:
There is more than one solution. One is: FJ starts from vertex 3
then 7 and stops at 1, travels to 11 followed by 4,5,11. He then
returns back to 1, and travels to 12 followed by 2,9,8,12. Finally,
he returns back to 1 and continues with 10,6,3,7. The costs are 8
* 2 = 16 for traveling from 1 to 11 and returning back, and 7 * 2
= 14 for traveling from 1 to 12 and back -- a total cost of 30.
출처:usaco 2009 feb