共计 2992 个字符，预计需要花费 8 分钟才能阅读完成。
题目粗心:
当初有 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;
}
正文完
