1252 하나로

1252 하나로

1. 모든 섬을 비용하여 섬과 섬 사이의 거리를 구한다.

2. 만든 거리들을 가지고 크루스칼 알고리즘을 활용해 최소비용신장트리를 만든다.

3 . 값을 출력한다.

ps --> 데이터타입을 잘 구성해야 한다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#define P pair<double,double>
using namespace std;
 
struct dist{
    int u, v;
    double c;
    dist(int u,int v,double c) :u(u),v(v),c(c){}
};
 
int t, n;
double e;
int group[1000];
P map[1000];
 
int Find(int x) {
    if (x == group[x]) return x;
    return group[x] = Find(group[x]);
}
 
void Union(int a,int b) {
    a = Find(a);
    b = Find(b);
    if (a == b) return;
    group[b] = a;
}
 
int compare_dist(const dist &a, const dist &b) {
    return a.c < b.c;
}
 
double kruskal(vector<dist> &d) {
    double ans = 0;
 
    sort(d.begin(), d.end(), compare_dist);
 
    for (int i = 0; i < d.size(); i++) {
        if (Find(d[i].u) == Find(d[i].v)) continue;
 
        ans += d[i].c;
        Union(d[i].u, d[i].v);
    }
 
    return e * (ans);
}
 
int main() {
    scanf("%d", &t);
    for (int tc = 1; tc <= t; tc++) {
        scanf("%d", &n);
        for (int i = 0; i < n; i++) {
            scanf("%lf", &map[i].first);
            group[i] = i;
        }
        for (int i = 0; i < n; i++) {
            scanf("%lf", &map[i].second);
        }
        scanf("%lf", &e);
 
        vector<dist> d;
        //모든경로에 대해 d 벡터에 저장
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                d.push_back(dist(i,j,
                    pow(map[i].first - map[j].first, 2) 
                  + pow(map[i].second - map[j].second, 2)));
            }
        }
 
        printf("#%d %.0lf\n", tc, kruskal(d));
    }
}