一种很显然的做法，注意到数据规模 $S\le 100$，在一座城市中最多有 $4$ 种不同的状态（矩形的四个顶点）。

考虑拆点，拆点后最多只有 $400$ 个点，考虑用邻接表、floyd 算法解决此题。

但是由于题目只给出了矩形的三个顶点的坐标，第四个顶点应该自己计算。

假设第一个点是 $A(x_1,y_1)$，第二个点是 $B(x_2,y_2)$，第三个点是 $C(x_3,y_3)$，第三个点是 $D(x_4,y_4)$。

有如下三种情况：

• $A{B}^2+A{C}^2=B{C}^2$，此时 $x_4=x_2+x_3-x_1$，$y_4=y_2+y_3-y_1$，$D(-x_1+x_2+x_3,-y_1+y_2+y_3)$。

  不难证明，因为 $AB$，$AC$ 是直角边，因此 $\mathbf{AB}=\mathbf{CD}$，由于 $\mathbf{AB}=(x_2-x_1,y_2-y_1)$，$C(x_3,x_4)$，所以 $D=C+\mathbf{AB}$。

• 同理，$A{B}^2+B{C}^2=A{C}^2$ 时，$D(x_1-x_2+x_3,y_1-y_2+y_3)$

• $A{C}^2+B{C}^2=A{B}^2$ 时，$D(x_1+x_2-x_3,y_1+y_2-y_3)$

剩下的很显然，计算同一个矩形中两点间的“高速公路”的边权并记录，计算不同矩形的两点间的“航线”的边权并记录，跑 floyd 即可，最后枚举起点与终点的状态。时间复杂度：拆点 $O(T\ast S)$，建边 $O(T\ast S^2)$，floyd$O(T\ast S^3)$，总复杂度 $O(T\ast S^3)$。

代码

#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;

// 快速读入整数的函数
inline int read() {
    int f = 1, x = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

typedef long long ll;
const ll INF = 0x7f7f7f7f; // 用于表示无穷大
const int N = 410;         // 最大点数

// 变量定义
ll s, A, B, T; // s: 矩形数量, A 和 B: 起点和终点矩形编号, T: 测试用例数量
double ans, t, dis[N][N]; // ans: 最终答案, t: 普通路径的权重, dis: 距离矩阵
double x[N], y[N], w[110]; // x, y: 点的坐标, w: 矩形的权重

// 计算两点之间的欧几里得距离
double getDistance(double x1, double y1, double x2, double y2) {
    return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}

// 计算两点之间的平方距离（避免开方，提高效率）
double squaredDistance(double x1, double y1, double x2, double y2) {
    return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
}

int main() {
    T = read(); // 读取测试用例数量
    while (T--) {
        memset(dis, 0, sizeof(dis)); // 初始化距离矩阵为0
        ans = INF;                   // 初始化答案为无穷大

        // 读取输入数据
        s = read(); // 矩形数量
        t = read(); // 普通路径的权重
        A = read(); // 起点矩形编号
        B = read(); // 终点矩形编号

        // 输入每个矩形的四个点和权重
        for (int i = 1; i <= s; i++) {
            // 读取矩形的三个点的坐标
            x[(i - 1) * 4 + 1] = read();
            y[(i - 1) * 4 + 1] = read();
            x[(i - 1) * 4 + 2] = read();
            y[(i - 1) * 4 + 2] = read();
            x[(i - 1) * 4 + 3] = read();
            y[(i - 1) * 4 + 3] = read();
            w[i] = read(); // 读取矩形的权重

            // 计算三个边的平方距离
            double disAB = squaredDistance(x[(i - 1) * 4 + 1], y[(i - 1) * 4 + 1],
                                           x[(i - 1) * 4 + 2], y[(i - 1) * 4 + 2]);
            double disAC = squaredDistance(x[(i - 1) * 4 + 1], y[(i - 1) * 4 + 1],
                                           x[(i - 1) * 4 + 3], y[(i - 1) * 4 + 3]);
            double disBC = squaredDistance(x[(i - 1) * 4 + 2], y[(i - 1) * 4 + 2],
                                           x[(i - 1) * 4 + 3], y[(i - 1) * 4 + 3]);

            // 根据三个边的关系计算第四个点的坐标
            if (disAB + disAC == disBC) {
                x[i * 4] = x[(i - 1) * 4 + 2] + x[(i - 1) * 4 + 3] - x[(i - 1) * 4 + 1];
                y[i * 4] = y[(i - 1) * 4 + 2] + y[(i - 1) * 4 + 3] - y[(i - 1) * 4 + 1];
            } else if (disAB + disBC == disAC) {
                x[i * 4] = x[(i - 1) * 4 + 1] + x[(i - 1) * 4 + 3] - x[(i - 1) * 4 + 2];
                y[i * 4] = y[(i - 1) * 4 + 1] + y[(i - 1) * 4 + 3] - y[(i - 1) * 4 + 2];
            } else if (disBC + disAC == disAB) {
                x[i * 4] = x[(i - 1) * 4 + 2] + x[(i - 1) * 4 + 1] - x[(i - 1) * 4 + 3];
                y[i * 4] = y[(i - 1) * 4 + 2] + y[(i - 1) * 4 + 1] - y[(i - 1) * 4 + 3];
            }
        }

        // 初始化距离矩阵
        for (int i = 1; i <= s * 4; i++) {
            for (int j = 1; j <= s * 4; j++) {
                if (i != j) {
                    if ((i - 1) / 4 != (j - 1) / 4) {
                        // 如果点i和点j不属于同一个矩形，使用普通路径权重t
                        dis[i][j] = t * getDistance(x[i], y[i], x[j], y[j]);
                    } else {
                        // 如果点i和点j属于同一个矩形，使用该矩形的权重w
                        dis[i][j] = w[(i - 1) / 4 + 1] * getDistance(x[i], y[i], x[j], y[j]);
                    }
                }
            }
        }

        // 使用Floyd-Warshall算法计算所有点对之间的最短路径
        for (int k = 1; k <= s * 4; k++) {
            for (int i = 1; i <= s * 4; i++) {
                for (int j = 1; j <= s * 4; j++) {
                    // 更新最短路径
                    dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
                }
            }
        }

        // 计算从起点矩形A到终点矩形B的最短路径
        for (int i = 1; i <= 4; i++) {
            for (int j = 1; j <= 4; j++) {
                // 遍历起点矩形A和终点矩形B的所有四个点，找到最短路径
                ans = min(ans, dis[(A - 1) * 4 + i][(B - 1) * 4 + j]);
            }
        }

        // 输出结果，保留一位小数
        printf("%.1lf\n", ans);
    }
    return 0;
}

声明：为了提高代码可读性，此代码采用了 AI 重构。