题意：从m个加油站里面选取1个站点，使得其离住宅的最近距离mindis尽可能地远，并且离所有住宅的距离都在服务范围ds之内。
如果有很多相同mindis的加油站，输出距所有住宅平均距离最小的那个。
如果平均值还是一样，就输出按照顺序排列加油站编号最小的。
分析：
加油站之间也是彼此有路连接的，所以最短路径计算的时候也要把加油站算上，是双向边，所以边的数组大小得开两倍。
加油站编号记为n+1~n+m，对这些点用dijkstra计算最短路径即可，这里顺便在dijkstra中进行了剪枝处理，不剪枝也没事。
#include <iostream> #include <cstdio> #include <algorithm> #include <string.h> #include <queue> #define INF 0X3f3f3f3f using namespace std; /* 从m个加油站里面选取1个站点，使得其离住宅的最近距离mindis尽可能地远，并且离所有住宅的距离都在服务范围ds之内。 如果有很多相同mindis的加油站，输出距所有住宅平均距离最小的那个。 如果平均值还是一样，就输出按照顺序排列加油站编号最小的。 分析： 加油站之间也是彼此有路连接的，所以最短路径计算的时候也要把加油站算上，是双向边，所以边的数组大小得开两倍。 加油站编号记为n+1~n+m，对这些点用dijkstra计算最短路径即可，这里顺便在dijkstra中进行了剪枝处理，不剪枝也没事。 */ const int maxn=1000+15; int dis[maxn]; int vis[maxn]; int head[maxn]; int tot=0; int mindis; struct Node{ int u; int dis; bool operator<(const Node tmp)const{ return dis>tmp.dis; } }; struct Edge{ int to; int next; int dist; }edge[10005*2]; void add(int u,int v,int dist){ edge[tot].to=v; edge[tot].dist=dist; edge[tot].next=head[u]; head[u]=tot++; } void init(){ memset(head,-1,sizeof(head)); tot=0; } bool dijkstra(int s,int n){ for(int i=0;i<maxn;i++){ dis[i]=INF; vis[i]=0; } priority_queue<Node>q; Node st,t; st.u=s; st.dis=0; dis[s]=0; q.push(st); bool first=true; while(!q.empty()){ st=q.top(); q.pop(); vis[st.u]=1; if(first && 1<=st.u && st.u<=n){ if(dis[st.u]<mindis){ return false; //剪枝，即离车站最小的距离比目前的mindis还要小，直接返回即可 } first=false; } for(int k=head[st.u];k!=-1;k=edge[k].next){ int v=edge[k].to; if(!vis[v] && dis[st.u]+edge[k].dist<dis[v]){ dis[v]=dis[st.u]+edge[k].dist; t.u=v; t.dis=dis[v]; q.push(t); } } } return true; } int main() { int n,m,k,ds; char str1[10],str2[10]; int u,v,dist; scanf("%d %d %d %d",&n,&m,&k,&ds); init(); for(int i=0;i<k;i++){ scanf("%s %s %d",str1,str2,&dist); if(str1[0]=='G') u=atoi(str1+1)+n; else u=atoi(str1); if(str2[0]=='G') v=atoi(str2+1)+n; else v=atoi(str2); add(u,v,dist); add(v,u,dist); } mindis=0; double avgdis=INF; int gasid=0; bool noAns=true; for(int i=1;i<=m;i++){ //如果最小距离小于目前的mindis，直接跳过 if(!dijkstra(n+i,n)){ continue; } dist=INF; int sum=0; bool flag=true; for(int j=1;j<=n;j++){ //有超出服务范围的 if(dis[j]>ds){ flag=false; break; } dist=min(dist,dis[j]); sum+=dis[j]; } if(!flag) continue; else noAns=false; double avg=sum*1.0/n; if(dist>mindis){ gasid=i; mindis=dist; avgdis=avg; } else if(dist==mindis){ if(avg<avgdis){ gasid=i; avgdis=avg; } } } if(noAns) printf("No Solution "); else printf("G%d %.1lf %.1lf ",gasid,(double)mindis,avgdis); return 0; }