7-1 垃圾箱分布（30 分)-PAT-最短路-axuhongbo的个人博客

7-1 垃圾箱分布（30 分)

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

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

输入格式：

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

随后 $K$ 行，每行按下列格式描述一条道路：

P1 P2 Dist

其中P1和P2是道路两端点的编号，端点可以是居民点，也可以是垃圾箱候选点。Dist是道路的长度，是一个正整数。

输出格式：

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

输入样例1：

输出样例1：

G1
2.0 3.3

输入样例2：

2 1 2 10
1 G1 9
2 G1 20

输出样例2：

No Solution

#include <iostream>
#include<bits/stdc++.h>
using namespace std;
const int inf  =0x3f3f3f3f;
map<string,int>mp;
map<int,string>name;
int f,nn;
int dist[12600],vis[12600];
int dist2[11600],dist3[12600],n;
int tu[16100][16100];
int cnt =0;
int Kill[600];
int id(string h){

   if(h[0]=='G'){

     string j =h.substr(1);
     int num = atoi(j.c_str());
     return num+n;
   }
   else{

     string j =h;
     int num = atoi(j.c_str());
     return num;
   }
}
int pre[600],Num[600];
void dijkstra(int s){

  memset(dist,inf,sizeof dist);
 // memset(dist2,0,sizeof dist2);
 // memset(dist3,0,sizeof dist3);
 // memset(Num,0,sizeof Num);
  memset(vis,0,sizeof vis);
 // memset(pre,-1,sizeof pre);
  dist[s] =0;
 // dist3[s] =Kill[s];
  while(1){

    int x =-1,Min =inf;
    for(int i=1;i<=nn+n;i++)
    {
        if(!vis[i]&&Min>dist[i]){

            Min  = dist[i];
            x  =i;
        }
    }
    if(x==-1)break;
    vis[x] = 1;
    for(int i=1;i<=nn+n;i++){

        if(!vis[i]){

            if(dist[i]>=dist[x]+tu[x][i]){

                dist[i] = dist[x]+tu[x][i];
             //   dist2[i] = dist2[x]+w[x][i];
               //dist2[i] = dist2[x]+1;
              //  Num[i] = 1;
             //  dist3[i] = dist3[x]+Kill[x];
                // pre[i] = x;
            }

    }

  }
}
}

int main()
{

    int m,s,d,M;
    cin>>n>>nn>>m>>M;
  //  string ss,dd;
  //  cin>>ss>>dd;

  // n = n+nn;
    for(int i=0;i<=n+nn;i++){

          for(int j=0;j<=n+nn;j++){

            if(i==j)continue;
            tu[i][j] = inf;

          }
    }
//    int u,v,l,ww;
//    for(int i=1;i<=n+nn;i++){
//
//        cin>>Kill[i];
//
//    }
//    for(int i=1;i<=m;i++){
//
//        string s1,s2;
//        int num;
//        cin>>s1>>s2>>num;
//        int i1 = id(s1);
//        int i2 = id(s2);
//        tu[i1][i2]= tu[i2][i1] = num;
//    }
    for(int i=1;i<=m;i++){

        string uu,vv;
        int l,u,v;
        cin>>uu>>vv>>l;
        u = id(uu);
        v = id(vv);
       // cout<<u<<" "<<v<<endl<<endl;
        tu[u][v] = tu[v][u] = min(tu[u][v],l);
      //  w[u][v]= w[v][u] = ww;
    }
    double A =0,AA = inf;
    int id  =-1;
    for(int i=1;i<=nn;i++){

        f = 1;
        dijkstra(n+i);
        double ans =0;
        double pp =inf;
//        cout<<"i:"<<i<<endl;
//        for(int j=1;j<=n;j++){
//
//            cout<<dist[j]<<" ";
//        }
//        cout<<endl;
        for(int j=1;j<=n;j++){

            if(dist[j]>M){
                f =0;
                break;
            }
            pp = min(pp,1.0*dist[j]);
            ans+=dist[j];
        }
        if(f){
           if(pp>A){

           A = pp;
           AA = ans;
           id = i;
           }
           else if(pp==A&&ans<AA){

               A = pp;
               AA = ans;
                id =i;
            }
        }
    }
    if(id==-1){

        printf("No Solution\n");
    }
    else{

        printf("G%d\n%.1f %.1f",id,A,AA/n);
    }









    return 0;
}