# ZOJ 2048 highways

```//#include "stdafx.h"
#include <iostream>
#include "stdio.h"
#include <math.h>
using namespace std;
int town[750][2];
double dis[750][750];
double ans;
int n;
void prim()
{
int temp[750];  //存放已经加入的结点
int size;    // 已加入的结点个数
int i, j, k;
int lastnode1 = 0, curnode, pos2;
double min;

temp[0] = 0;
size = 1;

dis[0][0] = 1;

for (i = 0; i < n - 1; i++)//执行n-1次将所有的点访问完
{
min = 32767; // 极大值
for (j = 0; j < size; j++)
{
curnode = temp[j];
for (k = 0; k < n; k++)
if (dis[curnode][k] <= min && dis[k][k] == 0) //min 为当前最小值，为0表示没有访问过，如果新加入结点后有再小的边就将对应的点加入
{
min = dis[curnode][k];
lastnode1 = curnode;

pos2 = k;
}
}
if (min != 0)
{

cout << lastnode1 + 1 << " " << pos2 + 1 << endl;//ans += min;
}
dis[pos2][pos2] = 1;//表示已经访问过
temp[size] = pos2; size++;

}
}
int main()
{
int T, M = -1, E;
cin >> T;
while (T--)
{
memset(dis, 0, sizeof(dis));
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> town[i][0] >> town[i][1];//输入town 的坐标
}
for (int i = 0; i < n; i++)
{
for (int j = i + 1; j < n; j++)//计算每两个点之前的距离
{

dis[j][i] = dis[i][j] = sqrt(pow(town[i][0] - town[j][0], 2) + pow(town[i][1] - town[j][1], 2));        //计算两点间的距离
}
}
cin >> E;
int x, y;
while (E--)
{
cin >> x >> y;
dis[x - 1][y - 1] = 0;
dis[y - 1][x - 1] = 0;

}

prim();
if (T)
cout << endl;
}
return 0;
}```

ZOJ 2048 highways