题意：
输入四个正整数N,M,K,D（N<=1000,M<=10,K<=10000）分别表示房屋个数，加油站个数，路径条数和加油站最远服务距离，接着输入K行每行包括一条路的两条边和距离。输出最近距离最远同时与所有房屋距离都不超过D的加油站名字和最近距离以及平均距离。如果有多个答案则优先输出平均距离最小的，再不唯一则输出编号最小的。
trick：
这题有一个诡异的事情，样例1的平均距离是3.25，取一位小数应该是3.2，四舍五入则是3.3，样例显示为3.3，此时我理解为四舍五入，题面说是精确到1位小数。
当我将ans+0.05时测试点4会不过，当我直接舍入时AC样例却输出3.2。??。。。
代码：
#define HAVE_STRUCT_TIMESPEC
#include<bits/stdc++.h>
using namespace std;
vector<pair<int,int> >edge[1017];
int dis[1017],vis[1017];
int sum[17],mnn[17],mxx[17];
void Dijkstra(int x){
dis[x]=0;
priority_queue<pair<int,int> >pq;
pq.push({0,x});
while(!pq.empty()){
int now=pq.top().second;
pq.pop();
if(vis[now])
continue;
vis[now]=1;
for(int i=0;i<edge[now].size();++i){
int v=edge[now][i].first;
if(!vis[v]&&dis[v]>dis[now]+edge[now][i].second){
dis[v]=dis[now]+edge[now][i].second;
pq.push({-dis[v],v});
}
}
}
}
int main(){
//ios::sync_with_stdio(false);
//cin.tie(NULL);
//cout.tie(NULL);
for(int i=1;i<=10;++i)
mnn[i]=1e9+7;
int n,m,k,d;
scanf("%d%d%d%d",&n,&m,&k,&d);
for(int i=1;i<=k;++i){
int u=0,v=0,w;
char s1[5],s2[5];
scanf("%s%s%d",s1,s2,&w);
if(s1[0]==‘G‘){
if(s1[2]==‘0‘)
u=1010;
else
u=1000+s1[1]-‘0‘;
}
else{
for(int j=0;j<strlen(s1);++j){
u*=10;
u+=s1[j]-‘0‘;
}
}
if(s2[0]==‘G‘){
if(s2[2]==‘0‘)
v=1010;
else
v=1000+s2[1]-‘0‘;
}
else{
for(int j=0;j<strlen(s2);++j){
v*=10;
v+=s2[j]-‘0‘;
}
}
edge[u].push_back({v,w});
edge[v].push_back({u,w});
}
int mn=0,pos=0,mnnn=0;
for(int i=1;i<=m;++i){
for(int j=1;j<=1010;++j)
dis[j]=1e9+7,vis[j]=0;
Dijkstra(i+1000);
for(int j=1;j<=n;++j){
sum[i]+=dis[j];
mnn[i]=min(mnn[i],dis[j]);
mxx[i]=max(mxx[i],dis[j]);
}
if(mxx[i]<=d&&mnn[i]>=mnnn){
if(mnn[i]>mnnn){
mn=sum[i];
pos=i;
mnnn=mnn[i];
}
else if(mnn[i]==mnnn&&sum[i]<mn){
mn=sum[i];
pos=i;
}
}
}
double ans=1.0*mn/n;
if(pos){
printf("G%d\n",pos);
printf("%d.0 %.1lf",mnnn,ans);
}
else
printf("No Solution");
return 0;
}
【PAT甲级】1072 Gas Station (30 分)（Dijkstra）
原文：https://www.cnblogs.com/ldudxy/p/11798889.html