#include<bits/stdc++.h>
using namespace std;
#define N 109
#define M 2600009
#define INF 0x3f3f3f3f
#define mem(a,b) memset(a,b,sizeof a)
#define PII pair<double,double>
#define PII2 pair<double ,int>
int e[M],ne[M],h[M],idx,cnt;
double w[M];
map<PII,int> mp;
const double eps = 1e-6;
double dist[M];
bool st[M];
double s,t,A,B; //城市个数 ，飞机单位历程价格
//A,B分别表示城市A B的序号
int s1,e1;
struct node
{
double x[6],y[6],T;
}city[N];
void add(int x,int y,double z)
{
e[idx] = y;
w[idx] = z;
ne[idx] = h[x];
h[x] = idx++;
}
void Dijstra(int x)
{
for(int i=1; i<=M; i++) dist[i] = DBL_MAX;
mem(st,false);
dist[x] = 0;
priority_queue<PII2,vector<PII2> ,greater<PII2> > heap;
heap.push({0,x});
while(heap.size())
{
PII2 tmp = heap.top();
heap.pop();
double d= tmp.first;
int p = tmp.second;
if(st[p]) continue;
st[p] = true;
for(int i=h[p]; i!=-1; i=ne[i])
{
int j = e[i];
if(dist[j] > d+w[i])
{
dist[j] = d+w[i];
heap.push({dist[j],j});
}
}
}
}
double Dist(double x1,double y1,double x2,double y2)
{
return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
int main()
{
int n;
cin>>n;
while(n--)
{
mp.clear();
//cout<<mp.size()<<" mp"<<endl;
mem(h,-1);
mem(e,0);
mem(ne,0);
mem(w,0);
idx=0;
s1=e1=cnt=0;
cin>>s>>t>>A>>B;
for(int i=1; i<=s; i++)
{
for(int j=1; j<=3; j++)
{
cin>>city[i].x[j]>>city[i].y[j];
if(!mp[{city[i].x[j],city[i].y[j]}])
mp[{city[i].x[j],city[i].y[j]}] = ++cnt;
if(i==A&&!s1) s1=cnt;
if(i==B&&!e1) e1 = cnt;
// if(i==A) cout<<cnt<<" ";
// if(i==B) cout<<cnt<<" ";
// cout<<cnt<<" ";
}
//cout<<endl;
cin>>city[i].T;
double x1 = city[i].x[1],y1 =city[i].y[1],x2 =city[i].x[2],y2 = city[i].y[2];
double x3 =city[i].x[3],y3 = city[i].y[3],x4,y4;
double a = Dist(x1,y1 ,x2,y2);
double b = Dist(x2,y2, x3,y3);
double c = Dist(x3,y3, x1,y1);
if(a*a+b*b-c*c<eps) {
city[i].x[4]=x4 = x1+x3-x2;
city[i].y[4] = y4 = y1+y3-y2;
if(!mp[{x4,y4}]) mp[{x4,y4}] = ++cnt;
add(mp[{x1,y1}],mp[{x2,y2}],a*city[i].T);
add(mp[{x2,y2}],mp[{x1,y1}],a*city[i].T);
add(mp[{x2,y2}],mp[{x3,y3}],b*city[i].T);
add(mp[{x3,y3}],mp[{x2,y2}],b*city[i].T);
add(mp[{x1,y1}],mp[{x4,y4}],b*city[i].T);
add(mp[{x4,y4}],mp[{x1,y1}],b*city[i].T);
add(mp[{x4,y4}],mp[{x3,y3}],a*city[i].T);
add(mp[{x3,y3}],mp[{x4,y4}],a*city[i].T);
}
if(a*a+c*c-b*b<eps) {
city[i].x[4]=x4 = x2+x3-x1;
city[i].y[4] = y4=y2+y3-y1;
if(!mp[{x4,y4}]) mp[{x4,y4}] = ++cnt;
add(mp[{x1,y1}],mp[{x2,y2}],a*city[i].T);
add(mp[{x2,y2}],mp[{x1,y1}],a*city[i].T);
add(mp[{x3,y3}],mp[{x4,y4}],a*city[i].T);
add(mp[{x4,y4}],mp[{x3,y3}],a*city[i].T);
add(mp[{x1,y1}],mp[{x3,y3}],c*city[i].T);
add(mp[{x3,y3}],mp[{x1,y1}],c*city[i].T);
add(mp[{x2,y2}],mp[{x4,y4}],c*city[i].T);
add(mp[{x4,y4}],mp[{x2,y2}],c*city[i].T);
}
if(b*b+c*c-a*a<eps) {
city[i].x[4]=x4= x1+x2-x3;
city[i].y[4] =y4=y1+y2-y3;
if(!mp[{x4,y4}]) mp[{x4,y4}] = ++cnt;
add(mp[{x1,y1}],mp[{x4,y4}],b*city[i].T);
add(mp[{x4,y4}],mp[{x1,y1}],b*city[i].T);
add(mp[{x3,y3}],mp[{x2,y2}],b*city[i].T);
add(mp[{x2,y2}],mp[{x3,y3}],b*city[i].T);
add(mp[{x1,y1}],mp[{x3,y3}],c*city[i].T);
add(mp[{x3,y3}],mp[{x1,y1}],c*city[i].T);
add(mp[{x2,y2}],mp[{x4,y4}],c*city[i].T);
add(mp[{x4,y4}],mp[{x2,y2}],c*city[i].T);
}
}
//各个城市之间的机场路线建图
for(int i=1; i<=s; i++)
{
for(int j=i+1; j<=s; j++)
{
for(int k=1 ;k<=4; k++)
{
for(int l=1; l<=4; l++)
{
int u = mp[{city[i].x[k],city[i].y[k]}];
int v = mp[{city[j].x[l],city[j].y[l]}];
double d = t*Dist(city[i].x[k],city[i].y[k],city[j].x[l],city[j].y[l]);
//cout<<u<<" "<<v<<" "<<d<<endl;
add(u,v,d);
add(v,u,d);
}
}
}
}
//cout<<s1<<" "<<e1<<endl;
double ans = DBL_MAX;
for(int i=s1; i<=s1+3; i++)
{
Dijstra(i);
for(int j=e1; j<=e1+3; j++)
{
//cout<<i<<" "<<j<<endl;
ans = min(ans,dist[j]);
}
}
printf("%.1f\n",ans);
}
return 0;
} 
查看13道真题和解析