2789122_ac_62ms_4060k.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <math.h>
#include <algorithm>
# define MAX 1001
# define INF 2100000000

using namespace std;

int K, no;
double cost[MAX][MAX];
double edge[MAX];

bool cmp(double a,double b)
{
	return a-b>0;
}

struct node
{
	double x, y;
}pot[1001];

void prim(int n,int v)
{
	int i, j, k;
	double min;
	double lowcost[MAX];

	no = 0;
	for(i = 0; i < n; i++)
		lowcost[i] = cost[v][i];
	for(i = 1; i < n; i++)
	{
		min = INF;
		for(j = 0; j < n; j++)
			if(lowcost[j]!=0&&lowcost[j]<min)
			{
				min = lowcost[j];
				k = j;
			}
			edge[no++] = min;
			lowcost[k] = 0;
		for(j = 0; j < n; j++)
			if(cost[k][j]!=0&&cost[k][j]<lowcost[j])
				lowcost[j] = cost[k][j];
	}
}

double dis(int i,int j)
{
	return sqrt((pot[i].x-pot[j].x)*(pot[i].x-pot[j].x)+(pot[i].y-pot[j].y)*(pot[i].y-pot[j].y));
}

void init(int n)
{
	int i, j;

	for(i = 0; i < n; i++)
		scanf("%lf%lf",&pot[i].x,&pot[i].y);
	for(i = 0; i < n; i++)
	{
		cost[i][i] = 0;
		for(j = i+1; j < n; j++)
			cost[i][j] = cost[j][i] = dis(i,j);
	}
}
int main()
{
	int n, t;

	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d",&K,&n);
		init(n);
		prim(n,0);
		sort(edge,edge+n-1,cmp);
		printf("%.2lf\n",edge[K-1]);
	}
	return 1;
}