C++ 代码

dist[i][j]数组的含义：从路由器1到路由器i且增设j个路由器时的最短路径
queue<pair<int, int>> 中first表示路由器编号， second表示增设的路由器数量

#include<iostream>
#include<cstring> 
#include<queue>
#include<algorithm>
#define x first
#define y second

using namespace std;
const int N = 210, M = N * N;
typedef pair<int, int> PII;
typedef long long LL;
int e[M], ne[M], h[N], idx;
//dist[i][j]表示终点为i且增设j个路由器时，到起点的最短距离
int dist[N][N];
//存每个路由器的坐标
PII route[N];
int n, m, k, r;
void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
//判断两点之间是否有边连接
bool check(int i, int j)
{
    LL x = route[i].x - route[j].x;
    LL y = route[i].y - route[j].y;
    return x * x + y * y <= (LL)r * r;
}
int bfs()
{
//q.x表示当前路由器编号， q.y表示增设的路由器数量
    queue<PII> q;
    q.push({1, 0});
    memset(dist, 0x3f, sizeof dist);
    dist[1][0] = 0;
    while(q.size())
    {
        auto t = q.front();
        q.pop();
        int num = t.x;
//遍历与当前路由器相连的路由器
        for(int i = h[num]; ~i; i = ne[i])
        {
            int j = e[i], y = t.y;
            //路由器编号大于n， 说明是增设的
            if(j > n) y++;
            if(y <= k)
            {
                if(dist[j][y] > dist[num][t.y] + 1)
                {
                    dist[j][y] = dist[num][t.y] + 1;
                    q.push({j, y});
                }
            }
        }
    }
//遍历所有增设路由器的情况，求路由器1到路由器2的最短距离
    int res = 1e8;
    for(int i = 0; i <= k; i++) res = min(res, dist[2][i]);
//求路由器1和路由器2之间的路由器数量
    return res - 1;
}
int main()
{
    cin >> n >> m >> k >> r;
    memset(h, -1, sizeof h);
//记录每个路由器的位置， 编号超过n的是增设的路由器
    for(int i = 1; i <= n + m; i ++) cin >> route[i].x >> route[i].y ;
//如果两个路由器距离小于r，连接一条无向边
    for(int i = 1; i < m + n; i++)
        for(int j = i + 1; j <= m + n ;j++)
            if(check(i, j)) add(i ,j), add(j, i);

    cout << bfs();
    return 0;
}