CCF-CSP第35次认证第四题——通讯延迟
官网题目链接：TUOJ
时间限制： 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。
样例输入
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
样例输出
6
样例解释
子任务
参考题解【存在效率问题，可直接看堆优化版】
思考过程：看到求最短通讯延迟，想到求最短路径，再一看题目说的是求节点 1 到 𝑛 的最短通讯延迟，想到可以用求单源最短路径的dijkstra算法
问题在于如何初始化图，边权显然是节点间的通讯延迟，而两个节点要能直接通讯则需要在同一基站的覆盖范围内，此时这两个节点之间有权值为该基站延时的无向边【无向图可以当有向图存，存每次存两条边即可】
但是图的初始化仍比较麻烦，因为在同一基站覆盖范围内的点两两之间可互相通信，需要用一个嵌套循环，这里我是用vector的迭代器在实现的【这里需要注意，不能直接将t赋值给边，而是要进行一个最小值判断，因为可能出现两个节点在多个基站覆盖范围内的情况，这时需要选择最小的延时作为边权】
#include<iostream>
#include<vector>
#include<cstring>using namespace std;typedef pair<int, int> PII;const int N = 5010;int g[N][N]; //存储每条边
int dist[N]; //存储1号点到每个点的最短距离
bool st[N]; //每个点的最短路径是否已经确定
vector <vector<int> > region (N, vector<int>(N, -1) ); //存储在同一个基站覆盖范围内的结点 PII nodes[N], stations[N], stations_rt[N];int dijkstra(int n) { for(int i = 1; i <= n - 1; i ++) {//每次找一个点，除1之外还有n-1个点，所以要循环n-1次 int t = -1; //在还未确定最短路的点中，寻找距离最小的点 for(int j = 1; j <= n; j ++) {if(!st[j] && (t == -1 || dist[t] > dist[j]))t = j;} //用t更新其他点的距离for(int j = 1; j <= n; j++) {dist[j] = min(dist[j], dist[t] + g[t][j]);} st[t] = true;}if(dist[n] == 0x3f3f3f3f) return -1;return dist[n];
} int main() {int n, m;scanf("%d%d", &n, &m); //n个结点，m个通讯基站for(int i = 1; i <= n; i++) {scanf("%d%d", &nodes[i].first, &nodes[i].second);} for(int i = 1; i <= m; i++) {scanf("%d%d%d%d", &stations[i].first, &stations[i].second, &stations_rt[i].first, &stations_rt[i].second);} //存图for(int i = 1; i <= m; i++) {//计算每个基站的覆盖范围 int radius = stations_rt[i].first;int l = stations[i].first - radius;int r = stations[i].first + radius;int top = stations[i].second + radius;int bottom = stations[i].second - radius;int idx = 0;for(int j = 1; j <= n; j++) {if ( (nodes[j].first >= l && nodes[j].first <= r) && (nodes[j].second >= bottom && nodes[j].second <= top) ) {region[i][idx++] = j; //在基站i覆盖范围内的所有结点j ---- 注意这里不能用push_back否则是在原有大小的后面添加了新元素 }} } memset(dist, 0x3f, sizeof dist);memset(g, 0x3f, sizeof g); // 别忘了初始化g为无穷大！！！我就说怎么结果一直是0 dist[1] = 0;for(int i = 1; i <= m; i++) {int t = stations_rt[i].second;for(auto j = region[i].begin(); *j != -1; j ++) {for(auto k = j + 1; *k != -1; k ++) {if(*j == *k) { //忽略自环 continue;}else if(*j == 1) {dist[*k] = t;g[*j][*k] = min(g[*j][*k], t);g[*k][*j] = min(g[*k][*j], t);}else if(*k == 1) {dist[*j] = t;g[*j][*k] = min(g[*j][*k], t);g[*k][*j] = min(g[*k][*j], t);}else {g[*j][*k] = min(g[*j][*k], t);g[*k][*j] = min(g[*k][*j], t);}}}}int res = dijkstra(n);if(res == -1) {printf("Nan\n");}else {printf("%d\n", res);}return 0;
}
但是上述题解存在性能问题：
本题中图很有可能是稀疏图（m = n ），稀疏图用堆优化版的dijkstra，效率为O(mlogn)
【稠密图(m = n ^ 2)用朴素版dijkstra即可，O(n ^ 2)】-------- 不对，这道题中稠密图和稀疏图的极端情况都有可能出现，两种方法都有可能不能通过所有测试点，要思考其他解决办法 ---- 堆优化版+虚拟节点或使用优先队列
优化版
从上面的分析可知，可将代码优化为使用虚拟节点【引入虚拟节点后边数骤降，可看为稀疏图，使用堆优化版dijkstra算法】
虚拟节点的作用是将一个基站覆盖的所有节点连接到这个虚拟节点上，而不是彼此之间直接连接。这样，原本需要k*(k-1)/2条边的全连接，现在只需要每个节点连接到虚拟节点，这样边数就从O(k²)降到了O(k)。当两个节点在同一个基站下通信时，它们可以通过虚拟节点中转，总延迟为基站延迟t，这样既保持了正确的延迟计算，又大幅减少了边数。
另外，可以不在一开始使用如下代码固定vector数组大小
vector <vector<int> > region (N, vector<int>(N, -1) ); //存储在同一个基站覆盖范围内的结点
我当时是想着如果不提前分配的话，到时候数组大小不够用了，重新分配空间会有时间开销；
但是这样有一个缺点就是我需要通过-1来判断当前数据是否合法，其实还有更好的选择，我可以通过reserve预分配空间，再用push_back添加元素
for (int i = 1; i <= m; i++) {region[i].reserve(n); //通过循环对内层数组预分配大小--还减少了空间复杂度，因为n <= N
}
优化vector相关后代码
#include<iostream>
#include<vector>
#include<cstring>using namespace std;typedef pair<int, int> PII;const int N = 5010;int g[N][N]; //存储每条边
int dist[N]; //存储1号点到每个点的最短距离
bool st[N]; //每个点的最短路径是否已经确定
vector <vector<int> > region (N); //存储在同一个基站覆盖范围内的结点 PII nodes[N], stations[N], stations_rt[N];int dijkstra(int n) { for(int i = 1; i <= n - 1; i ++) {//每次找一个点，除1之外还有n-1个点，所以要循环n-1次 int t = -1; //在还未确定最短路的点中，寻找距离最小的点 for(int j = 1; j <= n; j ++) {if(!st[j] && (t == -1 || dist[t] > dist[j]))t = j;} //用t更新其他点的距离for(int j = 1; j <= n; j++) {dist[j] = min(dist[j], dist[t] + g[t][j]);} st[t] = true;}if(dist[n] == 0x3f3f3f3f) return -1;return dist[n];
} int main() {int n, m;scanf("%d%d", &n, &m); //n个结点，m个通讯基站for(int i = 1; i <= n; i++) {scanf("%d%d", &nodes[i].first, &nodes[i].second);} for(int i = 1; i <= m; i++) {scanf("%d%d%d%d", &stations[i].first, &stations[i].second, &stations_rt[i].first, &stations_rt[i].second);} //存图for(int i = 1; i <= m; i++) {region[i].reserve(n); //一个区域最多覆盖所有节点n }for(int i = 1; i <= m; i++) {//计算每个基站的覆盖范围 int radius = stations_rt[i].first;int l = stations[i].first - radius;int r = stations[i].first + radius;int top = stations[i].second + radius;int bottom = stations[i].second - radius;for(int j = 1; j <= n; j++) {if ( (nodes[j].first >= l && nodes[j].first <= r) && (nodes[j].second >= bottom && nodes[j].second <= top) ) {region[i].push_back(j); //在基站i覆盖范围内的所有结点j }} } memset(dist, 0x3f, sizeof dist);memset(g, 0x3f, sizeof g); // 别忘了初始化g为无穷大！！！我就说怎么结果一直是0 dist[1] = 0;for(int i = 1; i <= m; i++) {int t = stations_rt[i].second;for (int j = 0; j < region[i].size(); j++) {for (int k = j + 1; k < region[i].size(); k++) {int u = region[i][j], v = region[i][k];if(u == v) continue; // 虽然不太可能出现重复，保险起见可以判断// 更新边权，取最小值g[u][v] = min(g[u][v], t);g[v][u] = min(g[v][u], t);// 特殊处理与节点1相关的情况if(u == 1) dist[v] = min(dist[v], t);if(v == 1) dist[u] = min(dist[u], t);}}}int res = dijkstra(n);if(res == -1) {printf("Nan\n");}else {printf("%d\n", res);}return 0;
}虚拟节点+堆优化版dijkstra
用优先队列实现堆
#include<iostream>
#include<cstring>
#include<queue>using namespace std;typedef pair<int, int> PII;const int N = 10010 * 2; //注意节点数 = n + m而不是n，因为要引入m个虚拟节点--- 开2倍确保足够 int h[N], w[N * 20], e[N * 20], ne[N * 20], idx; //因为题目说了每个通讯基站最多覆盖20个节点，也就是说最多有 N * 20条边
int dist[N]; //存储所有点到1号点的距离
bool st[N]; //存储每个点的最短距离是否已确定 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> >heap;heap.push({0, 1}); //first存距离（即边权），second存编号【因为排序会先按first排】 while(!heap.empty()) {auto t = heap.top();heap.pop();int number = t.second, distance = t.first;if(st[number]) continue; //如果已经找到该点的最短距离则进入下一次循环st[number] = true;for(int i = h[number]; i != -1; i = ne[i]) {int j = e[i]; //节点number的邻接节点jif(dist[j] > distance + w[i]) {dist[j] = distance + w[i];heap.push({dist[j], j});} }}if(dist[n] == 0x3f3f3f3f) return -1;return dist[n];
}int main () {int n, m;scanf("%d%d", &n, &m);PII node[n + 1];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;int ly = y - r, ry = y + r;int vi = n + i; //虚拟节点编号---从n开始往后编//遍历所有节点，找出覆盖范围for(int j = 1; j <= n; j++) {int nx = node[j].first, ny = node[j].second;if(nx >= lx && nx <= rx && ny >= ly && ny <= ry) {add(j, vi, 0); //节点到虚拟节点边权0add(vi, j, t); //虚拟节点到节点边权t }} }int res = dijkstra(n);if(res == -1) puts("Nan");else printf("%d\n", res); return 0;
}总结
该题思想很巧妙，通过引入一个虚拟节点，成功将k*(k-1)条有向边【同一基站覆盖范围内的每两个节点之间有两条】变成了2k条【每个节点到虚拟点一条，虚拟点到每个节点一条】，大大降低了初始化图的时间复杂度，而且由于大大降低了图的边数，可以通过使用堆优化版的dijkstra算法来提高效率。
以前没用过相关思想会很难想到这个方法，有经验以后就会好很多。
