题目链接：点击打开链接
题目大意：从m个加油站里面选取1个站点，让它离居民区的最近的人最远，并且所有的居民与它之间没有超出服务范围st。如果有很多个最远的加油站，输出距离所有居民区距离平均值最小的那个。如果平均值还是一样，就输出按照顺序排列加油站编号最小的那个。
解题思路：因为加油站之间也是彼此有路连接的，所以最短路径计算的时候也要把加油站算上。所以我们就是对n+m个点进行Dijkstra计算最短路径。要求计算出1~m号加油站距离其他站点的最短路径。这时候可以遍历dis数组，如果dis存在一个距离大于服务范围st的距离，那么我们就舍弃这个加油站。
取最最短的路径，这就是距离它最近的加油站mindis。如果mindis > rsdis，就是说找到了一个距离居民最小距离的加油站是更远的，那就选这个加油站，更新rsid为它的id。最后输出。
对于加油站的字符串编号的处理：如果最近居民区最大的值没有变化但是找到了一个更小的平均距离，那就选这个。我们可以根据输入的是G还是数字，如果是数字就令编号为他自己，如果是G开头的，编号设为n+G后面的数字。注意：最后输出精度控制。
AC 代码
usingnamespacestd; typedeflonglongll; constintmaxn=1024; intn,m,k,st; intvis[maxn], dis[maxn]; intg[maxn][maxn]; stringstreamss; intinputDeal(string&s) { ssclr(ss); intid=0; if(s[0]=='G') { s=s.substr(1); ss<<s; ss>>id; id+=n; } else { ss<<s; ss>>id; } returnid; } intdijkstra(ints) { dis[s]=0; while(1) { intmi=INF; s=-1; for(inti=1;i<=n+m;i++) if(!vis[i] &&dis[i]<mi) mi=dis[i], s=i; if(s==-1) return0; vis[s]=1; for(inti=1;i<=n+m;i++) if(!vis[i] &&mi+g[s][i]<dis[i]) dis[i]=mi+g[s][i]; } } intmain() { mem(g,INF); stringa,b; intw,u,v; scanf("%d%d%d%d",&n,&m,&k,&st); for(inti=0;i<k;i++) { cin>>a>>b>>w; u=inputDeal(a); v=inputDeal(b); g[u][v]=g[v][u]=w; } intrsid=-1; doublersdis=-1, rsaver=0; for(inti=n+1;i<=n+m;i++) { intmindis=INF; doubleaver=0; mem(dis,INF), mem(vis,0); dijkstra(i); for(inti=1;i<=n;i++) { if(dis[i]>st) { mindis=-1; break; } elseif(dis[i]<mindis) mindis=dis[i]; aver+=dis[i]; } if(mindis==-1) continue; aver/=n; if(mindis>rsdis) { rsdis=mindis; rsid=i; rsaver=aver; } elseif(mindis==rsdis&&aver<rsaver) { rsid=i; rsaver=aver; } } if(rsid==-1) puts("No Solution"); elseprintf("G%d\n%.1f %.1f\n",rsid-n,rsdis,rsaver+1e-4); return0; }
