比赛 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;
}