最短路中部分点只能从中任意选取K个问题-白红宇

最短路中部分点只能从中任意选取K个问题

阅读量：5982 次

发布时间：2019-06-20

本文共 1130 字，大约阅读时间需要 3 分钟。

题意：给N个点，还有另外m个点（其中只能选K个），求最短路。

思路：在SPFA的基础上，用一个数组来统计，在某点入队时（要拓展其他点了）,若该点是m个点中的，则count【i】=原来的+1；若不是，则继承原来的。出队时候限制一下，若大于K了，就停止拓展。

原题：目前在一个很大的平面房间里有 n 个无线路由器，每个无线路由器都

固定在某个点上。任何两个无线路由器只要距离不超过 r 就能互相建立网

络连接。

除此以外，另有 m 个可以摆放无线路由器的位置。你可以在这些位置

中选择至多 k 个增设新的路由器。

你的目标是使得第 1 个路由器和第 2 个路由器之间的网络连接经过尽

量少的中转路由器。请问在最优方案下中转路由器的最少个数是多少？

#include
    
     #include
     
      #include
      
       using namespace std; struct points{     int x,y;};const int inf=0x3f3f3f3f;int n,m,k,r;vector
       
        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

q; for(int i=0;i

k)continue; //限制，某点出队的次数 for(int i=0;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

>temp.x>>temp.y; v.push_back(temp); } get_gra(); spfa(); cout<

转载于:https://www.cnblogs.com/yezekun/p/3925790.html

你可能感兴趣的文章

启动 OracleMTSRecoveryServic 服务。错误 1：函数不正确。