[NOIP2001-提高] Car的旅行路线

形式化题目

有 $S$ 座城市，每座城市恰有 $4$ 个机场，位于一个矩形的 $4$ 个顶点上，但输入只给出每座城市任意 $3$ 个顶点的坐标。第 $i$ 座城市内任意两个机场之间都有一条笔直的高速铁路，单位里程价格为 $T_i$ ；任意两个不同城市的机场之间都有一条航线，单位里程价格统一为 $t$ 。一段路程的花费等于它的欧氏距离乘以该段的单位价格。给定起点城市 $A$ 与终点城市 $B$ ，求从 $A$ 的任意机场出发、到达 $B$ 的任意机场的最小总花费。

以样例为例： $S = 3$ ， $t = 10$ ， $A = 1$ ， $B = 3$ 。三座城市各补出第 4 个机场后，最优路线是「城 1 机场 3 $(3,1)$ —航线 $22.36$ → 城 2 机场 3 $(5,2)$ —铁路 $2.83$ → 城 2 机场 2 $(7,4)$ —航线 $22.36$ → 城 3 机场 1 $(8,6)$ 」，总花费 $47.549\cdots$ ，输出 47.5：

text

1
2
3
4
5
6
7
8
9输入
1
3 10 1 3
1 1 1 3 3 1 30
2 5 7 4 5 2 1
8 6 8 8 11 6 3

输出
47.5

正解

思路

先看朴素想法为什么不行。最直接的建模是「把一座城市压成一个点」：但一条航段的花费取决于从哪个机场起飞、在哪个机场降落，降落机场又决定城内铁路要走多远才能接上下一段——城市粒度的状态丢掉了「从哪个机场进出」，答案会算错。若把状态细化到机场，却按「枚举中转城市序列 + 每段贪心选最便宜机场」来做，中转序列有指数多种；而且相邻两段共用同一个中转机场，两段的机场选择互相耦合，贪心也不成立。

两个朴素做法共同的瓶颈是：路线任意，且相邻两段的机场衔接互相耦合。这恰好是最短路模型的适用场景——把「衔接」显式地写成边，让算法去枚举所有可能的衔接方式。

于是推导分三步。

第一步：补出第 4 个机场。 矩形按环序为 $P_1P_2P_3P_4$ ，设缺失点为 $d$ ，则它的对顶点 $c$ 一定在已知三点中； $c$ 的两条邻边通向的恰好是另外两个已知点 $a, b$ ，且 $c$ 处成直角。由对角线互相平分 $a + b = c + d$ 得

d = a + b - c.

实现时只需在三个已知点里找点积为 $0$ 的那个直角顶点。样例三城的补点结果如下（表格列出已知三点、直角顶点与第四点）：

城市	已知三点	直角顶点 $c$	另两点 $a, b$	第四点 $a+b-c$
1	(1, 1)、(1, 3)、(3, 1)	(1, 1)	(1, 3)、(3, 1)	(3, 3)
2	(2, 5)、(7, 4)、(5, 2)	(5, 2)	(2, 5)、(7, 4)	(4, 7)
3	(8, 6)、(8, 8)、(11, 6)	(8, 6)	(8, 8)、(11, 6)	(11, 8)

第二步：把机场建成图上的点。 粒度必须细到「(城市, 机场编号)」，全图共 $4S$ 个点。按题意连两类无向边：

同城边：每座城市 $\binom{4}{2} = 6$ 条铁路，边权 = 欧氏距离 $\times\ T_i$ ；
异城边：每对城市 $4 \times 4 = 16$ 条航线，边权 = 欧氏距离 $\times\ t$ 。

这样任何一条合法路线都对应图上一条路径，反之亦然，边权全部为正。

第三步：多源 Dijkstra。 「出发机场任选」等价于把 $A$ 城 4 个机场的距离初值都设为 $0$ 一起入堆；「到达机场任选」等价于优先队列第一次弹出 $B$ 城的任一机场时其距离就是答案（首次弹出的点已被最短路覆盖），直接返回即可，不必跑完全部点。三步分别对应 main.py 的 rect_fourth（补点）、build_graph（建图）与 min_fare（多源 Dijkstra）。

回到样例：城 1 铁路单价 30 太贵，最优路线完全不走城 1 的铁路，而是从 $(3,1)$ 飞进单价只有 1 的城 2，用城内铁路把位置从 $(5,2)$ 换到 $(7,4)$ ，再飞进城 3 的 $(8,6)$ ，合计 $22.36 + 2.83 + 22.36 \approx 47.55$ 。若从城 1 最近的机场 $(3,3)$ 直飞城 3 最近的 $(8,6)$ ，要 $\sqrt{34}\times 10 \approx 58.3$ ——「借便宜的城市铁路换位再飞」正是本题的最优结构。实现上中间过程全程用双精度累加，只在输出时 f"{fare:.1f}" 四舍五入到一位小数，避免中途舍入误差。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-10 11:30
 * update_at: 2026-10-10 11:30
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

// 矩形三个顶点补出第四个顶点：直角顶点为 c，另两点 a、b，第四顶点 = a + b - c
pair<int, int> rect_fourth(pair<int, int> a, pair<int, int> b, pair<int, int> c) {
    // c 是直角顶点
    return make_pair(a.first + b.first - c.first, a.second + b.second - c.second);
}

// 已知三点求第四个顶点
pair<int, int> rect_fourth_from_three(pair<int, int> p1, pair<int, int> p2, pair<int, int> p3) {
    pair<int, int> pts[3] = {p1, p2, p3};
    for (int i = 0; i < 3; i++) {
        pair<int, int> c = pts[i];
        pair<int, int> a = pts[(i + 1) % 3];
        pair<int, int> b = pts[(i + 2) % 3];
        ll dot = (ll)(a.first - c.first) * (b.first - c.first)
               + (ll)(a.second - c.second) * (b.second - c.second);
        if (dot == 0) return rect_fourth(a, b, c);
    }
    return make_pair(0, 0);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int cases;
    cin >> cases;
    cout << fixed << setprecision(1);
    while (cases--) {
        int city_count, fly_price;
        cin >> city_count >> fly_price;
        int start, end;
        cin >> start >> end;

        int total = city_count * 4;
        vector<pair<int, int> > airports(total);
        vector<int> rail(city_count);

        for (int c = 0; c < city_count; c++) {
            pair<int, int> p1, p2, p3;
            cin >> p1.first >> p1.second;
            cin >> p2.first >> p2.second;
            cin >> p3.first >> p3.second;
            cin >> rail[c];
            int base = c * 4;
            airports[base + 0] = p1;
            airports[base + 1] = p2;
            airports[base + 2] = p3;
            airports[base + 3] = rect_fourth_from_three(p1, p2, p3);
        }

        // 建图
        vector<vector<pair<int, double> > > adj(total);
        for (int c = 0; c < city_count; c++) {
            int base = c * 4;
            for (int i = 0; i < 4; i++) {
                for (int j = i + 1; j < 4; j++) {
                    double dx = airports[base + i].first - airports[base + j].first;
                    double dy = airports[base + i].second - airports[base + j].second;
                    double w = sqrt(dx * dx + dy * dy) * rail[c];
                    adj[base + i].push_back(make_pair(base + j, w));
                    adj[base + j].push_back(make_pair(base + i, w));
                }
            }
        }
        for (int c = 0; c < city_count; c++) {
            int base = c * 4;
            for (int c2 = c + 1; c2 < city_count; c2++) {
                int base2 = c2 * 4;
                for (int i = 0; i < 4; i++) {
                    for (int j = 0; j < 4; j++) {
                        double dx = airports[base + i].first - airports[base2 + j].first;
                        double dy = airports[base + i].second - airports[base2 + j].second;
                        double w = sqrt(dx * dx + dy * dy) * fly_price;
                        adj[base + i].push_back(make_pair(base2 + j, w));
                        adj[base2 + j].push_back(make_pair(base + i, w));
                    }
                }
            }
        }

        // 多源 Dijkstra：4 个起点并入，任一终点到达即停
        int base_a = (start - 1) * 4;
        int base_b = (end - 1) * 4;
        vector<double> dist(total, 1e18);
        priority_queue<pair<double, int>, vector<pair<double, int> >, greater<pair<double, int> > > pq;
        for (int i = 0; i < 4; i++) {
            dist[base_a + i] = 0.0;
            pq.push(make_pair(0.0, base_a + i));
        }
        double ans = 1e18;
        while (!pq.empty()) {
            double cost = pq.top().first;
            int u = pq.top().second;
            pq.pop();
            if (cost > dist[u]) continue;
            if (u >= base_b && u < base_b + 4) { ans = cost; break; }
            for (size_t i = 0; i < adj[u].size(); i++) {
                int v = adj[u][i].first;
                double w = adj[u][i].second;
                if (cost + w < dist[v]) {
                    dist[v] = cost + w;
                    pq.push(make_pair(cost + w, v));
                }
            }
        }
        cout << ans << "\n";
    }
    return 0;
}

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-02 04:43
# update_at: 2026-10-02 04:43

import sys
from collections.abc import Iterable
from heapq import heappop, heappush
from math import hypot


def rect_fourth(pts: list[tuple[int, int]]) -> tuple[int, int]:
    """矩形三个顶点补出第四个顶点。

    三个已知点里恰有一个顶点的两条邻边都在已知点中（直角顶点），记它为 c、
    另两点为 a、b，则第四个顶点 = a + b - c（对角线互相平分）。
    """
    for i, (cx, cy) in enumerate(pts):
        (ax, ay), (bx, by) = [p for j, p in enumerate(pts) if j != i]
        if (ax - cx) * (bx - cx) + (ay - cy) * (by - cy) == 0:  # a、b 在 c 处张成直角
            return ax + bx - cx, ay + by - cy
    raise ValueError("三个点构不成矩形顶点")  # 题面保证不会走到这里


def build_graph(
    airports: list[tuple[int, int]],
    rail: list[int],
    fly_price: int,
) -> list[list[tuple[int, float]]]:
    """把每个机场建成图上的一个点：同城机场两两修铁路，异城机场两两修航线。"""
    city_count = len(rail)
    adj: list[list[tuple[int, float]]] = [[] for _ in range(city_count * 4)]
    for c in range(city_count):
        base = c * 4
        for i in range(4):  # 同城 6 条铁路，单价 Ti
            xi, yi = airports[base + i]
            for j in range(i + 1, 4):
                xj, yj = airports[base + j]
                rail_cost = hypot(xi - xj, yi - yj) * rail[c]
                adj[base + i].append((base + j, rail_cost))
                adj[base + j].append((base + i, rail_cost))
        for c2 in range(c + 1, city_count):  # 异城 4x4=16 条航线，单价 t
            base2 = c2 * 4
            for i in range(4):
                xi, yi = airports[base + i]
                for j in range(4):
                    xj, yj = airports[base2 + j]
                    fly_cost = hypot(xi - xj, yi - yj) * fly_price
                    adj[base + i].append((base2 + j, fly_cost))
                    adj[base2 + j].append((base + i, fly_cost))
    return adj


def min_fare(adj: list[list[tuple[int, float]]], sources: Iterable[int], targets: set[int]) -> float:
    """多源 Dijkstra：从任一 source 出发、到任一 target 的最少花费，首次弹出 target 即答案。"""
    dist = [float("inf")] * len(adj)
    heap: list[tuple[float, int]] = []
    for s in sources:
        dist[s] = 0.0
        heappush(heap, (0.0, s))
    while heap:
        cost, u = heappop(heap)
        if cost > dist[u]:  # 过期堆元素
            continue
        if u in targets:  # 第一个弹出的目标点已被最短路覆盖
            return cost
        for v, w in adj[u]:
            if cost + w < dist[v]:
                dist[v] = cost + w
                heappush(heap, (cost + w, v))
    return float("inf")  # 航线全连通，实际不可达


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    out: list[str] = []
    cases = next(data)

    for _ in range(cases):
        city_count, fly_price = next(data), next(data)
        start, end = next(data), next(data)  # 出发城市 A、到达城市 B 的序号

        airports: list[tuple[int, int]] = []
        rail: list[int] = []  # 每城铁路单价 Ti，与 airports 按 4 个一组对齐
        for _ in range(city_count):
            pts = [(next(data), next(data)) for _ in range(3)]
            rail.append(next(data))  # 题面每行末尾的 Ti：该城铁路单位里程价格
            airports += [*pts, rect_fourth(pts)]

        adj = build_graph(airports, rail, fly_price)
        base_a, base_b = (start - 1) * 4, (end - 1) * 4
        # 出发、到达机场都可以任选：4 个起点并入、4 个终点任一到达即停
        fare = min_fare(
            adj,
            range(base_a, base_a + 4),
            set(range(base_b, base_b + 4)),
        )
        out.append(f"{fare:.1f}")

    print("\n".join(out))


if __name__ == "__main__":
    solve()

复杂度

时间：补点 $O(S)$ ；建图共 $6S + 16\binom{S}{2} = O(S^2)$ 条边；堆优化 Dijkstra 为 $O(E\log V) = O(S^2\log S)$ 。 $S \leqslant 100$ 时 $V = 400$ 、 $E \leqslant 79\,800$ ，实测每组约 0.02s。
空间：邻接表 $O(V + E) = O(S^2)$ ，实测峰值约 16MB。

总结

把「机场」而不是「城市」作为状态粒度：先用直角顶点补出矩形的第 4 个机场，再按「同城铁路、异城航线」两类边把题面直接翻译成一张正权无向图，最后用多源 Dijkstra（起点端 4 点初值 0、首次弹出终点城市即返回）求出最小花费。核心是识别出「相邻两段的机场衔接」必须交给最短路枚举，而不是贪心。

图示解析

这张图串起样例从补点、建模到得到答案的主线（异城航线两两全连，图中只画出最优路线用到的三段）：

flowchart LR
    subgraph city1["城市 1（铁路单价 30）"]
        a0["机场1 (1, 1)"]
        a1["机场2 (1, 3)"]
        a2["机场3 (3, 1)"]
        a3["机场4 (3, 3)"]
    end
    subgraph city2["城市 2（铁路单价 1）"]
        b0["机场1 (2, 5)"]
        b1["机场2 (7, 4)"]
        b2["机场3 (5, 2)"]
        b3["机场4 (4, 7)"]
    end
    subgraph city3["城市 3（铁路单价 3）"]
        c0["机场1 (8, 6)"]
        c1["机场2 (8, 8)"]
        c2["机场3 (11, 6)"]
        c3["机场4 (11, 8)"]
    end
    a2 ==>|航线 22.4| b2
    b2 ==>|铁路 2.8| b1
    b1 ==>|航线 22.4| c0
    start["城 1 任选出发"]:::ghost -.-> a2
    c0 -.-> goal["城 3 任选到达"]:::ghost
    classDef ghost fill:#fff,stroke:#999,stroke-dasharray: 3 3

先看每个子图是一个城市的 4 个机场（含补出来的第 4 个），再顺着粗边看路线：城 1 铁路单价 30 太贵，所以不在城 1 走铁路，而是从机场 3 直接飞进城 2，用单价 1 的铁路换到更好的起飞位，再飞进城 3 的机场 1。三段花费 $22.36 + 2.83 + 22.36 \approx 47.55$ ，而城 1 直飞城 3 最省也要 $\sqrt{34} \times 10 \approx 58.3$ ，说明「借便宜的城市铁路换位再飞」才是答案的来源。