通讯延迟(csp第35次)

时间限制： 1.5 秒

空间限制： 512 MiB

相关文件： 题目目录（样例文件）

题目描述

给定二维平面上 n 个节点，以及 m 个通讯基站。第 i 个基站可以覆盖以坐标 (xi,yi) 为中心、2ri​ 为边长的正方形区域，并使正方形区域内（包含边界）所有节点以 ti​ 单位时间的延迟进行相互通讯。

求节点 1 到 n 的最短通讯延迟。

输入格式

从标准输入读入数据。

第一行包含空格分隔的两个正整数 n、m；

接下来 n 行，每行两个整数 xi,yi，代表第 i 个节点的坐标；

接下来 m 行，每行四个整数 xj,yj,rj,tj​，代表第 j 个通讯基站的坐标，通讯半径与通讯延迟。

输出格式

输出到标准输出。

输出一行，即节点 1 到 n 的最短通讯延迟；如果无法通讯，则输出 Nan。

样例输入

1
2
3
4
5
6
7
8
9
10
11
5 5
0 0
2 4
4 0
5 3
5 5
1 2 2 5
3 5 2 6
2 0 2 1
4 2 2 3
5 4 1 2

样例输出

1
6

样例解释

1 号通讯基站延迟为 5，覆盖节点 1、2；

2 号通讯基站延迟为 6，覆盖节点 2、4、5；

3 号通讯基站延迟为 1，覆盖节点 1、3；

4 号通讯基站延迟为 3，覆盖节点 2、3、4；

5 号通讯基站延迟为 2，覆盖节点 4、5。

最短延迟方案为：

  1. 节点 1 通过 3 号基站传讯至节点 3，延迟 1；

  2. 节点 3 通过 4 号基站传讯至节点 4，延迟 3；

  3. 节点 4 通过 5 号基站传讯至节点 5，延迟 2；

总计延迟为 6。

子任务

30 的测试数据满足 n,m≤100；

对于额外 30 的测试数据，每个通讯基站至多覆盖 20 个节点；

全部的测试数据满足 n,m≤5000 且 0≤xi,yi,ri≤10^9、1≤ti≤10^5。

题解

  • 初看此题容易想到dijkstra
  • 但本题的难点在于建图 同一个基站内的点两两建边 所费时间代价不小 且建出来的图将会十分复杂
  • 本题所给数据下 稀疏图与稠密图的极端情况均有可能出现 dijkstra堆优化之后最短路算法本身已经没有多少优化的余地
  • 点的范围很大 实际涉及点数不那么多 想到离散化 但其对图的复杂度于事无补
  • 于是看到了这个惊为天人的想法：虚拟节点！
  • 对于一个站覆盖的范围 新建一个虚拟节点 再建所有节点通向虚拟节点的边 与虚拟节点通向所有节点的边 (它们的边权之和为t) 自然实现了这些点两两之间的双向连接 且边的条数从k(k-1)减为2k 大大简化了图 之后便可没有后顾之忧的使用堆优化版的dijkstra啦！

代码与注释

notice！数组要开的足够大 以防RE……

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
// dijkstra常用于解决非负权边 稠密图的问题 不怕有环
// 对于有重边的情况 建图时边权取最小值即可
#include <bits/stdc++.h>
using namespace std;
const int N = 200100 * 2;
// 头节点，权重，指向点，下一条边
typedef pair<int, int> PII;
int h[N], w[N*20], e[N*20], ne[N*20], idx; // 每个通讯基站最多覆盖20个点 可据此确定边的最大条数
int dist[N]; // 存储所有点到一号点的距离
bool st[N]; // 存储每个点是否已经确定
// 本题的关键在于图的存储 若一个通讯站包含k个点 则需要使用双重嵌套循环建立每两个点之间的距离
// 一个通讯站就要建k(k-1)条边 这样的时间复杂度太高 考虑优化
// 想象一个虚拟点 这样一来只需创建每个点到虚拟点 和虚拟点到每个点的边即可 一共2k条边
// 这样大大降低了图的边数 可以使用堆优化版的dijkstra了！
void add(int a, int b, int c) {
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}
int dijkstra(int n) {
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> q; 
    q.push({0, 1});
    while (q.empty() == 0)
    {
        int d = q.top().first, u = q.top().second;
        q.pop();
        if(st[u]) continue;
        st[u] = 1;
        for(int l = h[u]; l!=-1; l=ne[l]) {
            int td = w[l], v = e[l];
            if(st[v]) continue;
            if(d+td < dist[v]) {
                dist[v] = d+td;
                q.push({dist[v], v});
            }
        }
    }
    if(dist[n]==0x3f3f3f3f) return -1;
    else return dist[n];
}
int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    PII node[N];
    for(int i=1; i<=n; i++) {
        scanf("%d%d", &node[i].first, &node[i].second);
    }
    memset(h, -1, sizeof h); // 初始化邻接表
    idx = 0;
    // 处理每个站
    for(int i=1; i<=m; i++) {
        int x, y, r, t;
        scanf("%d%d%d%d", &x, &y, &r, &t);
        int lx = x-r, rx = x+r, ly = y-r, ry = y+r;
        int vi = n+i; // 虚拟节点编号 从n开始往后编
        // 遍历所有节点 找出覆盖范围
        for(int j=1; j<=n; j++) {
            if(node[j].first>=lx&&node[j].first<=rx&&node[j].second>=ly&&node[j].second<=ry) {
                add(j, vi, 0); // 节点到虚拟点边权0
                add(vi, j, t); // 虚拟点到节点边权t
            }
        }
    }
    int res = dijkstra(n);
    if(res == -1) puts("Nan");
    else printf("%d\n", res);
    return 0;
}