记录编号	461511	评测结果	AAAAA
题目名称	[NOIP 2001]Car的旅行路线	最终得分	100
用户昵称	nfy_2002	是否通过	通过
代码语言	C++	运行时间	0.022 s
提交时间	2017-10-19 22:49:13	内存使用	8.88 MiB

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#define RG register
#define IL inline
#define pi acos(-1.0)
#define ll long long
#define eps 0.0000001
using namespace std;

struct point{
  int x,y;
};
point c[1000];
int tot=0,num=0;
int n,s,T,A,B,zhong;
struct data{
  int first,nxt,to;
  double w;
};
data a[300005];
double DIS[500];
bool pan[500];

IL void add(int l,int r,double w){
  a[++num].to=r;
  a[num].nxt=a[l].first;
  a[l].first=num;
  a[num].w=w;
}

IL double cal(int aa,int bb){
  return sqrt((c[aa].x*1.0-c[bb].x*1.0)*(c[aa].x*1.0-c[bb].x*1.0)+(c[aa].y*1.0-c[bb].y*1.0)*(c[aa].y*1.0-c[bb].y*1.0));
}

IL void spfa(){
  for(int i=0;i<=tot+1;i++)
    DIS[i]=999999999.0;
  memset(pan,true,sizeof(pan));
  DIS[0]=0,pan[0]=false;
  RG queue <int> S;
  S.push(0);
  while(!S.empty()){
    RG int u=S.front();
    S.pop();
    pan[u]=true;
    for(RG int i=a[u].first;i;i=a[i].nxt){
      RG int v=a[i].to;
      if(DIS[v]>DIS[u]+a[i].w){
	DIS[v]=DIS[u]+a[i].w;
	if(pan[v]){
	  pan[v]=false;
	  S.push(v);
	}
      }
    }
  }
}

int main(){
    freopen("cardlxlx.in","r",stdin);
    freopen("cardlxlx.out","w",stdout);
    scanf("%d",&n);
    while(n--){
      scanf("%d%d%d%d",&s,&T,&A,&B);
      tot=0;
      zhong=s*4+1;
      memset(a,0,sizeof(a));
      for(int qq=1;qq<=s;qq++){
	RG int x1,y1,x2,y2,x3,y3,x4,y4,t;
	scanf("%d%d%d%d%d%d%d",&x1,&y1,&x2,&y2,&x3,&y3,&t);
	c[++tot]=(point){x1,y1},c[++tot]=(point){x2,y2},c[++tot]=(point){x3,y3};
	RG double p1=cal(tot-2,tot-1),p2=cal(tot-2,tot),p3=cal(tot-1,tot);
	if((p1*p1+p2*p2)-(p3*p3)<=eps){
	  RG double xx=(c[tot-1].x+c[tot].x)*1.0/2*1.0,yy=(c[tot-1].y+c[tot].y)*1.0/2*1.0;
	  x4=2*xx-c[tot-2].x,y4=2*yy-c[tot-2].y;
	} else if((p1*p1+p3*p3)-(p2*p2)<=eps){
	  RG double xx=(c[tot-2].x+c[tot].x)*1.0/2*1.0,yy=(c[tot-2].y+c[tot].y)*1.0/2*1.0;
	  x4=2*xx-c[tot-1].x,y4=2*yy-c[tot-1].y;
	} else if((p2*p2+p3*p3)-(p1*p1)<=eps){
	  RG double xx=(c[tot-1].x+c[tot-2].x)*1.0/2*1.0,yy=(c[tot-1].y+c[tot-2].y)*1.0/2*1.0;
	  x4=2*xx-c[tot].x,y4=2*yy-c[tot].y;
	}
	c[++tot]=(point){x4,y4};
	for(RG int i=tot-3;i<=tot;i++)
	  for(RG int j=i+1;j<=tot;j++){
	    RG double dis=cal(i,j);
	    add(i,j,dis*t),add(j,i,dis*t);
	  }
	if(qq==A)
	   for(int ii=tot-3;ii<=tot;ii++)
	     add(0,ii,0);
	if(qq==B)
	   for(int ii=tot-3;ii<=tot;ii++)
	     add(ii,zhong,0);
      }
      for(int i=1;i<=s;i++){
	int kk=(i-1)*4;
	for(RG int j=kk+1;j<=kk+4;j++)
	  for(RG int k=kk+5;k<=tot;k++){
	    RG double dis=cal(j,k);
	    add(j,k,dis*T),add(k,j,dis*T);
	  }
      }
      spfa();
      printf("%.1lf\n",DIS[zhong]);
    }
    return 0;
}