记录编号	192462	评测结果	AAAAA
题目名称	[NOIP 2001]Car的旅行路线	最终得分	100
用户昵称	forever	是否通过	通过
代码语言	C++	运行时间	0.011 s
提交时间	2015-10-11 07:27:28	内存使用	4.19 MiB

#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
struct dd{
	int end,next;
	double juli;
}jie[250000];
struct dt{
	int x[6]; int y[6];
}at[56];
int tot,head[5000],rt[25][6],num,mo[60],s,t,A,B,T;
double dis[5000];
bool vis[5000];
double Get_dis(int xi,int yi,int xa,int xb){
	return sqrt((at[xi].x[xa]-at[yi].x[xb])*(at[xi].x[xa]-at[yi].x[xb])+(at[xi].y[xa]-at[yi].y[xb])*(at[xi].y[xa]-at[yi].y[xb]));
}
double Get_diss(int xi,int yi,int er){
	return sqrt((at[xi].x[yi]-at[xi].x[er])*(at[xi].x[yi]-at[xi].x[er])+(at[xi].y[yi]-at[xi].y[er])*(at[xi].y[yi]-at[xi].y[er]));
}
void add(int x,int y,double z){
	jie[++tot].end=y; jie[tot].juli=z; jie[tot].next=head[x]; head[x]=tot;
}
void Get_line1(){
	for(int i=1;i<=s;++i)
	  for(int hi=1;hi<=4;++hi)
		for(int j=1;j<=s;++j)
		 for(int hj=1;hj<=4;++hj){
			if(i==j) continue;
			double ty=Get_dis(i,j,hi,hj);
			add(rt[i][hi],rt[j][hj],t*ty);
			add(rt[j][hj],rt[i][hi],t*ty);
		 }

}
void Get_line2(){
	for(int i=1;i<=s;++i)
	 for(int j=1;j<=4;++j)
	   for(int k=1;k<=4;++k){
		if(j==k) continue;
		double ty=Get_diss(i,j,k);
		add(rt[i][j],rt[i][k],mo[i]*ty);
		add(rt[i][k],rt[i][j],mo[i]*ty);
	 }
}
void spfa(int x){
	queue<int>que;
	for(int i=1;i<=num;++i){
		dis[i]=99999999.00; vis[i]=0;
	}
	dis[x]=0.00; vis[x]=1;
	que.push(x);
	while(!que.empty()){
		int yu=que.front(); que.pop(); vis[yu]=0;
		for(int i=head[yu];i;i=jie[i].next){
			int lin=jie[i].end;
			if(dis[lin]>dis[yu]+jie[i].juli){
				dis[lin]=dis[yu]+jie[i].juli;
				if(!vis[lin]){
					vis[lin]=1;
					que.push(lin);
				}
			}
		}
	}
}
void Work(){
	double Minn=9999999.00;
	for(int i=1;i<=4;++i){
		spfa(rt[A][i]);
		for(int j=1;j<=4;++j){
			if(dis[rt[B][j]]<Minn) Minn=dis[rt[B][j]];
		}
	}
	printf("%.1lf\n",Minn);
}
int main(){
    freopen("cardlxlx.in","r",stdin);
	freopen("cardlxlx.out","w",stdout);
	scanf("%d",&T);
  	for(int op=1;op<=T;++op){
	   num=0;
	   scanf("%d%d%d%d",&s,&t,&A,&B);
	   for(int i=1;i<=s;++i){
		  scanf("%d%d%d%d%d%d%d",&at[i].x[1],&at[i].y[1],&at[i].x[2],&at[i].y[2],&at[i].x[3],&at[i].y[3],&mo[i]);
		  for(int j=1;j<=3;j++)
			  for(int k=1;k<=3;k++)
			    if(j!=k&&(at[i].x[j]-at[i].x[k])*(at[i].x[6-k-j]-at[i].x[j])+(at[i].y[j]-at[i].y[k])*(at[i].y[6-k-j]-at[i].y[j])==0)
			    {
			    	at[i].x[4]=at[i].x[k]+at[i].x[6-k-j]-at[i].x[j];
			    	at[i].y[4]=at[i].y[k]+at[i].y[6-k-j]-at[i].y[j];
			    }
	   }
	   for(int i=1;i<=s;++i)
		for(int j=1;j<=4;++j)
		  rt[i][j]=num++;
	   Get_line1(); Get_line2();
	   Work();
	}
	getchar(); getchar();
}