老师讲过的……但是忘了好多唉，重新写了一遍
1 #include <stdio.h>
2 #include <string.h>
3 #include <math.h>
4 #define MAX 200000000
5 using namespace std;
6 FILE * fin = fopen("file.in", "r");
7 FILE * fout = fopen("file.out", "w");
8 struct point
9 {
10 double x, y;
11 };
12 point vert[101];
13 double res[101][101];
14 double dis(int i, int j)
15 {
16 return sqrt((vert[i].x - vert[j].x) * (vert[i].x - vert[j].x) + (vert[i].y - vert[j].y) * (vert[i].y - vert[j].y));
17 }
18 double min(double a, double b)
19 {
20 return a < b ? a : b;
21 }
22 double work(int n)
23 {
24 double s, Min = MAX;
25 res[2][1] = dis(2, 1);
26 for (int i = 2; i <= n; i++)
27 for (int j = 1; j < i; j++)
28 {
29 res[i][j] = min(res[i][j], res[i - 1][j] + dis(i - 1, i));
30 res[i][i - 1] = min(res[i][i - 1], res[i - 1][j] + dis(j, i));
31 }
32 for (int i = 1; i < n; i++)
33 {
34 s = dis(i, n);
35 if (Min > res[n][i] + s)
36 Min = res[n][i] + s;
37 }
38 return Min;
39 }
40 int main()
41 {
42 int n;
43 fscanf(fin, "%d", &n);
44 for (int i = 1; i <= n; i++)
45 fscanf(fin, "%lf%lf", &vert[i].x, &vert[i].y);
46 for (int i = 1; i <= n; i++)
47 for (int j = 1; j <= n; j++)
48 res[i][j] = MAX;
49 fprintf(fout, "%.4lf\n", work(n));
50 return 0;
51 }
52
posted on 2012-10-04 11:37
某科学的魂魄妖梦 阅读(186)
评论(0) 编辑 收藏 引用