如题,第一段是使用vector的TLE代码,第二段是使用结构体数组的AC代码,按理说vector虽然慢一点但也不至于慢这么多吧,请问这是为什么?
#include<bits/extc++.h>
using namespace std;
#define endl '\n'
typedef int INT;
//#define int long long
inline int read(){
int x=0,y=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')y=-1;c=getchar();}
while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
return x*y;
}
inline void write_base(int x){
if(x>9)write_base(x/10);
putchar('0'+x%10);
}
inline void write(int x){
if(x<0)putchar('-'),x*=-1;
write_base(x);
// putchar(' ');
putchar('\n');
}
//using namespace __gnu_pbds;
/********************************************************/
const int N=1e3+1;
double x[N],y[N];
int fa[N];
inline int find(int i){
int n=i;
while(i!=fa[i])
i=fa[i];
return fa[n]=i;
}
struct Node{
int a,b;double w;
bool operator<(Node node){
if(w==node.w)
if(a==node.a)
return b<node.b;
else
return a<node.a;
else
return w<node.w;
}
};
inline double dis(int a,int b){
return sqrt(pow(x[a]-x[b],2)+pow(y[a]-y[b],2));
}
vector<Node>v;
INT main(){//ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int n=read(),m=read();
for(register int i=1;i<=n;++i)
x[i]=read(),y[i]=read(),fa[i]=i;
for(register int i=1;i<=n;++i)
for(register int j=i+1;j<=n;++j)
v.push_back(Node{i,j,dis(i,j)}),
sort(v.begin(),v.end());
while(m--)
fa[find(read())]=find(read());
double ans=0;
for(auto&i:v)
if(find(i.a)!=find(i.b))
fa[find(i.a)]=find(i.b),
ans+=i.w;
printf("%.2lf",ans);
}
#include<bits/extc++.h>
using namespace std;
#define endl '\n'
typedef int INT;
//#define int long long
inline int read(){
int x=0,y=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')y=-1;c=getchar();}
while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
return x*y;
}
inline void write_base(int x){
if(x>9)write_base(x/10);
putchar('0'+x%10);
}
inline void write(int x){
if(x<0)putchar('-'),x*=-1;
write_base(x);
// putchar(' ');
putchar('\n');
}
//using namespace __gnu_pbds;
/********************************************************/
const int N=1e3+1;
double x[N],y[N];
int fa[N];
inline int find(int i){
int n=i;
while(i!=fa[i])
i=fa[i];
return fa[n]=i;
}
struct Node{
int a,b;double w;
bool operator<(Node node){
if(w==node.w)
if(a==node.a)
return b<node.b;
else
return a<node.a;
else
return w<node.w;
}
}node[1000000];int t=0;
inline double dis(int a,int b){
return sqrt(pow(x[a]-x[b],2)+pow(y[a]-y[b],2));
}
INT main(){//ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int n=read(),m=read();
for(register int i=1;i<=n;++i)
x[i]=read(),y[i]=read(),fa[i]=i;
for(register int i=1;i<=n;++i)
for(register int j=i+1;j<=n;++j)
node[t].a=i,node[t].b=j,node[t++].w=dis(i,j);
sort(node,node+t);
while(m--)
fa[find(read())]=find(read());
double ans=0;
for(auto&i:node)
if(find(i.a)!=find(i.b))
fa[find(i.a)]=find(i.b),
ans+=i.w;
printf("%.2lf",ans);
}