通讯延迟

形式化题目

平面上有 $n$ 个节点与 $m$ 个通讯基站。每个基站覆盖一个轴对齐正方形（中心 $(x, y)$ 、半边长 $r$ ），正方形内的任意两个节点可用该基站直接通信，延迟为该基站的 $t$ 。求节点 $1$ 到节点 $n$ 的最小总通信延迟；若不可达输出 Nan。

思路

一个基站覆盖 $q$ 个节点时，集合内任意两点连一条 $t$ 的边会产生 $q^2$ 条边。多个大基站会带来平方级的建边开销，需要更巧的建模。

朴素做法：显式建完全图

先看最直接的做法：把每个基站覆盖的节点两两连边，再在普通图上跑 Dijkstra。

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/**
 * 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-07-31 16:21
 * update_at: 2026-08-17 22:39
 */
// brute.cpp：小数据暴力解，把同一基站覆盖的节点两两连边后跑普通 Dijkstra。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 5005;
const long long INF = (1LL << 62);

int n, m;
long long node_x[MAXN], node_y[MAXN];
vector<pair<int, int> > graph[MAXN]; // 显式的节点完全图

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> node_x[i] >> node_y[i];

    // 每个基站：正方形内的任意两个节点连一条延迟边（双向）
    for (int i = 0; i < m; i++) {
        long long x, y, radius, delay;
        cin >> x >> y >> radius >> delay;
        vector<int> covered;
        for (int j = 0; j < n; j++) {
            if (llabs(node_x[j] - x) <= radius && llabs(node_y[j] - y) <= radius) {
                covered.push_back(j);
            }
        }
        // 集合内两两连边，q 个节点会建出 O(q^2) 条边
        for (int a = 0; a < (int)covered.size(); a++) {
            for (int b = 0; b < (int)covered.size(); b++) {
                if (a != b) graph[covered[a]].push_back(make_pair(covered[b], (int)delay));
            }
        }
    }

    // 标准 Dijkstra
    vector<long long> distance(n, INF);
    priority_queue<pair<long long, int>, vector<pair<long long, int> >,
                   greater<pair<long long, int> > > heap;
    distance[0] = 0;
    heap.push(make_pair(0, 0));
    while (!heap.empty()) {
        long long current_distance = heap.top().first;
        int node = heap.top().second;
        heap.pop();
        if (current_distance != distance[node]) continue;
        for (int i = 0; i < (int)graph[node].size(); i++) {
            int next_node = graph[node][i].first;
            long long next_distance = current_distance + graph[node][i].second;
            if (next_distance < distance[next_node]) {
                distance[next_node] = next_distance;
                heap.push(make_pair(next_distance, next_node));
            }
        }
    }

    if (distance[n - 1] == INF) cout << "Nan\n";
    else cout << distance[n - 1] << '\n';
    return 0;
}

做法直观但建边是平方级的，只适合小数据验证最短路语义。

主解：把基站看成超边

一个基站覆盖的节点集合可以看作一条超边：从集合内任意节点进入基站需付出延迟 $t$ ，从基站到集合内任意节点无需额外代价。于是从 $u$ 经该基站到 $v$ 的总代价就是 $t$ 。

在 Dijkstra 中为每个基站维护一个隐式状态：

弹出节点 $u$ 时，扫描所有尚未发现的基站，若 $u$ 在该基站覆盖范围内，就生成基站状态，距离为 当前距离 + t；
弹出基站状态时，以零代价松弛它覆盖的所有节点。

每个基站只被加入一次，避免了集合内完全图。

为什么每个基站只发现一次

Dijkstra 按距离从小到大弹出节点。某个基站第一次被覆盖节点触发时，这个节点是所有能进入该基站的节点中距离最小的已确定节点，因此 当前距离 + t 已经是该基站状态的最小可能值，之后再次进入不可能更优。

代码

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/**
 * 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-07-31 16:21
 * update_at: 2026-08-17 22:39
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 5005;
const int MAXM = 5005;
const long long INF = (1LL << 62);

int n, m;
long long node_x[MAXN], node_y[MAXN];   // 节点坐标
long long station_x[MAXM], station_y[MAXM]; // 基站坐标
long long station_radius[MAXM], station_delay[MAXM]; // 基站覆盖半径与延迟
vector<int> covered[MAXM]; // covered[i] 保存基站 i 覆盖的节点编号
long long dist_node[MAXN]; // dist_node[u] 节点 u 的最短延迟
long long dist_station[MAXM]; // 进入基站 i 后的最短延迟
bool discovered[MAXM];     // 基站 i 是否已被某个节点发现

// 判断节点 node 是否在基站 station 的方形覆盖范围内
bool in_range(int node, int station) {
    return llabs(node_x[node] - station_x[station]) <= station_radius[station]
        && llabs(node_y[node] - station_y[station]) <= station_radius[station];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> node_x[i] >> node_y[i];
    for (int i = 0; i < m; i++) {
        cin >> station_x[i] >> station_y[i] >> station_radius[i] >> station_delay[i];
        for (int j = 0; j < n; j++) {
            if (in_range(j, i)) covered[i].push_back(j);
        }
    }

    // 顶点编号：0..n-1 为节点，n..n+m-1 为基站状态
    priority_queue<pair<long long, int>, vector<pair<long long, int> >,
                   greater<pair<long long, int> > > heap;
    for (int i = 0; i < n; i++) dist_node[i] = INF;
    for (int i = 0; i < m; i++) dist_station[i] = INF;
    dist_node[0] = 0;
    heap.push(make_pair(0, 0));

    while (!heap.empty()) {
        long long current_distance = heap.top().first;
        int vertex = heap.top().second;
        heap.pop();

        if (vertex < n) {
            // 弹出的是节点状态
            int node = vertex;
            if (current_distance != dist_node[node]) continue;
            // 扫描尚未发现的基站：若当前节点在基站范围内，则进入该基站
            for (int i = 0; i < m; i++) {
                if (discovered[i]) continue;
                if (!in_range(node, i)) continue;
                discovered[i] = true;
                dist_station[i] = current_distance + station_delay[i];
                heap.push(make_pair(dist_station[i], n + i));
            }
        } else {
            // 弹出的是基站状态：离开基站不增加延迟，零代价松弛其覆盖的所有节点
            int station_id = vertex - n;
            if (current_distance != dist_station[station_id]) continue;
            for (int i = 0; i < (int)covered[station_id].size(); i++) {
                int next_node = covered[station_id][i];
                if (current_distance < dist_node[next_node]) {
                    dist_node[next_node] = current_distance;
                    heap.push(make_pair(current_distance, next_node));
                }
            }
        }
    }

    if (dist_node[n - 1] == INF) cout << "Nan\n";
    else cout << dist_node[n - 1] << '\n';
    return 0;
}

复杂度

设所有基站覆盖节点的总数为 $K$ 。

时间：预处理覆盖关系 $O(nm)$ 次几何判定；Dijkstra 中每个节点扫描全部基站 $O(nm)$ ，基站状态总共遍历 $O(K)$ 个覆盖节点，总时间复杂度 $O(nm + K \log(n + m))$ 。
空间：覆盖列表与各距离数组 $O(n + m + K)$ 。

总结

当一条边连接某个节点集合中的任意两点时，不要直接建集合内完全图。把集合看成超边，在第一次以最短距离进入时整体展开，既保留最短路语义，又避免平方级边存储。

目录

形式化题目

思路

朴素做法：显式建完全图

主解：把基站看成超边

为什么每个基站只发现一次

代码

复杂度

总结