分析

1. 将前n个固定点,m个待选择点存入节点数组p[],之后计算数组中每两个点间的距离，如果距离小于r，就在这两点之间建立一条无向边。

2. 关系建立后进行bfs()
   dist[i][j]表示 第i个点的路径中增设路由器的数量为j的最短距离。

3. 由于题目询问的是路径上路由器的最少数量，实际不用考虑计算路径长度，只需要把点的数量当做所谓的长度进行计算。

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N = 210;
typedef long long LL;
int h[N],e[N*N],ne[N*N],idx;
int n,m,k,r;
int dist[N][N];
struct node{
    int x,y;
}p[N];
bool check(int a,int b) 
{
    LL s1=(LL)(p[a].x-p[b].x)*(p[a].x-p[b].x)+(LL)(p[a].y-p[b].y)*(p[a].y-p[b].y);  //乘积很大，开LL
    return s1<=(LL)r*r;
}
void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int bfs()
{
    memset(dist,0x3f,sizeof dist);
    queue<node> q;
    q.push({1,0});  
    dist[1][0]=0;   //刚开始 在点1，路径上增设的路由器数量为0，距离也是0

    while(q.size())
    {
        auto t=q.front();
        q.pop();

        for(int i=h[t.x];~i;i=ne[i])
        {
            auto j=e[i],cnt=t.y;    //j是点t能够到达得到点，cnt是这个点路径上的增设的路由器数量
            if(j>n) cnt++;  //如果该点处于[n+1,n+m]，说明为增设的路由器，此时cnt++
            if(cnt<=k)  //如果此时还能继续增设路由器
            {
                if(dist[j][cnt]>dist[t.x][t.y]+1)   //如果可以更新最短路就进行更新
                {
                    dist[j][cnt]=dist[t.x][t.y]+1;  
                    q.push({j,cnt});
                }
            }
        }
    }

    int ans=N;
    for(int i=0;i<=k;i++)   //由题意，点2为终点，dist[2][i]表示到达点2，增设路由器i个的最短路
        ans=min(ans,dist[2][i]);    

    return ans-1;
}
int main()
{
    memset(h,-1,sizeof h);
    cin>>n>>m>>k>>r;
    for(int i=1;i<=n;i++) cin>>p[i].x>>p[i].y;
    for(int i=n+1;i<=n+m;i++) cin>>p[i].x>>p[i].y;

    for(int i=1;i<=n+m;i++) //枚举每两个点间的距离，如果距离小于r，就建立无向边
    {
        for(int j=i+1;j<=n+m;j++)
        {
            if(check(i,j))  
                add(i,j),add(j,i);
        }       
    }

    cout<<bfs();
    return 0;
}