《关于过样例的代码与10分意外邂逅那件事》
查看原帖
《关于过样例的代码与10分意外邂逅那件事》
309574
未知的X楼主2022/10/6 18:08

以下为离谱到家的不知道哪里有问题~~(好像没有问题)~~的代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cmath>
#define INF 2147483647
using namespace std;
struct edge{
    int to;
    long double dis;
};
vector<edge> e[1000005];
long double d[1005];//树枝最短
int n,m;
long double ans=0;
bool vis[1005];
struct point{
    int x,y;
};
point p[5005];
double dist(point a,point b){
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
void prim(){
    for(int i=1;i<=n;i++){
        d[i]=INF;
    }
    d[1]=0;
    for(int ii=1;ii<=n;ii++){
        int minn=INF;
        int k=1;

        for(int i=1;i<=n;i++){
            if(d[i]<minn&&vis[i]==false){
                minn=d[i];
                k=i;
            }
        }
        vis[k]=true;
        for(int i=1;i<=n;i++){
            if(!vis[i]){
                edge tmp1;
                tmp1.to=i;
                tmp1.dis=dist(p[k],p[i]);
                e[k].push_back(tmp1);
            } 
        }
        for(int i=0;i<e[k].size();i++){
            if(d[e[k][i].to]>e[k][i].dis){
                d[e[k][i].to]=e[k][i].dis;
            }
        }
        if(ii==n) for(int i=1;i<=n;i++) ans+=d[i];
    }
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>p[i].x>>p[i].y;
    }
    prim();
    printf("%.2Lf",ans);
    return 0;
} 

大哥大姐大神们,救救孩子

2022/10/6 18:08
加载中...