记录编号	2048	评测结果	AAAAA
题目名称	[NOIP 2001]Car的旅行路线	最终得分	100
用户昵称	BYVoid	是否通过	通过
代码语言	C++	运行时间	0.027 s
提交时间	2008-09-11 12:41:25	内存使用	0.27 MiB

#include <iostream>
#include <cmath>
#define MAX 401
using namespace std;

class tqueue
{
public:
	class node
	{
	public:
		int p;
		node *next;
		node(int tp)
		{
			p=tp;next=0;
		}
	};
	node *first,*last;
	int size;
	bool inq[MAX];
	tqueue()
	{
		size=0;
		first=last=0;
		memset(inq,0,sizeof(inq));
	}
	void ins(int p)
	{
		if (first)
			last=last->next=new node(p);
		else
			first=last=new node(p);
		size++;
		inq[p]=true;
	}
	int pop()
	{
		int rtn=first->p;
		inq[rtn]=false;
		node *t=first;
		first=first->next;
		delete t;
		size--;
		return rtn;
	}
};

class edge
{
public:
	int t;
	double v;
	edge* next;
	edge(int tt,double tv)
	{
		t=tt;v=tv;
		next=0;
	}
};

class tadjl
{
public:
	edge *f,*l;
	tadjl(){f=l=0;}
	void ins(int t,double v)
	{
		if (f)
			l=l->next=new edge(t,v);
		else
			f=l=new edge(t,v);
	}
};

typedef struct
{
	int x[4],y[4],cost;
}city;

int N,Price,A,B;
tadjl adjl[MAX];
city cty[101];
double sp[MAX];

void getpoint(int i)
{
	int x1=cty[i].x[1],x2=cty[i].x[2],x0=cty[i].x[0],y1=cty[i].y[1],y2=cty[i].y[2],y0=cty[i].y[0];
	int x3,y3;
	if ((x1-x0)*(x2-x0)+(y1-y0)*(y2-y0)==0)//0直角
	{
		x3=x1+x2-x0;
		y3=y1+y2-y0;
	}
	else if ((x0-x1)*(x2-x1)+(y0-y1)*(y2-y1)==0) //1直角
	{
		x3=x0+x2-x1;
		y3=y0+y2-y1;
	}
	else //2直角
	{
		x3=x0+x1-x2;
		y3=y0+y1-y2;
	}
	cty[i].x[3]=x3;
	cty[i].y[3]=y3;
}

void init()
{
	int i;
	freopen("cardlxlx.in","r",stdin);
	freopen("cardlxlx.out","w",stdout);
	cin >> N >> N >> Price >> A >> B;
	for (i=1;i<=N;i++)
	{
		cin >> cty[i].x[0] >> cty[i].y[0]
			>> cty[i].x[1] >> cty[i].y[1]
			>> cty[i].x[2] >> cty[i].y[2]
			>> cty[i].cost;
		getpoint(i);
	}
}

double dist(int x1,int y1,int x2,int y2)
{
	return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}

void make()
{
	int i,j,k,l;
	double v;
	for (i=1;i<=N;i++) 
	{
		//高速公路
		for (j=0;j<=3;j++)
		{
			for (k=0;k<=3;k++)
			{
				if (j!=k)
				{
					v=dist(cty[i].x[j],cty[i].y[j],cty[i].x[k],cty[i].y[k])*cty[i].cost;
					adjl[(i-1)*4+j].ins((i-1)*4+k,v);
				}
			}
		}
		//飞机航线
		for (j=1;j<=N;j++)
		{
			if (i!=j)
			{
				for (k=0;k<=3;k++)
				{
					for (l=0;l<=3;l++)
					{
						v=dist(cty[i].x[k],cty[i].y[k],cty[j].x[l],cty[j].y[l])*Price;
						adjl[(i-1)*4+k].ins((j-1)*4+l,v);
					}
				}
			}
		}
	}
}

void spfa(int s,double *sp)
{
	tqueue Q;
	int i,j;
	double v;
	edge *k;
	Q.ins(s);
	sp[s]=0;
	while (Q.size)
	{
		i=Q.pop();
		for (k=adjl[i].f;k;k=k->next)
		{
			j=k->t;
			v=k->v;
			if (sp[i]+v<sp[j])
			{
				sp[j]=sp[i]+v;
				if (!Q.inq[j])
					Q.ins(j);
			}
		}
	}
}


double min(double a,double b)
{
	return a<b?a:b;
}

int main()
{
	int i,j;
	double ans=0x7FFFFFFF;
	init();
	make();
	for (i=0;i<=3;i++)
	{
		for (j=0;j<N*4;j++)	sp[j]=0x7FFFFFFF;
		spfa((A-1)*4+i,sp);
		for (j=0;j<=3;j++)
			ans=min(ans,sp[(B-1)*4+j]);
	}
	printf("%.1lf",ans);
	return 0;
}