题目粗心:
当初有N座房子,M个加油站待抉择点,K条边,当初要在M个加油站待抉择点抉择一个加油站进去,要求满足间隔N个房子尽可能远然而同时也得保障房子均在服务范畴Ds中,如果有多个抉择均匀间隔最小的,如果还有多个，抉择编号最小的 。
算法思路：
典型的最短距离求解问题,应用Dijkstra算法实现即可,这里得先理解咱们须要取得什么样的信息,咱们通过Dijkstra算法能够取得以后加油站到所有房子的最短距离，由dis数组保留,而后咱们须要取得以下3个信息：
1.所有加油站中距离房子最短的间隔并且处于服务范畴内中的最大间隔(对应于加油站间隔N个房子尽可能远)2.以后加油站到所有房子的均匀最短距离,在1中的间隔相等的时候抉择最小的(通过dis数组能够轻易取得)3.加油站的编号(这个最好失去,每次执行Dijkstra算法的终点就是,依据1和2进行更新，否则不更新)晓得以上三点后,咱们就能够进行如下操作:
1、每一个加油站节点GM的节点的编号为N+M。
2、对于M个待选加油站咱们每次都进行 Dijkstra算法取得以后加油站到其余点的最短距离,保留在dis数组中,而后判断以后加油站间隔房子的间隔是否有超过服务范畴的,如果没有那么就记录以后加油站到房子的最短距离local_min_dis、到所有房子的均匀最短距离(这里应用总长度来代替)total_dis以及以后节点编号i，最初再重置visited数组就好,如果有超过范畴的，间接pass以后加油站。
3、如果以后的最短距离比全局最短距离更大或者相等然而总间隔比全局总间隔更小，更新全局最短距离global_max_dis，总间隔result_total_dis和站点编号result_index。
4、如果所有的加油站都超过服务返回就输入No Solution，这里应用result_index是否等于-1来进行判断。
留神点：
- 1、每一次获取最短门路须要初始化visited
- 2、输入节点编号的时候得减去N
- 3、获取最短门路的时候，须要进行N+M次，也即是得加油站自身也是一个实在存在的地点，能够用来优化最短门路。
- 4、最初保留1位小数输入的最短均匀间隔输入值和测试用例不一样然而在提交过程中没有任何问题。
- 5、最初一个测试点呈现运行时谬误是输出外面有G10,得取G前面的字符串而后转化为数字,而不是间接取前面一位，呈现段谬误,是因为maxn设置太小了,呈现答案谬误阐明，判断输出是否为G结尾的办法出错,不能应用字符串的长度进行判断,只能用第一个字符是否为G来进行判断,因为数子是从1位到4位变动,G前面数字是从1到2位变动的,或者maxn设置为了1010及其以下的数字,最小得设置为1011能力通过.
提交后果:
AC代码：
#include<cstdio>#include<vector>#include<algorithm>#include<string>#include<cstring>#include<iostream>using namespace std;int N,M,K,Ds;//房子数目，候选站点数目，路线数目，最大服务间隔int G[1200][1200];// 边权,示意间隔bool visited[1200];// 拜访标记数组 int dis[1200];// 每一个居民间隔终点的最短距离void Dijkstra(int start){ // 初始化 fill(dis,dis+1200,0x3fffffff); dis[start] = 0; // 循环N+M次 for(int i=1;i<=N+M;++i){ // 首先从所有未拜访的点中找到间隔终点最小的点 int nearest,minDis=0x3fffffff; for(int j=1;j<=N+M;++j){ if(!visited[j]&&minDis>dis[j]){ nearest = j; minDis = dis[j]; } } if(minDis==0x3fffffff) return ;// 没有找到，阐明其余点不再连通 // 优化借助nearest到其余未拜访的点的间隔 visited[nearest] = true; for(int j=1;j<=N+M;++j){ if(!visited[j]&&G[nearest][j]!=0&&dis[j]>dis[nearest]+G[nearest][j]){ dis[j] = dis[nearest]+G[nearest][j]; } } } }int main(){ scanf("%d %d %d %d",&N,&M,&K,&Ds); string a,b; int dist; int index_a,index_b; for(int i=0;i<K;++i){ cin>>a>>b>>dist; if(a[0]=='G'){ index_a = stoi(a.substr(1))+N;// G1为N+1 }else { index_a = stoi(a); } if(b[0]=='G'){ index_b = stoi(b.substr(1))+N; }else{ index_b = stoi(b); } G[index_a][index_b] = G[index_b][index_a] = dist; } // 求出每一个站点作为终点，其余房子间隔它的最短距离 int result_index = -1;// 最优加油站 int global_max_dis = -1;// 所有最短距离中的最大间隔 int result_total_dis = 0x3fffffff;// 最优加油站到所有居民房的总间隔 for(int i=N+1;i<=N+M;++i){ memset(visited,0,sizeof(visited));// 每一次遍历都得初始化拜访标记数组 Dijkstra(i); // 取得居民房到以后结点的最短距离后，须要取得以后加油站到所有居民房的最短距离，均匀最短距离(这里应用总间隔代替) int local_min_dis = 0x3ffffff; int total_dis = 0; bool isOutOfRange = false; for(int j=1;j<=N;++j){ if(dis[j]>Ds){ isOutOfRange = true; break; } local_min_dis = min(local_min_dis,dis[j]); total_dis += dis[j]; } if(isOutOfRange) continue;// 以后加油站无奈为所有居民提供服务 if(global_max_dis<local_min_dis){ result_index = i; global_max_dis = local_min_dis; result_total_dis = total_dis; }else if(global_max_dis==local_min_dis&&result_total_dis>total_dis){ result_index = i; result_total_dis = total_dis; } } if(result_index==-1){ printf("No Solution"); return 0; } printf("G%d\n",result_index-N); printf("%.1lf %.1lf",global_max_dis*1.0,result_total_dis*1.0/N); return 0;}