prim,10分求调
  • 板块P1265 公路修建
  • 楼主junee
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/11/13 22:27
  • 上次更新2023/11/13 22:31:41
查看原帖
prim,10分求调
757101
junee楼主2023/11/13 22:27
#include<algorithm>
#include<iostream>
#include<cmath>
#include<cstring>
using namespace std;
const int N=5010;
int x[N],y[N];
double dist[N];
bool st[N];
double res=0;
int n,m;
double d(int a,int b,int c,int d){
	return sqrt(1ll*(a-b)*(a-b)+(c-d)*(c-d));
}
void prim(){
    for(int i=1;i<=n;i++)dist[i]=d(x[1],x[i],y[1],y[i]);
    st[1]=1;
    for(int i=1;i<=n;i++){
        int t=-1;
        for(int j=1;j<=n;j++)if(!st[j]&&(t==-1||dist[t]>dist[j]))t=j;
        st[t]=1;
        res+=dist[t];
        for(int j=1;j<=n;j++){
            double dis=d(x[t],x[j],y[t],y[j]);
            if(!st[j]){
                dist[j]=min(dis,dist[j]);
            }
		}
    }
}
int main(){
    memset(st,0,sizeof st);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>x[i]>>y[i];
    prim();
    printf("%0.2lf",res);
    return 0;
}
2023/11/13 22:27
加载中...