垃圾箱分布

时间限制

200 ms

内存限制

65536 kB

代码长度限制

8000 B

判题程序

Standard

作者

陈越

大家倒垃圾的时候，都希望垃圾箱距离自己比较近，但是谁都不愿意守着垃圾箱住。所以垃圾箱的位置必须选在到所有居民点的最短距离最长的地方，同时还要保证每个居民点都在距离它一个不太远的范围内。

现给定一个居民区的地图，以及若干垃圾箱的候选地点，请你推荐最合适的地点。如果解不唯一，则输出到所有居民点的平均距离最短的那个解。如果这样的解还是不唯一，则输出编号最小的地点。

输入格式：

输入第一行给出4个正整数：N（<= 10³）是居民点的个数；M（<= 10）是垃圾箱候选地点的个数；K（<= 10⁴）是居民点和垃圾箱候选地点之间的道路的条数；D_S是居民点与垃圾箱之间不能超过的最大距离。所有的居民点从1到N编号，所有的垃圾箱候选地点从G1到GM编号。

随后K行，每行按下列格式描述一条道路：
P1 P2 Dist
其中P1和P2是道路两端点的编号，端点可以是居民点，也可以是垃圾箱候选点。Dist是道路的长度，是一个正整数。

输出格式：

首先在第一行输出最佳候选地点的编号。然后在第二行输出该地点到所有居民点的最小距离和平均距离。数字间以空格分隔，保留小数点后1位。如果解不存在，则输出“No Solution”。

输入样例1：

输出样例1：

G1

2.0 3.3

输入样例2：

输出样例2：

No Solution

详见代码，dijstra

#include <iostream>

#include <cstring>

#include <string>

#include <algorithm>

#define inf 0x3f3f3f3f

using namespace std;

int n,k,m,ds;

int e[][];

bool v[];

int d[];

int kk=;

struct node

{

    int bh;

    double p;

    int h;

    int zd;

}a[];

bool cmp(node x,node y)

{

    if(x.zd==y.zd)

    {

        if(x.p==y.p)

            return x.bh<y.bh;

        else return x.p<y.p;

    }

    else return x.zd>y.zd;//最短距离要最长

}

void dijstra(int s)

{

    int i;

    memset(v,,sizeof(v));

    v[s]=;

    int zd=inf;

    for(i=;i<=n+m;i++)

    {

        d[i]=e[s][i];

        if(!v[i]&&i<=n&&d[i]<zd)//条件要写全

            zd=d[i];

    }

    while()

    {

        int k=-;

        int mm=inf;

        for(i=;i<=n+m;i++)

        {

            if(!v[i]&&d[i]<mm)

            {

                k=i;

                mm=d[i];

            }

        }

        if(k==-) break;

        v[k]=;

        for(i=;i<=n+m;i++)

        {

            if(d[i]>d[k]+e[k][i])

            {

                d[i]=d[k]+e[k][i];

                if(!v[i]&&i<=n&&d[i]<zd)

                    zd=d[i];//把最短的距离找出来

            }

        }

    }

    int ss=;

    for(i=;i<=n;i++)

    {

        if(d[i]>ds) break;//最短路径超出范围的不要

        else ss+=d[i];

    }

    if(i==n+)

    {

        a[kk].bh =s-n;

        a[kk].h=ss;

        a[kk].zd=zd;

        a[kk++].p=ss*1.0/n;

    }

}

int main()

{

   cin>>n>>m>>k>>ds;

   int i,j;

   for(i=;i<=n+m;i++)

       for(j=;j<=n+m;j++)

       {

           if(i==j) e[i][j]=;

           else e[i][j]=inf;

       }

   for(i=;i<=k;i++)

   {

       string a,b;//G的处理

       int z;

       cin>>a>>b>>z;

       int x=,y=;

       if(a[]!='G')

       {

           int l=a.length ();

           for(int i=;i<l;i++)

           {

               x=x*+a[i]-'';

           }

       }

       else

       {

          int l=a.length ();

           for(int i=;i<l;i++)

           {

               x=x*+a[i]-'';

           }

            x+=n;

       }

       if(b[]!='G')

       {

            int l=b.length ();

           for(int i=;i<l;i++)

           {

               y=y*+b[i]-'';

           }

       }

       else

       {

           int l=b.length ();

           for(int i=;i<l;i++)

           {

               y=y*+b[i]-'';

           }

           y+=n;

       }

       if(e[x][y]>z)

       {

           e[x][y]=z;

           e[y][x]=z;

       }

   }

   for(int i=n+;i<=m+n;i++)//遍历每一个垃圾箱

   {

       dijstra(i);

   }

   if(k==) cout<<"No Solution";

   else

   {

       sort(a+,a+kk,cmp);//排个序，是kk

       if(a[].bh==)  cout<<"No Solution";

       else

       {

           cout<<"G"<<a[].bh<<endl;

            printf("%.1lf",a[].zd*1.0);cout<<" ";

           printf("%.1lf",a[].p);

       }

   }

   return ;

}

巴特西

PAT 垃圾箱分布（30分）dijstra

垃圾箱分布

最新文章

热门文章