$\quad$先从题意中抽象出模型,即给定起点和终点,求在经过有限个特殊点的情况下,从起点到终点的最短距离
$\quad$我首先是想到DP,开一个二维数组dp[x][y],第一维记录当前点,第二维记录用过多少个特殊点,然后发现模型可以再进一步抽象
$\quad$考虑几个对于作出本题最关键的点:
$\quad$$\quad$1.是否存在多次遍历到一个点x,使得其y值不同
$\quad$$\quad$2.是否在第一次遍历到一个点dp[x][y]后,之后再遍历到dp[x][y]的情况不会优于此次
$\quad$$\quad$1.答案是肯定的,存在第一次遍历到x点后,从其他点绕了远路过来,虽然步数更多,但是y更小,所以我们需要开两维st数组,即st[x][y]
$\quad$$\quad$2.答案是肯定的,首次遍历到dp[x][y]后,后续的再遍历到dp[x][y],都相当于绕了远路,不会优于此次情况,所以我们可以在(x,y)出队后,就将st[x][y]设置为true,后续遍历直接跳过
$\quad$之后我们处理一下每个点能够到达的点,并在读入的时候给该点打上type标记是否为特殊点,就可以直接bfs了
#include <bits/stdc++.h>
using namespace std;
const int N=310;
vector<int> can[N]; //can数组里记录的是每个点能到达的其他点
int dp[N][N]; //dp数组,代表到达x点,经过y个特殊点的最短距离
typedef long long ll;
typedef pair<int, int> PII;
PII node[N]; //读入节点
int type[N]; //标记数组
int n,m,k,r;
ll R; //会爆int,所以用ll来存半径的平方
bool st[N][N];
bool check(int i,int j){ //判断i号点能否到j号点
int dx=node[i].first-node[j].first;
int dy=node[i].second-node[j].second;
ll d=1ll*dx*dx+1ll*dy*dy;
if(d>R) return false;
return true;
}
void init(){ //初始化函数,初始化能互相到达的点
for(int i=1;i<=n+m;i++){
for(int j=1;j<i;j++){
if(check(i,j)) can[i].push_back(j),can[j].push_back(i);
}
}
}
void bfs(){
memset(dp,0x3f,sizeof dp);
queue<PII> q;
q.push({1,0});
dp[1][0]=0;
while(q.size()){
auto t=q.front();q.pop();
int ver=t.first,used=t.second;
if(st[ver][used]) continue;
st[ver][used]=true;
for(auto x:can[ver]){
if(type[x]){ //如果是特殊点,有两种选择,走或不走,不走就是不更新数组且不压入队列
//所以我们只用处理走的情况
if(used>=k) continue; //如果走过的特殊点已经大于k,就直接剪枝
dp[x][used+1]=min(dp[x][used+1],dp[ver][used]+1); //更新dp数组
q.push({x,used+1});
}
else{
dp[x][used]=min(dp[x][used],dp[ver][used]+1); //如果是正常点,就正常更新dp数组
q.push({x,used});
}
}
}
}
int main()
{
scanf("%d%d%d%d",&n,&m,&k,&r);
R=1ll*r*r; //直接记录半径的平方,之后在check函数就不用sqrt()
for(int i=1;i<=n;i++){
scanf("%d%d",&node[i].first,&node[i].second);
type[i]=0; //打标记,0表示正常点
}
for(int i=n+1;i<=n+m;i++){
scanf("%d%d",&node[i].first,&node[i].second);
type[i]=1; //打标记,1表示特殊点
}
init();
bfs();
int ans=0x3f3f3f3f;
for(int i=0;i<=k;i++) ans=min(ans,dp[2][i]-1); //要减1的原因是,在从1号点出发时会多更新一次,因为只算中继
cout<<ans;
return 0;
}
光头哥yyds