比赛 |
noip20081103 |
评测结果 |
AAWWWWWWWA |
题目名称 |
放养奶牛 |
最终得分 |
30 |
用户昵称 |
BYVoid |
运行时间 |
0.000 s |
代码语言 |
C++ |
内存使用 |
0.00 MiB |
提交时间 |
2008-11-03 20:54:40 |
显示代码纯文本
#include <iostream>
#include <cmath>
using namespace std;
const int MAX=101;
const int MAXS=41;
const double INF=1e10;
class list
{
public:
list *next;
int p;
double v;
list(int tp,double tv):p(tp),v(tv)
{
next=0;
}
};
class tAdjl
{
public:
list *first,*last;
void ins(int p,double v)
{
if (first)
last=last->next=new list(p,v);
else
first=last=new list(p,v);
}
tAdjl()
{
first=last=0;
}
};
template <typename T> class tQueue
{
private:
class tqlist
{
public:
tqlist *next;
T value;
tqlist(T tv):value(tv)
{
next=0;
}
};
tqlist *first,*last;
public:
int size;
void ins(T value)
{
if (first)
last=last->next=new tqlist(value);
else
first=last=new tqlist(value);
size++;
}
T pop()
{
size--;
T rtn=first->value;
tqlist *tp=first;
first=first->next;
delete tp;
return rtn;
}
tQueue()
{
first=last=0;
size=0;
}
};
struct point
{
int x,y,id;
};
int N,U;
point P[MAX][MAXS];
int pcnt[MAX];
tQueue<int> Q;
tAdjl adjl[MAX*MAXS];
bool inq[MAX*MAXS];
double sp[MAX*MAXS];
double S;
point *IP[MAX*MAXS];
inline double dist(const point &a,const point &b)
{
return sqrt((double)(a.x-b.x)*(double)(a.x-b.x)+(double)(a.y-b.y)*(double)(a.y-b.y));
}
void init()
{
int i,j,k,x,y,a,b,idcnt=0;
double v;
freopen("cowties.in","r",stdin);
freopen("cowties.out","w",stdout);
scanf("%d",&N);
for (i=1;i<=N;i++)
{
scanf("%d",&pcnt[i]);
for (j=1;j<=pcnt[i];j++)
{
scanf("%d%d",&x,&y);
P[i][j].x=x;
P[i][j].y=y;
P[i][j].id=++idcnt;
}
}
for (k=1;k<=N-1;k++)
{
for (i=1;i<=pcnt[k];i++)
{
a=P[k][i].id;
for (j=1;j<=pcnt[k+1];j++)
{
b=P[k+1][j].id;
v=dist(P[k][i],P[k+1][j]);
if ((int)v==0)
continue;
adjl[a].ins(b,v);
adjl[b].ins(a,v);
}
}
}
for (i=1;i<=pcnt[1];i++)
{
a=0;
b=P[1][i].id;
adjl[a].ins(b,0);
}
for (i=1;i<=pcnt[N];i++)
{
a=P[N][i].id;
U=b=idcnt+1;
adjl[a].ins(b,0);
}
for (i=0;i<=U;i++)
{
sp[i]=INF;
}
}
void spfa()
{
int i,j;
double v;
list *k;
sp[0]=0;
Q.ins(0);
while (Q.size)
{
i=Q.pop();
inq[i]=false;
for (k=adjl[i].first;k;k=k->next)
{
j=k->p;
v=k->v;
if (sp[i]+v<sp[j])
{
sp[j]=sp[i]+v;
if (!inq[j])
{
inq[j]=true;
Q.ins(j);
}
}
}
}
S=sp[U];
}
void solve()
{
int i,j;
double v,minv=INF;
for (i=1;i<=pcnt[N];i++)
{
for (j=1;j<=pcnt[1];j++)
{
v=dist(P[N][i],P[1][j]);
if ((int)v!=0 && v<minv)
minv=v;
}
}
S+=minv;
S*=100;
S=floor(S);
}
int main()
{
init();
spfa();
solve();
printf("%.0lf\n",S);
return 0;
}