L3-005 垃圾箱分布（30 分）

痛定思痛。 2022-05-23 11:23 142阅读 0赞

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

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

**输入格式：**

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

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

**输出格式：**

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

**输入样例1：**

4 3 11 5
    1 2 2
    1 4 2
    1 G1 4
    1 G2 3
    2 3 2
    2 G2 1
    3 4 2
    3 G3 2
    4 G1 3
    G2 G1 1
    G3 G2 2

**输出样例1：**

G1
    2.0 3.3

**输入样例2：**

2 1 2 10
    1 G1 9
    2 G1 20

**输出样例2：**

No Solution

代码：

#include<stdio.h>  
    #include<string.h>  
    #include<algorithm>  
    using namespace std;  
    const int INF=999999999;  
    int Map[1020][1020],dis[1020],visited[1020];  
    int main()  
    {  
        int i,j,n,m,k,t,p,l;  
        char x[6],y[6];  
        fill(Map[0],Map[0]+1020*1020,INF);  
        fill(dis,dis+1020,INF);  
        scanf("%d %d %d %d",&n,&m,&k,&t);  
        for(i=0;i<k;i++)  
        {  
            scanf("%s %s %d",x,y,&p);  
            int a,b;  
            if(x[0]=='G')  
            {  
                a=n+atoi(x+1);  
            }  
            else  
            {  
                a=atoi(x);  
            }  
            if(y[0]=='G')  
            {  
                b=n+atoi(y+1);  
            }  
            else  
            {  
                b=atoi(y);  
            }  
            Map[a][b]=Map[b][a]=p;  
        }  
        int flag=-1;  
        double Mindis=-1,Average=INF;  
        for(i=n+1;i<=n+m;i++)  
        {  
            double mindis=INF,average=0;  
            fill(dis,dis+1020,INF);  
            fill(visited,visited+1020,0);  
            dis[i]=0;  
            for(j=0;j<n+m;j++)  
            {  
              int index=-1,value=INF;  
              for(l=1;l<=m+n;l++)  
              {  
                  if(visited[l]==0&&dis[l]<value)  
                  {  
                      index=l;  
                      value=dis[l];  
                  }  
              }  
              if(index==-1)  
              {  
                  break;  
              }  
              visited[index]=1;  
              for(l=1;l<=n+m;l++)  
              {  
                  if(visited[l]==0&&dis[l]>dis[index]+Map[index][l])  
                  {  
                      dis[l]=dis[index]+Map[index][l];  
                  }  
              }  
            }  
              for(l=1;l<=n;l++)  
              {  
                  if(dis[l]>t)  
                  {  
                      mindis=-1;  
                      break;  
                  }  
                  if(dis[l]<mindis)  
                  {  
                      mindis=dis[l];  
                  }  
                  average+=1.0*dis[l];  
              }  
              if(mindis==-1)  
              {  
                  continue;  
              }  
              average=average/n;  
              int l1=0;  
              if(Mindis<mindis)  
              {  
                  Average=average;  
                  Mindis=mindis;  
                  flag=i;  
              }  
              else if(Mindis==mindis&&Average>average)  
              {  
                  Average=average;  
                  flag=i;  
              }  
        }  
        if(flag==-1)  
        {  
            printf("No Solution\n");  
        }  
        else  
        {  
            printf("G%d\n",flag-n);  
            printf("%.1lf %.1lf\n",Mindis,Average);  
        }  
        return 0;  
    }