1. C++, Tobias Fuchs

/*
* Author: Tobias Fuchs
* Problem: 10147 - Highways
* Verdict: Accepted
* Runtime: 1.210
*
*/

#include<stdio.h>
#include<math.h>
#include<vector>
#include<map>
#include<iostream>
#include<utility>
#include<string.h>
#include<queue>
#include<set>

#ifdef _LOG
#define log(msg) ::std::cout << msg << ::std::endl
#else
#define log(msg) (void*)(0)
#endif

#define INFTY 10000000

typedef struct {
unsigned int x;
unsigned int y;
} coord_t;

// town id -> coords
::std::map< int, coord_t> towns;

// [town a][town b] -> distance
bool map[750][750];
// [town a][town b] -> existing street?
bool existing_streets[750][750];

class Edge
{
private:
unsigned int m_from, m_to;
double m_weight;
public:
Edge(unsigned int from, unsigned int to, double weight)
: m_from(from), m_to(to), m_weight(weight)
{ }
public:
inline double weight() const { return m_weight; }
inline unsigned int to() const { return m_to; }
inline unsigned int from() const { return m_from; }
};
bool operator<(const Edge & a, const Edge & b) { return (a.weight() > b.weight()); }

inline double distance(unsigned int town_a, unsigned int town_b)
{
double d;
// Weight to same town is to be ignored
if(town_a == town_b) {
return INFTY;
}
if(existing_streets[town_a][town_b]) {
return 0;
}
// Distance has been computed for other direction
// already:
if(map[town_a][town_b]) { return map[town_a][town_b]; }

// Get distance via cartesian coords:
coord_t a = towns[town_a];
coord_t b = towns[town_b];
double x = abs(a.x - b.x);
double y = abs(a.y - b.y);
d = sqrt(pow(x,2.0) + pow(y,2.0));
map[town_a][town_b] = d;
return d;
}

inline void add_town(unsigned int x, unsigned int y)
{
coord_t c;
c.x = x;
c.y = y;
towns[towns.size()] = c;
}

void prim(unsigned int n_towns) {
bool marked[n_towns];
unsigned int v,w, new_streets, num_mst_edges;
new_streets = 0;
num_mst_edges = 0;
// Start with empty priority queue:
::std::priority_queue<Edge, ::std::deque<Edge> > pqueue;


memset(marked, 0, sizeof(marked));
v = 0;
marked[v] = true;
// Add all incident edges of v into queue (all other
// towns are incident):
for(unsigned int t=0; t<n_towns; ++t) {
// Find indicent edge that has an unmarked endpoint w:
pqueue.push(Edge(v, t, distance(v,t)));
}
Edge e(0,0,0.0);
while(num_mst_edges < n_towns-1) {
// Find indicent edge that has an unmarked endpoint w:
e = pqueue.top();
w = e.to();
while(marked[w]) {
pqueue.pop();
e = pqueue.top();
w = e.to();
}
marked[w] = true;
++num_mst_edges;
if(!existing_streets[e.from()][e.to()]) {
::std::cout << e.from()+1 << " " << e.to()+1 << ::std::endl;
++new_streets;
}
pqueue.pop();
for(unsigned int t=0; t<n_towns; ++t) {
// Find indicent edge that has an unmarked endpoint w:
if(!marked[t]) {
pqueue.push(Edge(w, t, distance(w,t)));
}
}
}
if(!new_streets) { ::std::cout << "No new highways need" << ::std::endl; }
}

int main(int argc, char * argv[])
{

int n_towns, k, i, n_cases, x, y, n_streets; ;

while(scanf("%d",&n_cases) && n_cases)
{
while(n_cases) {
--n_cases;
scanf("%d", &n_towns);
if(n_towns == 0) continue;

for(i = 0; i<n_towns; i ++)
{
scanf("%d%d", &x, &y); // read town
add_town(x,y);
}
scanf("%d", &n_streets); // read town
while(n_streets) {
scanf("%d%d",&x,&y);
existing_streets[x-1][y-1] = true;
existing_streets[y-1][x-1] = true;
--n_streets;
}

prim(n_towns);
if(n_cases) { ::std::cout << ::std::endl; }

// Reset for next case:
memset(map, 0, sizeof(map));
memset(existing_streets, 0, sizeof(existing_streets));
towns.clear();
}
}
return 0;
}