Solution题目要求选择建立一个最佳的加油站前提是这个加油站必须能连通所有的居民住所并使得所有居民住所中距离这个加油站最近的距离尽可能远若有多个选择则选择平均距离最小的加油站若仍然有多个选择则选择序号较小的加油站。代码如下//单源最短路#includeiostream#includemath.h#includealgorithm#includeiomanip#includestring#includevector#defineMAX 1500#defineINF 0x3f3f3f3fusing namespace std;structgas_station{doubledis;//距离加油站最近的距离加油站的距离doubleavg_dis;//平均距离intindex;};vectorgas_stationsta;intvisit[MAX];//访问数组doubledis[MAX];//记录最短距离intmp[MAX][MAX];intn,m;//n为结点数m为加油站数intk,d;//k为边数d为gas station最大服务范围voiddijkstra(ints){//dijkstrafor(inti0;iMAX;i){//初始化dis和visitvisit[i]0;dis[i]INF;}dis[s]0;for(inti1;inm;i){intminvINF;intu-1;for(intj1;jnm;j){if(dis[j]minvvisit[j]0){minvdis[j];uj;}}if(u-1){return;}visit[u]1;for(intv1;vnm;v){if(visit[v]0mp[u][v]!INF){if(dis[v]dis[u]mp[u][v]){dis[v]dis[u]mp[u][v];}}}}}intto_index(string s){//将字符串转为下标intindex0;for(inti0;is.length();i){if(s[i]!G)indexindex*10s[i]-0;}if(s[0]G){indexn;}returnindex;}boolcmp(gas_station a,gas_station b){if(a.disb.dis){returntrue;}elseif(a.disb.dis){if(a.avg_disb.avg_dis){returntrue;}elseif(a.avg_disb.avg_dis){returna.indexb.index;}}returnfalse;}intmain(){for(inti0;iMAX;i){//初始化图for(intj0;jMAX;j){mp[i][j]INF;}}cinnmkd;string s1,s2;inta,b;intlen;for(inti0;ik;i){//读入数据cins1s2len;ato_index(s1);bto_index(s2);mp[a][b]mp[b][a]len;}for(intin1;inm;i){intminlINF;doubletotal_dis0.0;dijkstra(i);bool flagtrue;for(intj1;jn;j){if(dis[j]d){flagfalse;break;}total_disdis[j];if(dis[j]minl){minldis[j];}}if(flag){gas_station temp;temp.disminl;temp.avg_distotal_dis/n;temp.indexi;sta.push_back(temp);}}if(sta.empty()){coutNo Solution;}else{sort(sta.begin(),sta.end(),cmp);coutGsta[0].index-nendl;coutfixedsetprecision(1)sta[0].dis ;coutfixedsetprecision(1)sta[0].avg_dis;}return0;}