双调欧几里得旅行商问题

 1 //双调欧几里得旅行商问题  
 2 
 3 //PKU 2677  
 4 #include<stdio.h>
 5 #include<math.h>
 6 #include<stdlib.h>
 7 #define R 1001
 8  int dis(int i,int j);
 9 void shortway( int **b,int N);
10 struct Node
11 {
12     int x;
13     int y;
14 }a[1001];
15 int main(void)
16 {
17     int M,N,i,j,k;
18      int **b;
19      int s[R]={0};
20     a[0].x=0;a[0].y=0;
21     scanf("%d",&M);
22     for(i=0;i<M;i++)
23     {
24         scanf("%d",&N);
25 //二级指针开辟一个二维数组
26         b=(int**)malloc((N+1)*sizeof(int));//b是指向指针的指针
27         for(j=0;j<N+1;j++)
28             b[j]=(int*)malloc((N+1)*sizeof(int));//b[j]是指针
29 //
30         for(j=0;j<N+1;j++)
31             for(k=0;k<N+1;k++)
32                 b[j][k]=0;
33 
34         for(j=1;j<=N;j++)
35         {
36             scanf("%d%d",&a[j].x,&a[j].y);
37         }
38         shortway(b,N);
39         s[i]=b[N][N]+N*10;
40         free(b);
41     }
42     for(i=0;i<M;i++)
43         printf("%d\n",s[i]);
44 
45     return 0;    
46 }
47 int dis(int i,int j)
48 {
49     int m,m1,m2;
50     m1=abs(a[i].x-a[j].x)*400;
51     m2=abs(a[i].y-a[j].y);
52     m2=m2>(360-m2)?(360-m2):m2;
53     return m=m1+m2;    
54 }
55 void shortway(int **b,int N)
56 {
57     int i,j,k;
58     int num;
59     b[0][0]=0;
60     for(i=1;i<=N;i++)
61         for(j=0;j<=i;j++)
62         {
63             if(i==j)
64                 b[i][j]=b[i][j-1]+dis(i,j-1);
65             if(i>j+1)
66                 b[i][j]=b[i-1][j]+dis(i-1,i);
67             if(i==j+1)
68             {
69             
70                 b[i][j]=(int)pow(2,30);//??
71                 if(j==0)
72                     b[i][j]=b[0][0]+dis(1,0);
73                 for(k=0;k<j;k++)
74                 {
75                     num=b[k][j]+dis(k,i);
76                         //printf("%d,%d,%d\n",b[k][j],dis(k,i),num);
77                     if(b[i][j]>num)
78                         b[i][j]=num;
79                 }
80             }
81             b[j][i]=b[i][j];
82         }
83 }