CCF模拟 无线网络

 1 #include <bits/stdc++.h>
 2 #define LL long long
 3 using namespace std;
 4 const int maxn = 300;
 5 struct point {
 6     int x,y,isadded;
 7 } p[maxn*maxn];
 8 int n,m,k,d[maxn];
 9 double r;
10 double getDis(int i,int j) {
11     double tmp = (LL)(p[i].x - p[j].x)*(p[i].x - p[j].x);
12     tmp += (LL)(p[i].y - p[j].y)*(p[i].y - p[j].y);
13     return sqrt(tmp);
14 }
15 struct node {
16     int id,pass,added;
17     node(int x = 0,int y = 0,int z = 0) {
18         id = x;
19         pass = y;
20         added = z;
21     }
22 };
23 queue<node>q;
24 int bfs(){
25     memset(d,0x3f,sizeof(d));
26     while(!q.empty()) q.pop();
27     d[0] = 0;
28     q.push(node(0,0,0));
29     while(!q.empty()){
30         node now = q.front();
31         q.pop();
32         for(int i = 1; i < n+m; ++i)
33         if(i != now.id && getDis(i,now.id) <= r&& now.added+p[i].isadded <= k && d[i] > now.pass+1){
34             d[i] = now.pass + 1;
35             //cout<<i<<" "<<d[i]<<endl;
36             q.push(node(i,d[i],now.added+p[i].isadded));
37         }
38     }
39     return d[1] - 1;
40 }
41 int main() {
42     while(~scanf("%d %d %d %lf",&n,&m,&k,&r)) {
43         for(int i = 0; i < n + m; ++i) {
44             scanf("%d %d",&p[i].x,&p[i].y);
45             p[i].isadded = i >= n?1:0;
46         }
47         cout<<bfs()<<endl;
48     }
49     return 0;
50 }