首页 > 代码库 > 最短路中部分点只能从中任意选取K个问题
最短路中部分点只能从中任意选取K个问题
题意:给N个点,还有另外m个点(其中只能选K个),求最短路。
思路:在SPFA的基础上,用一个数组来统计,在某点入队时(要拓展其他点了),若该点是m个点中的,则count【i】=原来的+1;若不是,则继承原来的。出队时候限制一下,若大于K了,就停止拓展。
原题:目前在一个很大的平面房间里有 n 个无线路由器,每个无线路由器都
固定在某个点上。任何两个无线路由器只要距离不超过 r 就能互相建立网
络连接。
除此以外,另有 m 个可以摆放无线路由器的位置。你可以在这些位置
中选择至多 k 个增设新的路由器。
你的目标是使得第 1 个路由器和第 2 个路由器之间的网络连接经过尽
量少的中转路由器。请问在最优方案下中转路由器的最少个数是多少?
#include<iostream> #include<vector> #include<queue> using namespace std; struct points { int x,y; }; const int inf=0x3f3f3f3f; int n,m,k,r; vector<points>v; //点 int map[205][205]; //图 int dis(points a,points b) //距离 { return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y); } void get_gra() //建图 { for(int i=0;i<n+m;i++) { for(int j=i+1;j<n+m;j++) { if(dis(v[i],v[j])<=r*r) { map[j][i]=map[i][j]=1; } else { map[i][j]=map[j][i]=inf; } } } } int inq[205]; int d[205]; int count[205]; void spfa() { queue<int>q; for(int i=0;i<n+m;i++) { count[i]=inq[i]=0; d[i]=inf; } q.push(0);inq[0]=1;d[0]=0; while(!q.empty()) { int cur=q.front(); q.pop();inq[cur]=0; if(count[cur]>k)continue; //限制,某点出队的次数 for(int i=0;i<n+m;i++) { if(d[i]>d[cur]+map[cur][i]) { d[i]=d[cur]+map[cur][i]; if(inq[i]==0) { if(i>=n) //被限制次数的点,若是经过该点(该点入队),则加 { count[i]=count[cur]+1; } else //一般的点继承 { count[i]=count[cur]; } inq[i]=1; q.push(i); } } } } } int main() { while(cin>>n>>m>>k>>r) { v.clear(); points temp; for(int i=0;i<n+m;i++) { cin>>temp.x>>temp.y; v.push_back(temp); } get_gra(); spfa(); cout<<d[1]-1<<endl; //问的是中间有几个点 } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。