1. Martin Lambeck

package acm_10369_arctic_network;

import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.TreeSet;

/**
* FWP, Ausgew¦hlte Probleme aus dem ACM Programming Contest, SS10
* Problem: acm_10369_arctic_network
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=116&page=show_problem&problem=1310
*
* @author Martin Lambeck
* @version 1.0, 17.08.2010
*
* Method : mst (prim)
* Status : Accepted
* Runtime: 0.836
*/


public class Main
{
static Scanner sc = new Scanner(System.in);

public static void main(String... args)
{
int cases = sc.nextInt();

for (int i = 0; i < cases; i++)
testcase();
}

public static void testcase()
{
int s = sc.nextInt();
int p = sc.nextInt();

ArrayList<int[]> posts = new ArrayList<int[]>(p); //x,y of outposts
double[][] adja = new double[p][p]; //distance

for (int i = 0; i < p; i++)
{
int x = sc.nextInt();
int y = sc.nextInt();

posts.add(new int[]{x, y});
}

for (int i = 0; i < p; i++)
{
for (int j = 0; j < p; j++)
{
int[] p1 = posts.get(i);
int[] p2 = posts.get(j);
int dx = p2[0] - p1[0];
int dy = p2[1] - p1[1];

adja[i][j] = Math.sqrt(dx*dx + dy*dy);
}
}

System.out.printf("%.2f%n", mst(adja, p, s));
}

static double mst(double[][] adja, int p, int s)
{
boolean[] visited = new boolean[p];
PriorityQueue<Edge> pq = new PriorityQueue<Edge>(p);

TreeSet<Edge> ts = new TreeSet<Edge>(); //contains all edges, sorted by costs (asc)

//prim mst

for (int i = 1; i < p; i++) //headquarters
{
pq.add(new Edge(0, i, adja[0][i]));
}

visited[0] = true; //headquarters

while (pq.size() > 0)
{
Edge e = pq.poll();

if (visited[e.to])
continue;

visited[e.to] = true;

for (int i = 0; i < p; i++)
{
if (!visited[i])
pq.add(new Edge(e.to, i, adja[e.to][i]));
}

ts.add(e);
}


//replace expensive edges by sat

boolean[] sat = new boolean[p]; //true if outpost has satellite transceiver

s--; //headquarters

while ((s >= 0) && (ts.size() > 0))
{
Edge e = ts.last(); //edge of highest cost

//because of prims algo, if edge e is deleted:
// e.to will not anymore be connected to the headquarters (other than e.from)
// so e.to will get a sat-transceiver (not e.from)

if (!sat[e.to]) //there is no satellite yet
{
s--;
sat[e.to] = true;
}

if (s >= 0)
ts.pollLast(); //remove edge, if it was possible to replace by sat
}


if (ts.size() > 0)
return ts.last().costs;
else
return 0.0;
}
}

class Edge implements Comparable<Edge>
{
double costs;
int to;
int from;

public Edge(int f, int t, double c)
{
from = f;
to = t;
costs = c;
}

public int compareTo(Edge o)
{
if (costs == o.costs)
return 0;

return (costs < o.costs ? -1 : 1);
}
}