大佬帮忙看一下
查看原帖
大佬帮忙看一下
694866
grass_dream楼主2022/8/25 17:45
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
using namespace std;
const int N=1010,M=10000050,INF=0x3f3f3f3f,pp=0;
double cost[N][N];
bool used[N];
double mindist[N];
int n, m;
struct zb{
	int x,y;
}a[N]; 
int prim() {
    memset(mindist, INF, sizeof(mindist));
    mindist[1] = 0;
    int res = 0;
    while (true)
	{
        int u = -1;
        for (int i=1;i<=n;i++)
		{
            if(!used[i]&&(u==-1||mindist[i]<mindist[u]))
			{
                u = i;
            }
        }
        if(u==-1)break;
        if (mindist[u] == INF) return -1;
        used[u] = true;
        res += mindist[u];
        for (int i = 1; i <= n; i++) {
            mindist[i] = min(mindist[i], cost[u][i]);
        }
    }
    return res;
}

int main() {
    memset(cost, INF, sizeof(cost));
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
    	cin>>a[i].x>>a[i].y; 
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=i+1;j<=n;j++)
		{
			cost[i][j]=sqrt(abs(a[i].x-a[j].x)*abs(a[i].x-a[j].x)+abs(a[i].y-a[j].y)*abs(a[i].y-a[j].y));
			cost[j][i]=sqrt(abs(a[i].x-a[j].x)*abs(a[i].x-a[j].x)+abs(a[i].y-a[j].y)*abs(a[i].y-a[j].y));
		}
	}
    for (int i=0;i<m;i++){
        int u,v;
        cin>>u>>v;
        cost[u][v]=0;
        cost[v][u]=0;
    }
    double res=prim();
    printf("%.2lf",res);
    return 0;
}
2022/8/25 17:45
加载中...