摘要：
问题描述目前，一个大的平面房间中有n个无线路由器，每个无线路由器都固定在某个点上。只要距离不超过r，任何两个无线路由器都可以彼此建立网络连接。您的目标是使第一个路由器和第二个路由器之间的网络连接通过尽可能少的中转路由器。接下来，有n行，每行包含两个整数xi和yi，表示无线路由器已放置在该点上。输入中所有坐标的绝对值不得超过108，以确保输入中的坐标不同。
问题描述
目前在一个很大的平面房间里有 n 个无线路由器,每个无线路由器都固定在某个点上。任何两个无线路由器只要距离不超过 r 就能互相建立网络连接。
除此以外,另有 m 个可以摆放无线路由器的位置。你可以在这些位置中选择至多 k 个增设新的路由器。
你的目标是使得第 1 个路由器和第 2 个路由器之间的网络连接经过尽量少的中转路由器。请问在最优方案下中转路由器的最少个数是多少?
除此以外,另有 m 个可以摆放无线路由器的位置。你可以在这些位置中选择至多 k 个增设新的路由器。
你的目标是使得第 1 个路由器和第 2 个路由器之间的网络连接经过尽量少的中转路由器。请问在最优方案下中转路由器的最少个数是多少?
输入格式
第一行包含四个正整数 n,m,k,r。(2 ≤ n ≤ 100,1 ≤ k ≤ m ≤ 100, 1 ≤ r ≤ 108)。
接下来 n 行,每行包含两个整数 xi 和 yi,表示一个已经放置好的无线 路由器在 (xi, yi) 点处。输入数据保证第 1 和第 2 个路由器在仅有这 n 个路由器的情况下已经可以互相连接(经过一系列的中转路由器)。
接下来 m 行,每行包含两个整数 xi 和 yi,表示 (xi, yi) 点处可以增设 一个路由器。
输入中所有的坐标的绝对值不超过 108,保证输入中的坐标各不相同。
接下来 n 行,每行包含两个整数 xi 和 yi,表示一个已经放置好的无线 路由器在 (xi, yi) 点处。输入数据保证第 1 和第 2 个路由器在仅有这 n 个路由器的情况下已经可以互相连接(经过一系列的中转路由器)。
接下来 m 行,每行包含两个整数 xi 和 yi,表示 (xi, yi) 点处可以增设 一个路由器。
输入中所有的坐标的绝对值不超过 108,保证输入中的坐标各不相同。
输出格式
输出只有一个数,即在指定的位置中增设 k 个路由器后,从第 1 个路 由器到第 2 个路由器最少经过的中转路由器的个数。
样例输入
5 3 1 3
0 0
5 5
0 3
0 5
3 5
3 3
4 4
3 0
0 0
5 5
0 3
0 5
3 5
3 3
4 4
3 0
样例输出
2
早期题目真是水啊，压根没考虑选K个，试着直接写了个dij跑N+M全部的点，就100分了= =
本来想的是先跑，然后贪心的删除点，结果试了试直接就A了。
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define inf 0x3f3f3f3f 4 #define LL long long 5 #define pii pair<int,int> 6 #define x first 7 #define y second 8 pii p[222]; 9 int n,m,sum,k; 10 LL r; 11 int e[205][205]; 12 bool ok(int i,int j){ 13 return ((LL)p[i].x-p[j].x)*(p[i].x-p[j].x)+((LL)p[i].y-p[j].y)*(p[i].y-p[j].y)<=r*r; 14 } 15 int d[205]; 16 bool vis[205]; 17 int dij(){ 18 memset(d,inf,sizeof(d)); 19 memset(vis,0,sizeof(vis)); 20 d[1]=0; 21 for(int i=1;i<=sum;++i){ 22 int tar=0; 23 for(int j=1;j<=sum;++j){ 24 if(!vis[j]&&d[j]<d[tar])tar=j; 25 } 26 vis[tar]=1; 27 for(int j=1;j<=sum;++j){ 28 if(!vis[j]&&e[tar][j]&&d[j]>d[tar]+1)d[j]=d[tar]+1; 29 } 30 } 31 //for(int i=1;i<=sum;++i)cout<<d[i]<<' '; 32 return d[2]-1; 33 } 34 int main(){ 35 memset(e,inf,sizeof(inf)); 36 cin>>n>>m>>k>>r;sum=n+m; 37 for(int i=1;i<=sum;++i)e[i][i]=0,cin>>p[i].first>>p[i].second; 38 for(int i=1;i<=sum;++i){ 39 for(int j=i+1;j<=sum;++j){ 40 if(ok(i,j)) e[i][j]=e[j][i]=1; 41 } 42 } 43 cout<<dij(); 44 return 0; 45 }