2020-03-13(CCF201403-4 无线网络）

#include <iostream>
#include <queue>
//#include <cmath>
//#include <cstring>
 using namespace std;
 
 /*
    把坐标转换成顶点
    将顶点抽象出来以后，就可以运用正常的邻接矩阵来做， 
 */
 
const int N = 210;
int g[N][N];  // 1 代表有边 
bool flag[N]; // 是否在新增里，true 表示在新增的里面 
typedef pair<int, int> PII;
PII tmp[N]; //将路由器的坐标先存进来， 再构造图 
int res[N]; // 存放结果 ，表示第 i 个路由器的最小步数是多少 
int n, m, k;
long long r;
queue<PII> q;  // first: 第几个顶点(路由器)   second: 此时经过了多少个新增设的 (注意要 <= k) 
//int bet; // 表示经过了多少个新增的，必须 <= k 
bool st[N]; // 标记该点（路由器）有没有被找过 

long long dist(long long a, long long  b, long long c, long long  d)
{
    long long res = (long long )((c-a) * (c-a)) + (long long)((d - b) * (d - b));
    return res;
}

void make_graph()
{
    for(int i = 1; i <= n+m; i++)
    {
        for(int j = i+1; j <= n+m; j++)
        {
             long long t = dist(tmp[j].first, tmp[j].second, tmp[i].first, tmp[i].second); 
            if( t  <= (long long )(r * r) ) 
            {
                g[i][j] = g[j][i] = 1;
            }
            
        }
        if(i > n) flag[i] = true;
          
    }
}

 int main()
 {
    scanf("%d%d%d%d", &n, &m, &k, &r);

    
    for(int i = 1; i <= n+m; i++)
    {
        long long a, b;
        scanf("%lld %lld", &a, &b); 
        tmp[i].first = a;   tmp[i].second = b; 
    }
    
    make_graph();   
     q.push({1, 0});
     st[1] = true;
     while(q.size())
     {
        PII t = q.front();
        int x = t.first,   bet = t.second;
        st[x] = true;
        q.pop();
        if(x == 2) break;
        for(int i = 1; i <= n+m; i++)
        {
            if( !st[i] && g[x][i] && bet <= k) // 有边，但还要分是新增的还是可以随便放的 
             {
                if(!flag[i]) //可以随便放
                  {
                      res[i] = res[x] + 1;
                      if(!st[i])
                      {
                        q.push({i, bet});
                       } 
                      st[i] = true;
                      
                  } 
                  
                if(flag[i] && bet +1 <=k)
                {
                    res[i] = res[x] + 1;
                    if(!st[i]) 
                    {
                        q.push({i, bet + 1});
                    }
                    st[i] = true;
                    
                }
             }  
        }
     }

    cout<<res[2] - 1<<endl;
  }