比赛 |
noip20081103 |
评测结果 |
WWTTTTTTTA |
题目名称 |
放养奶牛 |
最终得分 |
10 |
用户昵称 |
zqzas |
运行时间 |
0.000 s |
代码语言 |
C++ |
内存使用 |
0.00 MiB |
提交时间 |
2008-11-03 22:07:01 |
显示代码纯文本
#include <iostream>
#include <cmath>
#define MAXN 111
#define INF 99999999
using namespace std;
int n,many[MAXN],pos[MAXN][3],hash[MAXN*2][MAXN*2],data[MAXN][MAXN][3];
double ans;
inline double far(int x1,int y1,int x2,int y2)
{
return sqrt( ((double)(x1-x2))*((double)(x1-x2))+ ((double)(y1-y2))*((double)(y1-y2)) );
}
void dfs(int x,double now)
{
if (x>=n)
{
double zan;
zan=now-far(pos[n-1][0],pos[n-1][1],0,0)+far(pos[n-1][0],pos[n-1][1],pos[0][0],pos[0][1]);
if (zan<ans)
ans=zan;
return;
}
if (now>ans)
return;
int a,b;
for (int i=0;i<many[x+1];i++)
{
a=data[x+1][i][0];
b=data[x+1][i][1];
if (hash[a][b]==0)
{
hash[a][b]=1;
pos[x+1][0]=a;
pos[x+1][1]=b;
dfs(x+1,now+far(pos[x][0],pos[x][1],a,b));
hash[a][b]=0;
pos[x+1][0]=0;
pos[x+1][1]=0;
}
}
}
void run()
{
many[n]=1;
ans=INF;
for (int i=0;i<many[0];i++)
{
pos[0][0]=data[0][i][0];
pos[0][1]=data[0][i][1];
dfs(0,0);
}
}
void ini()
{
cin>>n;
for (int i=0;i<n;i++)
{
cin>>many[i];
for (int j=0;j<many[i];j++)
{
cin>>data[i][j][0]>>data[i][j][1];
data[i][j][0]+=100;
data[i][j][1]+=100;
}
}
}
int main()
{
freopen("cowties.in","r",stdin);
freopen("cowties.out","w",stdout);
ini();
run();
cout<<(int)(ans*100);
return 0;
}