代码感悟:
- 本题中重要的一点是浮点数的精度问题
#include<bits/stdc++.h>
using namespace std;
int main()
{
double a=1.15;
printf("%.15lf\n",a);
printf("%.16lf\n",a);
printf("%.1lf\n",a);
}
输出:
1.150000000000000
1.1499999999999999
1.1
所以为了解决这种不能四舍五入的问题,要在浮点数后边加上1e-18
int main()
{
double a=1.15;
printf("%.1lf\n",a+1e-18);
}
输出:
1.2
TLE代码:
本题目使用堆优化的dijkstra算法会超时,过7/11,但是采用朴素版的就可以AC,从时间复杂度上分析,我不明白为什么前者可以超时???
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<unordered_map>
#include<unordered_set>
#include<queue>
using namespace std;
const int N=1e3+50,M=1e4+10;
int h[N],e[M],ne[M],d[M];
int idx;
int dist[N];
unordered_map<string,int>h1;
unordered_map<int,string>h2;
int id=1000;
int n,m,k,p;
typedef pair<int,int>pii;
void add(int a,int b,int c){
e[idx]=b;
ne[idx]=h[a];
d[idx]=c;
h[a]=idx++;
}
//记录加油站和房屋之间的距离
//如果加油站和一个房屋之间无通路则不同,如果最短距离大于p则不同
//记录每一个加油站连通的房屋
bool st[M];
void dij(int x){
memset(st,false,sizeof st);
memset(dist,0x3f,sizeof dist);
dist[x]=0;
priority_queue<pii,vector<pii>,greater<pii> >heap;
heap.push({0,x});
// cout<<x<<endl;
int si=0;
while(!heap.empty()){
auto tt=heap.top();
heap.pop();
int a=tt.first;
int b=tt.second;
if(st[b])//去掉已经访问过的点和其他的加油站
continue;
st[b]=true;
for(int i=h[b];i!=-1;i=ne[i]){
int j=e[i];
//cout<<j<<' '<<dist[j]<<endl;
if(dist[j]>a+d[i]){
dist[j]=a+d[i];
si++;
heap.push({dist[j],j});
}
}
}
}
struct T{
double av;
int distance;
string name;
}R[50];
bool cmp(T a,T b){
if(a.distance!=b.distance)
return a.distance>b.distance;
else if(a.av!=b.av)
return a.av<b.av;
else
return a.name<b.name;
}
int main(){
cin>>n>>m>>k>>p;
memset(h,-1,sizeof h);
unordered_set<int>temp,home;
for(int i=0;i<k;i++){
string a,b;
int c;
cin>>a>>b>>c;
if(a[0]=='G'){
if(!h1.count(a)){
id++;
h1[a]=id;
h2[id]=a;
}
temp.insert(h1[a]);
a=to_string(h1[a]);
}
else{
home.insert(atoi(a.c_str()));
}
if(b[0]=='G'){
if(!h1.count(b)){
id++;------------------》加油站的编号从1001开始编码
h1[b]=id;
h2[id]=b;
}
temp.insert(h1[b]);
b=to_string(h1[b]);
}
else{
home.insert(atoi(b.c_str()));
}
add(atoi(a.c_str()),atoi(b.c_str()),c);
add(atoi(b.c_str()),atoi(a.c_str()),c);
}
int idd=0;
for(auto &t:temp){
int x=t;
dij(x);
int flag=0;
int sum=0,mi=0x3f;
string name;
name=h2[t];
for(auto &tt:home){
if(dist[tt]>p){
flag=1;
break;
}
sum+=dist[tt];
mi=min(mi,dist[tt]);
}
double av;
if(!flag){
int an=home.size();
av=(double)(sum*1.0/an);
R[idd]={av,mi,name};
idd++;
}
}
if(idd==0){
cout<<"No Solution";
}
else{
sort(R,R+idd,cmp);
cout<<R[0].name<<endl;
printf("%.1lf %.1lf",(double)R[0].distance,R[0].av+1e-8);
}
return 0;
}
AC代码:
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<unordered_map>
#include<unordered_set>
#include<queue>
using namespace std;
const int N=1e3+50,M=1e4+10;
int h[N],e[M],ne[M],d[M];
int idx;
int dist[N];
unordered_map<string,int>h1;
unordered_map<int,string>h2;
int g[N][N];
int n,m,k,p;
int id;
typedef pair<int,int>pii;
void add(int a,int b,int c){
e[idx]=b;
ne[idx]=h[a];
d[idx]=c;
h[a]=idx++;
}
//记录加油站和房屋之间的距离
//如果加油站和一个房屋之间无通路则不同,如果最短距离大于p则不同
//记录每一个加油站连通的房屋
bool st[M];
void dij1(int x){
memset(st,false,sizeof st);
memset(dist,0x3f,sizeof dist);
dist[x]=0;
for(int i=1;i<=n+m;i++){----------------》这里就是为什么加油站的编码从n+1开始的原因了!!
int t=-1;
for(int j=1;j<=n+m;j++){
if(!st[j]&&(t==-1||dist[t]>dist[j])){
t=j;
}
}
st[t]=true;
for(int j=1;j<=n+m;j++){
dist[j]=min( dist[j],dist[t]+g[t][j]);
}
}
}
struct T{
double av;
int distance;
string name;
}R[50];
bool cmp(T a,T b){
if(a.distance!=b.distance)
return a.distance>b.distance;
else if(a.av!=b.av)
return a.av<b.av;
else
return a.name<b.name;
}
int main(){
cin>>n>>m>>k>>p;
memset(h,-1,sizeof h);
unordered_set<int>temp,home;
memset(g,0x3f,sizeof g);
id=n;----------》由于本种方法图的存储结构为邻接矩阵,所以这个加油站的编码起始为n+1!!!
for(int i=0;i<k;i++){
string a,b;
int c;
cin>>a>>b>>c;
if(a[0]=='G'){
if(!h1.count(a)){
id++;
h1[a]=id;
h2[id]=a;
}
temp.insert(h1[a]);
a=to_string(h1[a]);
}
else{
home.insert(atoi(a.c_str()));
}
if(b[0]=='G'){
if(!h1.count(b)){
id++;
h1[b]=id;
h2[id]=b;
}
temp.insert(h1[b]);
b=to_string(h1[b]);
}
else{
home.insert(atoi(b.c_str()));
}
int ta=atoi(a.c_str()),tb=atoi(b.c_str());
g[ta][tb]=min(g[ta][tb],c);
g[tb][ta]=min(g[tb][ta],c);
}
int idd=0;
for(auto &t:temp){
int x=t;
dij1(x);
int flag=0;
int sum=0,mi=0x3f;
string name;
name=h2[t];
// cout<<t<<' '<<name<<endl;
for(auto &tt:home){
if(dist[tt]>p){
flag=1;
break;
}
sum+=dist[tt];
mi=min(mi,dist[tt]);
}
double av;
if(!flag){
int an=home.size();
av=(double)(sum*1.0/an);
R[idd]={av,mi,name};
idd++;
}
}
if(idd==0){
cout<<"No Solution";
}
else{
sort(R,R+idd,cmp);
cout<<R[0].name<<endl;
printf("%.1lf %.1lf",(double)R[0].distance,R[0].av+1e-8);
}
return 0;
}