水~。
题意
有N所居民房、M个加油站待建点以及K条无向边。现在要从M个加油站待建点中选出一个来建造加油站，使得该加油站距离最近的居民房尽可能远，且必须保证所有房子与该加油站的距离都不超过给定的服务范围DS。现在给出N、M、K、DS，以及K条无向边的端点及边权，输出应当选择的加油站编号、与该加油站最近的居民房的距离、该加油站距离所有居民房的平均距离。
如果有多个最近距离相同的解，那么选择平均距离最小的；如果平均距离也相同，则选择编号最小的。
思路
- 首先要解决顶点的编号问题。对居民房来说，输入的编号就是它的编号；对加油站来说，输入的编号去掉最前面的'G'后就是它的编号，但是为了与居民房区分，需要把加油站的编号加上居民房的个数来作为加油站的编号。例如，如果有5个居民房、3个加油站，那么居民房的编号就是1 ~ 5，而加油站的编号就是6 ~ 8。因此需要按字符串的形式读入题目给定的编号，然后根据字符串首位是否为'G'来判断如何处理编号。
- 枚举每个加油站，使用Dijkstra算法来得到所有居民房距离该加油站的最短距离。但是要注意，本题中所有无向边都是真实存在的，也就是说，所有待选加油站也需要作为实际的顶点参与Djkstra算法的计算。因此，Djkstra 算法中的顶点编号范围应当是1 ~ (n+ m)。在得到某个加油站的数组d[MAXV]后，需要获取其中最小的元素(即该加油站与居民房的最近距离)及计算所有居民房(1 ~ n)与加油站的平均距离，过程中如果出现某个d[i]大于DS，则说明存在居民房与该待选加油站的距离超过了服务范围，该待选加油站不合格。接下来，如果该最近距离比当前最大的最近距离还大，则更新最大的最近距离；如果最近距离相同，则更新最小的平均距离。
注意点
本题是要使最近距离最大，因此定义存放最大的最近距离的变量时，其初值必须设为一个较小的数。
const int N=1011;
vector<PII> g[N];
int dist[N];
bool vis[N];
int n,m,k,Ds;
int get(string s)
{
if(s[0] == 'G') return n+stoi(s.substr(1));
else return stoi(s);
}
void dijkstra(int st)
{
memset(dist,0x3f,sizeof dist);
memset(vis,0,sizeof vis);
priority_queue<PII,vector<PII>,greater<PII>> heap;
dist[st]=0;
heap.push({0,st});
while(heap.size())
{
int t=heap.top().se;
heap.pop();
if(vis[t]) continue;
vis[t]=true;
for(int i=0;i<g[t].size();i++)
{
int j=g[t][i].fi,w=g[t][i].se;
if(dist[j] > dist[t] + w)
{
dist[j]=dist[t]+w;
heap.push({dist[j],j});
}
}
}
}
int main()
{
cin>>n>>k>>m>>Ds;
while(m--)
{
string a,b;
int w;
cin>>a>>b>>w;
int ta=get(a),tb=get(b);
g[ta].pb({tb,w});
g[tb].pb({ta,w});
}
int ans=0;
int bestdist=0,minsum=INF;
for(int i=n+1;i<=n+k;i++)
{
dijkstra(i);
bool ok=true;
for(int j=1;j<=n;j++)
if(dist[j] > Ds)
{
ok=false;
break;
}
if(!ok) continue;
int mindist=INF;
int sum=0;
for(int j=1;j<=n;j++)
{
mindist=min(mindist,dist[j]);
sum+=dist[j];
}
if(mindist > bestdist)
{
ans=i;
bestdist=mindist;
minsum=sum;
}
else if(mindist == bestdist && sum < minsum)
{
ans=i;
minsum=sum;
}
}
if(ans == 0) puts("No Solution");
else
{
cout<<'G'<<ans-n<<endl;
printf("%.1f %.1f
",(double)bestdist,(double)minsum/n+eps);
}
//system("pause");
return 0;
}