1 //Accepted    228K    32MS 2 //dp[k][i][j] 表示从1的k号节点到i的j号节点的最小花费 3 //dp[k][i][j]=min(dp[k][i-1][h]+cost) cost为i的j号节点与i-1的h号节点之间的距离 4 //ans=min(dp[k][n][i]+cost) cost 为n的i号节点与1的k号节点之间的距离 5 //事实上，数组的k这一维可以省略 6 #include <cstdio> 7 #include <cstring> 8 #include <cmath> 9 #include <iostream>10 using namespace std;11 const int imax_n = 105;12 const int imax_m = 45;13 const double inf = 100000000.0;14 struct Point15 {16     int x,y;17 }p[imax_n][imax_m];18 int count[imax_n];19 double dp[imax_n][imax_m];20 int n;21 double min(double a,double b)22 {23     if (a-b<1e-9) return a;24     return b;25 }26 double getCost(int i,int x,int j,int y)27 {28     return sqrt((double )((p[i][x].x-p[j][y].x)*(p[i][x].x-p[j][y].x)+(p[i][x].y-p[j][y].y)*(p[i][x].y-p[j][y].y)));29 }30 void Dp()31 {32     double ans=inf;33     for (int k=1;k<=count[1];k++)34     {35         memset(dp,0,sizeof(dp));36         for (int i=1;i<=n;i++)37         for (int j=1;j<=count[i];j++)38         dp[i][j]=inf;39         dp[1][k]=0;40         for (int i=2;i<=n;i++)41         {42             for (int j=1;j<=count[i];j++)43             {44                 //dp[i][j]=inf;45                 for (int h=1;h<=count[i-1];h++)46                 {47                     dp[i][j]=min(dp[i][j],dp[i-1][h]+getCost(i-1,h,i,j));48                 }49             }50         }51         for (int i=1;i<=count[n];i++)52         ans=min(ans,dp[n][i]+getCost(n,i,1,k));53     }54     printf("%d\n",(int )(ans*100));55 }56 int main()57 {58     scanf("%d",&n);59     for (int i=1;i<=n;i++)60     {61         scanf("%d",&count[i]);62         for (int j=1;j<=count[i];j++)63         {64             scanf("%d%d",&p[i][j].x,&p[i][j].y);65         }66     }67     Dp();68     return 0;69 }