随笔 - 6  文章 - 1  trackbacks - 0
<2012年10月>
30123456
78910111213
14151617181920
21222324252627
28293031123
45678910

常用链接

留言簿

随笔档案

搜索

  •  

最新评论

阅读排行榜

评论排行榜

老师讲过的……但是忘了好多唉,重新写了一遍
 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(21);
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 某科学的魂魄妖梦 阅读(163) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理