很容易就能看出这是一道最短路的题目，需要先建图，再求解，这道题难点在于建图

---

建图

首先要明确题目含义，每个城市含有四个飞机场，而这四个飞机场能连成一个矩形，但题目中仅给出了三个顶点，需要根据这三个顶点来确定第四个顶点，不妨先假设$(x_1,y_1)$和$(x_3,y_3)$为一组相对的顶点，那么剩下的$(x_2,y_2)$就必然与$(x_4,y_4)$为一组相对的顶点，此时$x_4=x_1+x_3-x_2,y_4=y_1+y_3-y_2$，

那该如何确定哪两个顶点是相对的呢？

先来回顾一下矩形的定义：至少有三个内角都是直角的四边形是矩形，

所以，若$(x_1,y_1)$和$(x_3,y_3)$为一组相对的顶点，由边$(x_1,y_1)$,$(x_2,y_2)$和$(x_2,y_2)$,$(x_3,y_3)$组成的夹角角度应为$90°$，这时候就该请出勾股定理了，定义如下：

如果三角形两条边的平方和等于第三边的平方，那么这个三角形就是直角三角形

所以只需要三个if语句就能判断第四个顶点的位置，代码如下：

if (f(x[i][1],y[i][1],x[i][2],y[i][2])+f(x[i][2],y[i][2],x[i][3],y[i][3])==f(x[i][1],y[i][1],x[i][3],y[i][3])) //(x1,y1),(x3,y3)为对角顶点
    x[i][4]=x[i][1]+x[i][3]-x[i][2],y[i][4]=y[i][1]+y[i][3]-y[i][2];
else if (f(x[i][1],y[i][1],x[i][3],y[i][3])+f(x[i][3],y[i][3],x[i][2],y[i][2])==f(x[i][1],y[i][1],x[i][2],y[i][2])) //(x1,y1),(x2,y2)为对角顶点
    x[i][4]=x[i][1]+x[i][2]-x[i][3],y[i][4]=y[i][1]+y[i][2]-y[i][3];
else    //(x2,y2),(x3,y3)为对角顶点
	x[i][4]=x[i][2]+x[i][3]-x[i][1],y[i][4]=y[i][2]+y[i][3]-y[i][1];

其中f函数为两点距离的平方，
接下来就不说了，就是根据题目描述建边。由于每个城市有四个顶点，第$i$个城市（下标从$0$开始）的第$j$个顶点记为$i*4+j$。

---

求最短路

很容易看出这是一个稠密图，且$S$很小，$4S$最大也才$400$，用$Floyd$虽然简便，但$64000000$有很大风险，这里采用堆优化的$Dijkstra$（其实不用堆优化似乎更好？），入队时把$(a-1)*4+j(1≤j≤4)$加入，一旦找到$(b-1)*4+j(1≤j≤4)$就返回。

---

完整代码

#include<bits/stdc++.h>
#define int long long
using namespace std;

int n,t,a,b,x[105][5],y[105][5];
vector<vector<pair<int,double> > > g(450); //first是顶点，second是距离（边权）
double dist[450];
double d(int x1,int y1,int x2,int y2) //计算距离
{
	return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
int f(int x1,int y1,int x2,int y2) //计算距离的平方
{
	return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
}
struct node
{
	int v;
	double w;
	bool operator < (const node &other) const //默认是大根堆，符号要反过来
	{
		return w>other.w;
	}
};
double dijkstra()
{
	priority_queue<node> q;
	for (int i=1;i<=4;i++) //入队
		q.push({(a<<2)+i,0}),dist[(a<<2)+i]=0;
	while (!q.empty())
	{
		int nv=q.top().v;
		double nw=q.top().w;
		q.pop();
		if (nv==(b<<2)+1 || nv==(b<<2)+2 || nv==(b<<2)+3 || nv==(b<<2)+4) //堆优化，一旦找到就可以返回
			return nw;
		for (auto G:g[nv])
		{
			if (dist[nv]+G.second<dist[G.first]) //松弛操作
			{
				dist[G.first]=dist[nv]+G.second;
				q.push({G.first,dist[G.first]});
			}
		}
	}
}
signed main()
{
	int T;
	cin >> T;
	while (T--)
	{
        g.clear(); //记得初始化
		cin >> n >> t >> a >> b;
		a--,b--; //使下标从0开始
		int w;
		for (int i=0;i<=n;i++)
		{
			for (int j=1;j<=4;j++)
				dist[(i<<2)+j]=1e12; //初始化，double类型不能用memset
		}
		for (int i=0;i<n;i++) //注意下标从0开始
		{
			cin >> x[i][1] >> y[i][1] >> x[i][2] >> y[i][2] >> x[i][3] >> y[i][3] >> w;
			if (f(x[i][1],y[i][1],x[i][2],y[i][2])+f(x[i][2],y[i][2],x[i][3],y[i][3])==f(x[i][1],y[i][1],x[i][3],y[i][3])) //(x1,y1),(x3,y3)为对角顶点
				x[i][4]=x[i][1]+x[i][3]-x[i][2],y[i][4]=y[i][1]+y[i][3]-y[i][2];
			else if (f(x[i][1],y[i][1],x[i][3],y[i][3])+f(x[i][3],y[i][3],x[i][2],y[i][2])==f(x[i][1],y[i][1],x[i][2],y[i][2])) //(x1,y1),(x2,y2)为对角顶点
				x[i][4]=x[i][1]+x[i][2]-x[i][3],y[i][4]=y[i][1]+y[i][2]-y[i][3];
            else    //(x2,y2),(x3,y3)为对角顶点
				x[i][4]=x[i][2]+x[i][3]-x[i][1],y[i][4]=y[i][2]+y[i][3]-y[i][1];
            //用勾股定理确定第四个顶点的坐标
			for (int j=1;j<=4;j++)
            {
                for (int k=j+1;k<=4;k++) //k从j+1开始，避免重复计数或自环。这里是高铁
                {
                	int id1=(i<<2)+j,id2=(i<<2)+k; //计算索引
                    g[id1].push_back({id2,w*1.0*d(x[i][j],y[i][j],x[i][k],y[i][k])});
                    g[id2].push_back({id1,w*1.0*d(x[i][j],y[i][j],x[i][k],y[i][k])});
                }
            }
            for (int j=0;j<i;j++) //航线部分
            {
            	for (int k=1;k<=4;k++)
            	{
            		for (int l=1;l<=4;l++)
            		{
            			int id1=(i<<2)+k,id2=(j<<2)+l; //计算索引
            			g[id1].push_back({id2,t*1.0*d(x[i][k],y[i][k],x[j][l],y[j][l])});
            			g[id2].push_back({id1,t*1.0*d(x[i][k],y[i][k],x[j][l],y[j][l])});
					}
				}
			}
		}
		printf("%.2lf\n",dijkstra());
	}
	return 0;
}