2 sinat 33185026 sinat_33185026 于 2016.03.29 11:29 提问

CCF 无线网络问题 求代码出现的问题
ccf

图片说明

 #include<iostream>
#include<cmath> 
#include<cstring>
#include<queue>

using namespace std;

int d[100][100];

struct plot
{
    long long x;
    long long y;
    int vis;
    long long dis;
}p[200];

int main()
{
    memset(d,0,sizeof(d));//d[]赋值全0 
    int m,n,k,num,t,f,knum,tt;
    long long r;

    //输入数据 
    cin>>n>>m>>k>>r;
    queue<int> q;
    for(int i=0;i<n+m;i++)
    {
     cin>>p[i].x>>p[i].y;
     p[i].vis=0;
     p[i].dis=pow(10,8)+1;
     } 


    //建立可达矩阵 
    for(int i=0;i<n+m;i++)
       for(int j=i+1;j<n+m;j++)
           {
            if((p[i].x-p[j].x)*(p[i].x-p[j].x)+(p[i].y-p[j].y)*(p[i].y-p[j].y)<=r*r)
            {
                d[i][j]=d[j][i]=1;
            }

           }


    //运用BFS 
    knum=0;
    num=0;
    q.push(0);
    p[0].dis=0;
    while(!q.empty())
    {
        t=q.front();
        q.pop();
        p[t].vis=0;
        if(t>n)//如果被访问的结点是需要增设的,则需要的增设的数量+1 
        knum++;
        f=0;
        for(int i=1;i<n+m;i++)
           {
            if((d[t][i]==1)&&(p[i].vis==0))//如果该结点有可用邻接点而且该点是已存在的结点或者是需要增设的结点但是目前需要增设的数量小于上限 
            {
                if(i<=n||((i>n)&&(knum<k)))
                {

                    if(p[i].dis>p[t].dis+1)//如果原先从原点到该结点的距离大于通过t结点到达该结点的距离+1,则更改该结点的距离变量,并将其入队列 
                    {
                      q.push(i);
                       p[i].vis=1;
                      p[i].dis=p[t].dis+1;
                      f=1;

                    }

                }

            }


           }
        if(f==0&&t>n)//如果该结点没有可用的邻接点,而且是需要增设的,那么需要的增设的数量-1 
          knum--;

    }

    cout<<p[1].dis-1<<endl;//输出从源结点到目的结点的距离 


}
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!