Solution：
题目要求：选择建立一个最佳的加油站，前提是这个加油站必须能连通所有的居民住所，并使得所有居民住所中距离这个加油站最近的距离尽可能远，若有多个选择，则选择平均距离最小的加油站，若仍然有多个选择，则选择序号较小的加油站。
代码如下：
//单源最短路#include<iostream>#include<math.h>#include<algorithm>#include<iomanip>#include<string>#include<vector>#defineMAX 1500#defineINF 0x3f3f3f3fusing namespace std;structgas_station{doubledis;//距离加油站最近的距离加油站的距离doubleavg_dis;//平均距离intindex;};vector<gas_station>sta;intvisit[MAX];//访问数组doubledis[MAX];//记录最短距离intmp[MAX][MAX];intn,m;//n为结点数，m为加油站数intk,d;//k为边数，d为gas station最大服务范围voiddijkstra(ints){//dijkstrafor(inti=0;i<MAX;i++){//初始化dis和visitvisit[i]=0;dis[i]=INF;}dis[s]=0;for(inti=1;i<=n+m;i++){intminv=INF;intu=-1;for(intj=1;j<=n+m;j++){if(dis[j]<minv&&visit[j]==0){minv=dis[j];u=j;}}if(u==-1){return;}visit[u]=1;for(intv=1;v<=n+m;v++){if(visit[v]==0&&mp[u][v]!=INF){if(dis[v]>dis[u]+mp[u][v]){dis[v]=dis[u]+mp[u][v];}}}}}intto_index(string s){//将字符串转为下标intindex=0;for(inti=0;i<s.length();i++){if(s[i]!='G')index=index*10+s[i]-'0';}if(s[0]=='G'){index+=n;}returnindex;}boolcmp(gas_station a,gas_station b){if(a.dis>b.dis){returntrue;}elseif(a.dis==b.dis){if(a.avg_dis<b.avg_dis){returntrue;}elseif(a.avg_dis==b.avg_dis){returna.index<b.index;}}returnfalse;}intmain(){for(inti=0;i<MAX;i++){//初始化图for(intj=0;j<MAX;j++){mp[i][j]=INF;}}cin>>n>>m>>k>>d;string s1,s2;inta,b;intlen;for(inti=0;i<k;i++){//读入数据cin>>s1>>s2>>len;a=to_index(s1);b=to_index(s2);mp[a][b]=mp[b][a]=len;}for(inti=n+1;i<=n+m;i++){intminl=INF;doubletotal_dis=0.0;dijkstra(i);bool flag=true;for(intj=1;j<=n;j++){if(dis[j]>d){flag=false;break;}total_dis+=dis[j];if(dis[j]<minl){minl=dis[j];}}if(flag){gas_station temp;temp.dis=minl;temp.avg_dis=total_dis/n;temp.index=i;sta.push_back(temp);}}if(sta.empty()){cout<<"No Solution";}else{sort(sta.begin(),sta.end(),cmp);cout<<"G"<<sta[0].index-n<<endl;cout<<fixed<<setprecision(1)<<sta[0].dis<<" ";cout<<fixed<<setprecision(1)<<sta[0].avg_dis;}return0;}
)
