原题链接

将每个城市拆成四个点，即四个机场来看，那么这题就是求最短路。

不过建图有些麻烦，先要找出第四个机场的坐标。

设另外三个机场的坐标为\((x_1, y_1), (x_2, y_2), (x_3, y_3)\)，其中\((x_1, y_1), (x_3, y_3)\)为对角线两点。



那么第四个点的坐标即为\((x_1 + x_3 - x_2, y_1 + y_3 - y_2)\)。

这个是通过对角线交点为中点，坐标为线段两端点坐标和的一半算得。当然可以用勾股等方法算。

至于找出对角线的两端点，则可以计算原本三点两两之间的长度，那么最长的就是对角线了。当然用勾股也可以判。

然后就之间跑最短路即可。

这里我用的是\(dijkstra\)。

#include<cstdio>

#include<cmath>

#include<cstring>

#include<queue>

using namespace std;

const int N = 110;

const int M = 410;

const int K = M * M;

struct dd {

	int x;

	double D;

	bool operator < (const dd &b) const { return D > b.D; }

};

struct poi {

	int x[5], y[5], po[5], z;

};

poi a[N];

int fi[M], ne[K], di[K], st, ed, m, l;

double dis[M], da[K];

bool v[M];

priority_queue<dd>q;

inline int re()

{

	int x = 0;

	char c = getchar();

	bool p = 0;

	for (; c < '0' || c > '9'; c = getchar())

		p |= c == '-';

	for (; c >= '0' && c <= '9'; c = getchar())

		x = x * 10 + c - '0';

	return p ? -x : x;

}

inline double minn(double x, double y) { return x < y ? x : y; }

inline void add(int x, int y, double z)

{

	di[++l] = y; da[l] = z; ne[l] = fi[x]; fi[x] = l;

	di[++l] = x; da[l] = z; ne[l] = fi[y]; fi[y] = l;

}

inline double calc(int x, int y, int xx, int yy, int z) { return sqrt(1.0 * (x - xx) * (x - xx) + 1.0 * (y - yy) * (y - yy)) * z; }//计算边的花费

inline int fin(int k)//找对角线，顺便添入部分铁路

{

	int i, j, L = 0, id;

	double D[4], ma = 0;

	for (i = 1; i < 3; i++)

		for (j = i + 1; j < 4; j++)

		{

			D[++L] = calc(a[k].x[i], a[k].y[i], a[k].x[j], a[k].y[j], a[k].z);

			add(a[k].po[i], a[k].po[j], D[L]);

			if (ma < D[L])

				ma = D[L], id = L;

		}

	return id ^ 1 ? id ^ 2 ? 1 : 2 : 3;

}

inline void addp(int x, int y)//将两两城市之间的航道建好

{

	for (int i = 1; i < 5; i++)

		for (int j = 1; j < 5; j++)

			add(a[x].po[i], a[y].po[j], calc(a[x].x[i], a[x].y[i], a[y].x[j], a[y].y[j], m));

}

double dij()//dijkstra

{

	int i, x, y;

	memset(dis, 66, sizeof(dis));

	memset(v, 0, sizeof(v));

	for (i = 1; i <= 4; i++)//因为可以从这个城市的任意一个机场出发，所以全部丢进去。

		q.push({ a[st].po[i], 0.0 }), dis[a[st].po[i]] = 0;//不知道为什么如果我前面加上结构体类型，VS就不能编译，用C++11的特性才行

	while (!q.empty())

	{

		x = q.top().x;

		q.pop();

		if (v[x])

			continue;

		v[x] = 1;

		for (i = fi[x]; i; i = ne[i])

			if (dis[y = di[i]] > dis[x] + da[i])

			{

				dis[y] = dis[x] + da[i];

				q.push({ y, dis[y] });

			}

	}

	double mi = 1e9;

	for (i = 1; i < 5; i++)

		mi = minn(mi, dis[a[ed].po[i]]);//取min

	return mi;

}

int main()

{

	int i, j, t, n, p;

	t = re();

	while (t--)

	{

		memset(fi, 0, sizeof(fi));

		n = re(); m = re(); st = re(); ed = re();

		l = p = 0;

		for (i = 1; i <= n; i++)

		{

			for (j = 1; j < 4; j++)

				a[i].x[j] = re(), a[i].y[j] = re(), a[i].po[j] = ++p;

			a[i].z = re();

			int k = fin(i);

			a[i].x[4] = a[i].x[1] + a[i].x[2] + a[i].x[3] - (a[i].x[k] << 1);//计算第四个点的坐标

			a[i].y[4] = a[i].y[1] + a[i].y[2] + a[i].y[3] - (a[i].y[k] << 1);

			a[i].po[4] = ++p;

			for (j = 1; j < 4; j++)

				add(a[i].po[4], a[i].po[j], calc(a[i].x[4], a[i].y[4], a[i].x[j], a[i].y[j], a[i].z));

		}

		for (i = 1; i < n; i++)

			for (j = i + 1; j <= n; j++)

				addp(i, j);

		printf("%.1f\n", dij());

	}

	return 0;

}