Posted on 2009-04-23 16:02
superman 閱讀(223)
評論(0) 編輯 收藏 引用 所屬分類:
USACO
1 #include <cmath>
2 #include <iostream>
3
4 using namespace std;
5
6 struct Point
7 {
8 int x, y;
9 } ;
10
11 int sqr(int n)
12 {
13 return n * n;
14 }
15
16 int n;
17 Point p[150];
18 bool adj[150][150];
19 double dist[150][150];
20
21 int subGraphCnt;
22
23 int visited[150];
24 void dfs(int p)
25 {
26 visited[p] = subGraphCnt;
27 for (int i = 0; i < n; i++)
28 if (adj[p][i] == true && visited[i] == false)
29 dfs(i);
30 }
31
32 int main()
33 {
34 freopen("cowtour.in", "r", stdin);
35 freopen("cowtour.out", "w", stdout);
36
37 cin >> n;
38 for (int i = 0; i < n; i++)
39 cin >> p[i].x >> p[i].y;
40
41 cin.get();
42 for (int i = 0; i < n; i++)
43 {
44 for (int j = 0; j < n; j++)
45 {
46 char c;
47 c = cin.get();
48 adj[i][j] = c - '0';
49 }
50 cin.get();
51 }
52
53 for (int i = 0; i < n; i++)
54 for (int j = i + 1; j < n; j++)
55 if (adj[i][j])
56 {
57 int tmp = sqr(p[i].x - p[j].x) + sqr(p[i].y - p[j].y);
58 dist[i][j] = dist[j][i] = sqrt(tmp);
59 }
60 else
61 dist[i][j] = dist[j][i] = INT_MAX;
62
63 for (int k = 0; k < n; k++)
64 for (int i = 0; i < n; i++)
65 for (int j = 0; j < n; j++)
66 if (dist[i][k] != INT_MAX && dist[k][j] != INT_MAX)
67 dist[i][j] <?= (dist[i][k] + dist[k][j]);
68
69 for (int i = 0; i < n; i++)
70 if (visited[i] == 0)
71 {
72 subGraphCnt++;
73 dfs(i);
74 }
75
76 double x[150] = { 0 };
77 for (int i = 0; i < n; i++)
78 for (int j = 0; j < n; j++)
79 if (dist[i][j] != INT_MAX)
80 x[i] >?= dist[i][j];
81
82 double ans = INT_MAX;
83 for (int i = 0; i < n; i++)
84 for (int j = 0; j < n; j++)
85 if (visited[i] != visited[j])
86 {
87 double tmp = sqrt(sqr(p[i].x - p[j].x) + sqr(p[i].y - p[j].y));
88 tmp += (x[i] + x[j]);
89 ans <?= tmp;
90 }
91 for (int i = 0; i < n; i++)
92 ans >?= x[i];
93
94 cout.setf(ios_base::showpoint);
95 cout.setf(ios_base::fixed);
96 cout.precision(6);
97 cout << ans << endl;
98
99 return 0;
100 }
101