bnu14288Cowties

昨天练习一道题.题意大概是.有n头牛,需要按次序连接成一个环(1连2,2连3....,).每头牛都有几个可选坐标.求怎样连可以使连接的线最短.

思路:dp的思想.cow[i].dis[j]表示第i头牛的第j个坐标到第一头牛的第t个坐标的最短距离由于要连成环,所以cow[0].dis[t]里就是这个环的最短距离 .枚举一下第一头牛的坐标.就可以得到结果.

最后的结果要取整.第一次就是因为不是取整的.WA了

#include<stdio.h>
#include<string.h>
#include<math.h>

typedef struct dd
{
    int x[45];
    int y[45];
    int n;
    double dis[45];
}DD;

DD cow[110];
double dis2(int i,int j,int k);
double work(int i);
void init();
int s;
int main()
{
    while(scanf("%d",&s)!=EOF)
    {
        double tt1,min;
        for(int i=0;i<s;i++)
        {
            scanf("%d",&cow[i].n);
            for(int j=0;j<cow[i].n;j++)
            {
                scanf("%d%d",&cow[i].x[j],&cow[i].y[j]);
            }
        }
        min=10000000;
        for(int i=0;i<cow[0].n;i++)
        {
            init();
            tt1=work(i);
            min=min<tt1?min:tt1;
        }
        printf("%d\n",(int)(min *100));
    }
    return 0;
}
double work(int t)
{
    int i,j,k,n;
    double tmin;
    if(s<2) return 0;
    for(i=0;i<cow[1].n;i++)
        cow[1].dis[i]=dis2(t,i,1);
    for(n=2;n<s;n++)//cow
    {
        for(i=0;i<cow[n].n;i++) //nth cow pos
        {
            for(j=0;j<cow[n-1].n;j++) //n-1th cow pos
            {
                double tt2=dis2(j,i,n);
                if(tt2+cow[n-1].dis[j]<cow[n].dis[i])
                {
                    cow[n].dis[i]=tt2+cow[n-1].dis[j];
                    ///                 printf("%.0lf n=%d n=%d  n-1=%d\n",tt2*100,n,i,j);
                }
            }
        }
    }
    j=s-1;
    tmin=10000000;
    for(i=0;i<cow[j].n;i++)
    {
        double tt2=dis2(i,t,0);
        if(tt2+cow[j].dis[i]<tmin)
            tmin=tt2+cow[j].dis[i];
    }
    return tmin;
}
double dis2(int i,int j,int k)
{
    double x,y,sum;
    int n=(k-1+s)%s;
    x=cow[n].x[i]-cow[k].x[j];
    y=cow[n].y[i]-cow[k].y[j];
    return sqrt(x*x+y*y);
}
void init()
{
    for(int i=1;i<s;i++)
        for(int j=0;j<cow[i].n;j++)
            cow[i].dis[j]=10000000;
}