无线网络

问题描述

　　目前在一个很大的平面房间里有 n 个无线路由器,每个无线路由器都固定在某个点上。任何两个无线路由器只要距离不超过 r 就能互相建立网络连接。
　　除此以外,另有 m 个可以摆放无线路由器的位置。你可以在这些位置中选择至多 k 个增设新的路由器。
　　你的目标是使得第 1 个路由器和第 2 个路由器之间的网络连接经过尽量少的中转路由器。请问在最优方案下中转路由器的最少个数是多少?

输入格式

　　第一行包含四个正整数 n,m,k,r。(2 ≤ n ≤ 100,1 ≤ k ≤ m ≤ 100, 1 ≤ r ≤ 10⁸)。
　　接下来 n 行,每行包含两个整数 x_i 和 y_i,表示一个已经放置好的无线路由器在 (x_i, y_i) 点处。输入数据保证第 1 和第 2 个路由器在仅有这 n 个路由器的情况下已经可以互相连接(经过一系列的中转路由器)。
　　接下来 m 行,每行包含两个整数 x_i 和 y_i,表示 (x_i, y_i) 点处可以增设一个路由器。
　　输入中所有的坐标的绝对值不超过 10⁸,保证输入中的坐标各不相同。

输出格式

　　输出只有一个数,即在指定的位置中增设 k 个路由器后,从第 1 个路由器到第 2 个路由器最少经过的中转路由器的个数。

样例输入

5 3 1 3
0 0
5 5
0 3
0 5
3 5
3 3
4 4
3 0

样例输出

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<queue>
 6 #define MAX 1010
 7 using namespace std;
 8 
 9 int n, m, k;
10 long long r;
11 
12 struct Node{
13     int x, y;
14     Node(){}
15     Node(int xx, int yy){
16         x = xx, y = yy;
17     }
18     // 优先队列将按距离从小到大排列
19     friend bool operator < (Node n1, Node n2) {
20         return (n1.x + n1.y) > (n2.x + n2.y);
21     }
22 
23 };
24 vector<Node> Point;
25 vector<Node> reach;
26 vector<Node> temp;
27 Node Start, End;
28 
29 bool within(Node n, Node org, long long r){
30     if ( (r*r) < ((n.x - org.x)*(n.x - org.x) + (n.y - org.y)*(n.y - org.y)) ){
31         return false;
32     }
33     return true;
34 
35 }
36 
37 void init(){
38     cin >> n >> m >> k >> r;
39     int x, y;
40     cin >> x >> y;
41     Start.x = x;
42     Start.y = y;
43     cin >> x >> y;
44     End.x = x;
45     End.y = y;
46     for (int i = 0; i < m + n - 2; i++)
47     {
48         cin >> x >> y;
49         Point.push_back(Node(x, y));
50     }
51 }
52 
53 int solve(){
54     int ans = 0;
55     for (vector<Node>::iterator it = Point.begin(); it != Point.end();){
56         if (within(*it, Start, r)){
57             reach.push_back(*it);
58             it = Point.erase(it);
59         }
60         else
61             it++;
62     }
63 
64     while (1)
65     {
66         ans++;
67         for (int i = 0; i < reach.size(); i++){
68             if (within(End, reach[i], r))
69                 return ans;
70         }
71         while (reach.size())
72         {
73             Node tempnode = reach[reach.size() - 1];
74             for (vector<Node>::iterator it = Point.begin(); it != Point.end();){
75                 if (within(*it, tempnode, r)){
76                     temp.push_back(*it);
77                     it = Point.erase(it);
78                 }
79                 else
80                     it++;
81             }
82             reach.pop_back();
83         }
84         reach = temp;
85         temp.clear();    
86     }
87 }
88 
89 int main(){
90     init();
91     cout << solve();
92     return 0;
93 }