#include<stdio.h>
#include<vector>
#include<queue>
#include<algorithm>
#include<iostream>
#define VISITED 1
#define UNVISITED 0
using namespace std;
struct node{//坐标轴上结点
int v;//表示节点
__int64 x;
__int64 y;
int mark;//标记是可以摆放的点
};
struct q_node{
int v; //表示节点
int cost; //表示当前花费结点
int value;//表示当前使用
};
vector<node> all;
vector<node> g[205];
queue <q_node> q;
int vis[205];
int inqueue[205];
void creatGraph(__int64 r){
__int64 d = r * r;
// cout << "d -> " << d << endl;
for(int i = 0 ; i < all.size() ; i++){
int v_now = i + 1;
// cout << "-------x ->" << all[i].x << " y->" << all[i].y << endl;
for(int j = i+1 ; j < all.size() ; j++){
if(d >= (all[j].x - all[i].x)* (all[j].x - all[i].x) + (all[j].y - all[i].y) * (all[j].y - all[i].y) ) {//距离公式
g[v_now].push_back(all[j]);//连接两个点
g[all[j].v].push_back(all[i]);
// cout << "x ->" << all[j].x << " y->" << all[j].y << endl;
}
}//for(j)
}//for(i)
}
int bfs(int counter){
q_node temp;
temp.cost = 0;
temp.v = 1;
temp.value = 0;
q.push(temp);//1号点入队
while(!q.empty()){
temp = q.front();
q.pop();
vis[temp.v] = VISITED;
// cout << "g[temp.v].size() - > " << g[temp.v].size() <<endl;
for(int i = 0 ; i < g[temp.v].size() ; i++){
if(g[temp.v][i].v == 2)return temp.cost;
if(temp.value <= counter && vis[g[temp.v][i].v] == UNVISITED){
q_node temp1;
temp1.value = temp.value + g[temp.v][i].mark; //加上需要消耗的路由器
temp1.cost = temp.cost + 1;
temp1.v = g[temp.v][i].v ;
if (temp1.value > counter || inqueue[temp1.v])continue;//没有后半句往往会超时,因为相同元素进入队列,虽然可以利用vis来标记,但利用inqueue来保存标记值会比较清晰
q.push(temp1);
inqueue[temp1.v] = 1;
}// if unvisited
}//for(i)
}
return 0;
}
int main(){
int n,m,k;
__int64 r;
node temp;
scanf("%d%d%d%I64d",&n,&m,&k,&r);
temp.mark = 0;//标记为固定路由器
for(int i = 1 ; i <= n ; i++){
temp.v = i;
scanf("%I64d%I64d",&temp.x,&temp.y);
all.push_back(temp);
}//for(i)
temp.mark = 1;//标记为固定路由器
for(int i = n+1 ; i <= n + m ; i++){
temp.v = i;
scanf("%I64d%I64d",&temp.x,&temp.y);
all.push_back(temp);
}//for(i)
creatGraph(r);
int result = bfs(k);
printf("%d",result);
return 0;
}
没有合适的资源?快使用搜索试试~ 我知道了~
CCF答案汇总
共70个文件
exe:35个
cpp:35个
需积分: 27 22 下载量 9 浏览量
2017-03-26
16:55:16
上传
评论
收藏 12.74MB RAR 举报
温馨提示
为历年的CCF试题答案,全个人编写,1-4题,
资源推荐
资源详情
资源评论
收起资源包目录
CCF.rar (70个子文件)
CCF
201503-1.cpp 403B
未命名1.cpp 916B
201503-4.exe 1.9MB
201609-2.cpp 1017B
201412-2.exe 1.83MB
201403-4.cpp 2KB
201604-4.cpp 2KB
201312-2.cpp 681B
201509-3.exe 1.88MB
201503-3.cpp 2KB
201409-2.cpp 802B
201312-4.cpp 842B
201509-2.exe 1.83MB
201412-4.exe 1.88MB
未命名4.cpp 646B
201512-3.exe 1.83MB
201503-3.exe 1.86MB
201609-2.exe 1.83MB
201412-1.cpp 224B
201409-1.exe 1.83MB
201412-3.cpp 2KB
vector.exe 1.87MB
201312-1.exe 1.83MB
201512-1.cpp 236B
201509-1.exe 1.83MB
201509-1.cpp 237B
201503-2.exe 1.88MB
201403-1.exe 1.83MB
201512-2.cpp 952B
201509-2.cpp 521B
201412-2.cpp 2KB
201409-3.cpp 820B
201512-1.exe 1.83MB
201409-1.cpp 395B
201509-3.cpp 1KB
201312-3.exe 1.83MB
201312-1.cpp 396B
201409-4.exe 1.58MB
201503-1.exe 1.83MB
201403-3.cpp 2KB
201509-4.cpp 2KB
未命名1.exe 1.83MB
201609-1.exe 1.83MB
201403-1.cpp 419B
201403-2.exe 1.86MB
201503-2.cpp 660B
201609-3.exe 1.87MB
201312-3.cpp 412B
201312-4.exe 1.86MB
vector.cpp 544B
201403-4.exe 1.9MB
201412-4.cpp 1KB
201512-4.cpp 1KB
201503-4.cpp 1KB
201512-2.exe 1.83MB
201409-3.exe 1.83MB
201412-1.exe 1.87MB
201509-4.exe 1.89MB
201409-2.exe 1.83MB
201409-4.cpp 2KB
201403-2.cpp 898B
未命名4.exe 1.88MB
201512-3.cpp 2KB
201403-3.exe 2.01MB
201609-1.cpp 304B
201609-3.cpp 2KB
201512-4.exe 1.92MB
201604-4.exe 1.91MB
201312-2.exe 1.84MB
201412-3.exe 1.91MB
共 70 条
- 1
资源评论
laeen
- 粉丝: 1
- 资源: 2
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功