记录编号	121736	评测结果	AAAAA
题目名称	[NOIP 2001]Car的旅行路线	最终得分	100
用户昵称	席一鸣	是否通过	通过
代码语言	C++	运行时间	0.002 s
提交时间	2014-09-21 10:21:40	内存使用	0.34 MiB

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
struct sb
{
	int x,y,c;
}pos[2001];
bool b[201];
double d[101];
int n,tot,costf,st,ed,tc,x[5],y[5],costt[201];
double dis(int x,int y)
{
	double k;
	k=sqrt(pow(pos[x].x-pos[y].x,2)+pow(pos[x].y-pos[y].y,2));
	if(pos[x].c==pos[y].c)
	  k*=costt[pos[x].c];
	else
	  k*=costf;
	return k;
}
double dij(int st)
{
	double min,k;
	int i,j,p;
	memset(b,0,sizeof(b));
	memset(d,100,sizeof(d));
	d[st]=0;
	for(i=1;i<=tot;i++)
	{
		min=1e38;
		for(j=1;j<=tot;j++)
		  if(!b[j]&&d[j]<min)
		  {
		  	min=d[j];
		  	p=j;
		  }
		b[p]=1;
		for(j=1;j<=tot;j++)
		  if(!b[j])
		    d[j]=d[j]>d[p]+dis(p,j)?d[p]+dis(p,j):d[j];
	}
	k=1e38;
	for(i=1;i<=tot;i++)
	{
		if(pos[i].c==ed)
		  for(j=0;j<=3;j++)
		    k=d[i+j]<k?d[i+j]:k;
		if(pos[i].c==ed)
		  break;
	}
	return k;
}
main()
{
	freopen("cardlxlx.in","r",stdin);
	freopen("cardlxlx.out","w",stdout);
	cin>>tc;
	double min=1e38;
	int i,j,k;
	while(tc)
	{
		cin>>n>>costf>>st>>ed;
		for(i=1;i<=n;i++)
		{
			cin>>x[1]>>y[1]>>x[2]>>y[2]>>x[3]>>y[3]>>costt[i];
			for(j=1;j<=3;j++)
			  for(k=1;k<=3;k++)
			    if(j!=k&&(x[j]-x[k])*(x[6-k-j]-x[j])+(y[j]-y[k])*(y[6-k-j]-y[j])==0)
			    {
			    	x[4]=x[k]+x[6-k-j]-x[j];
			    	y[4]=y[k]+y[6-k-j]-y[j];
			    }
			for(j=1;j<=4;j++)
			{
				pos[++tot].x=x[j];
				pos[tot].y=y[j];
				pos[tot].c=i;
			}
		}
		for(i=1;i<=tot;i++)
		{
			if(pos[i].c==st)
			  for(j=0;j<=3;j++)
			    min=dij(i+j)<min?dij(i+j):min;
			if(pos[i].c==st)
			  break;
		}
		printf("%.1lf",min);
		tc--;
	}
	fclose(stdin);
	fclose(stdout);
}