# test

10165102128 edited 4 年，10 月前

test

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <cstdio>

using namespace std;

struct path{
int u, v;
double dis;
bool operator <(const path& ano) const{
return dis > ano.dis;
}
path(int u, int v, double dis):u(u), v(v), dis(dis){}
};

vector<path> e;
vector<int> G[1100];
bool vis[1100];
vector<int> v;
pair<int ,int> farm[1100];

int main(){
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; i++){
cin >> farm[i].first >> farm[i].second;
}
int t = 0;
for(int i = 0; i < m; i++){
int temp1, temp2;
cin >> temp1 >> temp2;
e.push_back(path(temp1, temp2, 0));
G[temp1].push_back(t++);
e.push_back(path(temp2, temp1, 0));
G[temp2].push_back(t++);
}
for(int i = 1; i <= n - 1; i++){
for(int j = i + 1; j <= n; j++){
long long dx = farm[i].first - farm[j].first;
long long dy = farm[i].second - farm[j].second;
e.push_back(path(i, j, sqrt(dx * dx + dy * dy)));
G[i].push_back(t++);
e.push_back(path(j, i, sqrt(dx * dx + dy * dy)));
G[j].push_back(t++);
}
}
double res = 0;
v.push_back(1);
vis[1] = true;
while(v.size() != n){
double d = 10000000;
int next;
for(int u: v){
for(int temp: G[u]){
if(!vis[e[temp].v] && e[temp].dis < d){
d = e[temp].dis;
next = e[temp].v;

}
}
}
v.push_back(next);
vis[next] = true;
res += d;
}
printf("%.2f\n", res);
}