| 试题编号： | 201403-4 |
| 试题名称： | 无线网络 |
| 时间限制： | 1.0s |
| 内存限制： | 256.0MB |
| 问题描述： | 问题描述 目前在一个很大的平面房间里有 n 个无线路由器,每个无线路由器都固定在某个点上。任何两个无线路由器只要距离不超过 r 就能互相建立网络连接。 输入格式 第一行包含四个正整数 n,m,k,r。(2 ≤ n ≤ 100,1 ≤ k ≤ m ≤ 100, 1 ≤ r ≤ 108)。 输出格式 输出只有一个数,即在指定的位置中增设 k 个路由器后,从第 1 个路 由器到第 2 个路由器最少经过的中转路由器的个数。 样例输入 5 3 1 3 样例输出 2 |
#include<iostream>
#include<vector>
#include<math.h>
#include<queue>
using namespace std;typedef struct Node{int x,y;int vr;//标记该路由器是否是真实存在的路由器 int num,k;//num记录遍历到当前节点经过的路由器个数，，k表示还剩几个可以添加的路由器个数 vector<int> con;//表示每个结点连接的路由器
}Node;Node node[300];double getDis(Node a,Node b){//判断两个路由器的距离 double x=a.x-b.x;double y=a.y-b.y;double res=sqrt(x*x+y*y);return res;
}int main(){int n,m,k,r;cin>>n>>m>>k>>r;for(int i=1;i<=n;i++){//输入n个实在的路由器 cin>>node[i].x>>node[i].y;node[i].vr=0;}for(int i=n+1;i<=n+m;i++){//继续输入m个不存在路由器的放置点（我们假设点上就存在路由器） cin>>node[i].x>>node[i].y;node[i].vr=1;}for(int i=1;i<n+m;i++){//比较每两个路由器，判断两个路由器是否相连接 for(int j=i+1;j<=n+m;j++){if(getDis(node[i],node[j])<=r){node[i].con.push_back(j);node[j].con.push_back(i);}}}int vis[300]={0}; queue<Node> q;node[1].k=k;node[1].num=0;q.push(node[1]);while(!q.empty()){//广度遍历 Node temp=q.front();q.pop();vector<int> v=temp.con;for(int i=0;i<v.size();i++){int tar=v[i];if(tar==2){cout<<temp.num;return 0;}if(vis[tar]==0){node[tar].num=temp.num+1;if(node[tar].vr==0){//若要访问的是实际存在路由器 node[tar].k=temp.k;}else{if(temp.k>0){//若访问的是不存在的路由器（即假设存在） node[tar].k=temp.k-1;//把剩下可添加的结点-1 }}vis[tar]=1;q.push(node[tar]);}}}
}更多相关CCF的试题解答，请点击>>CCF历年认证考试解答