PAT (Advanced Level) Practice - 1072 Gas Station（30 分）

PAT (Advanced Level) Practice - 1072 Gas Station（30 分）

​

题目大意：从m个加油站里面选取1个站点，让它离居民区的最近的人最远，并且所有的居民与它之间没有超出服务范围st。如果有很多个最远的加油站，输出距离所有居民区距离平均值最小的那个。如果平均值还是一样，就输出按照顺序排列加油站编号最小的那个。

解题思路：因为加油站之间也是彼此有路连接的，所以最短路径计算的时候也要把加油站算上。所以我们就是对n+m个点进行Dijkstra计算最短路径。要求计算出1~m号加油站距离其他站点的最短路径。这时候可以遍历dis数组，如果dis存在一个距离大于服务范围st的距离，那么我们就舍弃这个加油站。

取最最短的路径，这就是距离它最近的加油站mindis。如果mindis > rsdis，就是说找到了一个距离居民最小距离的加油站是更远的，那就选这个加油站，更新rsid为它的id。最后输出。

对于加油站的字符串编号的处理：如果最近居民区最大的值没有变化但是找到了一个更小的平均距离，那就选这个。我们可以根据输入的是G还是数字，如果是数字就令编号为他自己，如果是G开头的，编号设为n+G后面的数字。注意：最后输出精度控制。

AC 代码

#include#include#include#define mem(a,b) memset(a,b,sizeof a)#define ssclr(ss) ss.clear(), ss.str("")#define INF 0x3f3f3f3f#define MOD 1000000007using namespace std;typedef long long ll;const int maxn=1024;int n,m,k,st;int vis[maxn], dis[maxn];int g[maxn][maxn];stringstream ss;int inputDeal(string &s){ ssclr(ss); int id=0; if(s[0]=='G') { s=s.substr(1); ss<>id; id+=n; } else { ss<>id; } return id;}int dijkstra(int s){ dis[s]=0; while(1) { int mi=INF; s=-1; for(int i=1;i<=n+m;i++) if(!vis[i] && dis[i]>a>>b>>w; u=inputDeal(a); v=inputDeal(b); g[u][v]=g[v][u]=w; } int rsid=-1; double rsdis=-1, rsaver=0; for(int i=n+1;i<=n+m;i++) { int mindis=INF; double aver=0; mem(dis,INF), mem(vis,0); dijkstra(i); for(int i=1;i<=n;i++) { if(dis[i]>st) { mindis=-1; break; } else if(dis[i]rsdis) { rsdis=mindis; rsid=i; rsaver=aver; } else if(mindis==rsdis && aver

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。