思路与算法

每个机场建一个顶点，城市内部两点连铁路费用边，城市之间连航空费用边。任何合法旅行都对应图中路径，反向也成立，因此问题是从A城市四个点到B城市四个点的最短路。三个矩形顶点中恰有一个直角顶点R，另两个为U,V，用向量点积等于0确定R，第四点为U+V−R。

补出每个城市第四机场，初始化全部4S个距离为无穷、A的四机场为0。使用朴素多源Dijkstra：每次选未确定且距离最小机场u，枚举全部机场v，按是否同城计算对应费率乘欧氏距离并松弛。最后取B四机场距离的最小值，输出两位小数。

正确性说明

矩形两条相邻边垂直，因此三个已知点中直角唯一；平行四边形向量恒等式给出的第四顶点正确。建图包含且仅包含题目允许的一段铁路或航线，权值就是该段费用；逐段对应保持总费用。所有边权非负，包括重合机场的零权边，Dijkstra每次选出的最小暂定距离即最短距离：若存在更短路径，沿该路径第一个未确定点的前驱已确定，其松弛已产生不大于这条路径的暂定距离，与选取规则矛盾。四个源距离均设0恰好表示自由选择起点；对四个终点取最小恰好表示自由选择终点，故答案最优。

复杂度

令V=4S。初始化和补点O(V)时间、O(V)空间，朴素选点与隐式完全图松弛总O(V²)时间，每组额外O(V)空间；Q组时间O(QS²)，所有费率相同时仍允许跨城中转但不能违反三角不等式。点积用64位整数避免溢出，欧氏距离用double；本地坐标/费率界下存在直接飞行答案不超过约1.5×10^8，远小于双精度的0.01分辨率。Q=0直接结束；A=B输出0；非退化矩形保证直角可定位；不同城市重合机场对应零费用边。

易错点

不能假定输入第二个机场总是直角顶点；必须检查三个点。铁路可以连接同城任意两机场，城市之间所有机场对也都有航线；不能只比较两个城市的直达费用而漏掉低价铁路中转。不能固定起点或终点机场，A的四点全部以距离0作为源。不同城市机场重合时仍是合法零权边。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
struct Point {
    long long x, y;
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int q;
    cin >> q;
    cout << fixed << setprecision(2);
    while (q--) {
        int s, t, a, b;
        cin >> s >> t >> a >> b;
        --a;
        --b;
        vector<Point> p(4 * s);
        vector<int> price(s);
        for (int i = 0; i < s; i++) {
            Point z[3];
            for (int j = 0; j < 3; j++)
                cin >> z[j].x >> z[j].y;
            cin >> price[i];
            int r = 0;
            for (int j = 0; j < 3; j++) {
                int u = (j + 1) % 3, v = (j + 2) % 3;
                if ((z[u].x - z[j].x) * (z[v].x - z[j].x) + (z[u].y - z[j].y) * (z[v].y - z[j].y) ==
                    0)
                    r = j;
            }
            for (int j = 0; j < 3; j++)
                p[4 * i + j] = z[j];
            p[4 * i + 3] = {z[(r + 1) % 3].x + z[(r + 2) % 3].x - z[r].x,
                            z[(r + 1) % 3].y + z[(r + 2) % 3].y - z[r].y};
        }
        int n = 4 * s;
        vector<double> d(n, 1e100);
        vector<bool> used(n, false);
        for (int i = 0; i < 4; i++)
            d[4 * a + i] = 0;
        for (int it = 0; it < n; it++) {
            int u = -1;
            for (int i = 0; i < n; i++)
                if (!used[i] && (u < 0 || d[i] < d[u]))
                    u = i;
            if (u < 0)
                break;
            used[u] = true;
            for (int v = 0; v < n; v++) {
                double dx = p[u].x - p[v].x, dy = p[u].y - p[v].y,
                       w = hypot(dx, dy) * (u / 4 == v / 4 ? price[u / 4] : t);
                d[v] = min(d[v], d[u] + w);
            }
        }
        double ans = 1e100;
        for (int j = 0; j < 4; j++)
            ans = min(ans, d[4 * b + j]);
        cout << ans << '\n';
    }
}