PAT.A1072 Gas Station

PAT.A1072 Gas Station

​​返回目录​​

题意

有N所居民房、M个加油站待建点以及K条无向边。现在要从M个加油站待建点中选出一个来建造加油站，使得该如油站距离最近的居民房尽可能远，且必须保证所有房子与该加油站的距离都不超过给定的服务范围DS。现在给出N、M、K、DS，以及K条无向边的端点及边权，输出应当选择的加油站编号、与该加油站最近的居民房的距离、该加油站距离所有居民房的平均距离。如果有多个最近距离相同的解，那么选择平均距离最小的:如果平均距离也相同，则选择编号最小的。

样例（可复制）

4 3 11 51 2 21 4 21 G1 41 G2 32 3 22 G2 13 4 23 G3 24 G1 3G2 G1 1G3 G2 2

//outputG12.0 3.3

2 1 2 101 G1 92 G1 20

//output

注意点

本题思路如下：先对每个加油站都进行一次最短路径搜索，每次后都能得到每个加油站到每个房屋的距离，然后进行统计最近的距离，平均距离，最远距离，根据题意找到最优的加油站。本题需要解决编号问题，笔者的做法是对n个房屋的编号为1-n，对m个加油站的编号为n+1-n+m。其中使用了string处理较为方便，stoi()函数为c++11后STL的内置函数，可以将string转换为int。在进行Dijkstra时，需要注意每次都要对dis和vis进行初始化。除此之外还需要注意，循环找最短路径的条件不能写成while(!vis[i]),这是因为要得到所有房屋到加油站的距离。

#includeusing namespace std;const int N=1020;int n,m,k,ds;//房子数量，候选加油站数量，边数，可支持的最远距离int G[N][N];//图 int dis[N];//每个房屋到指定加油站的距离bool vis[N];//标记是否访问过int best=-1;//最优加油站编号double minavg=INT_MAX,maxdis=-1;//最小平均距离，距离最近的房屋中最远的那个int getid(string s){ if(s[0]=='G'){ s.erase(s.begin()); return stoi(s)+n; } return stoi(s);}void Dijkstra(int root){ fill(dis,dis+N,INT_MAX); memset(vis,false,sizeof(vis)); dis[root]=0; for(int i=0;idis[j]){ minn=dis[j]; v=j; } } vis[v]=true; for(int j=0;jdis[v]+G[v][j]){ dis[j]=dis[v]+G[v][j]; } } }}int main(){ cin>>n>>m>>k>>ds; while(k--){ string a,b; int dd; cin>>a>>b>>dd; int id1=getid(a),id2=getid(b); G[id1][id2]=G[id2][id1]=dd; } for(int i=n+1;i<=n+m;i++){ Dijkstra(i);//对每个加油站都进行一次找最短路径 int maxx=-1; double avg=0,minn=INT_MAX; for(int j=1;j<=n;j++){ avg+=dis[j]*1.0; maxx=max(dis[j],maxx); minn=min(dis[j]*1.0,minn); } if(maxx<=ds&&minn>maxdis){ best=i; maxdis=minn; minavg=avg; }else if(maxx<=ds&&minn==maxdis&&avg

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