Baekjoon 1774번 우주신과의 교감

문제

https://www.acmicpc.net/problem/1774

걸린 시간

00 : 43 : 22

풀이

C++

#include <bits/stdc++.h>
#define INF 1e9
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

struct DisjointSet{
    vector<int> parent, rank;
    DisjointSet(int n): parent(n), rank(n, 1){
        for(int i = 0; i < n; i++)
            parent[i] = i;
    }
    int find(int u) {
        if(u == parent[u]) return u;
        return parent[u] = find(parent[u]);
    }
    void merge(int u, int v){
        u = find(u); v = find(v);
        if(u == v) return;
        if(rank[u] > rank[v]) swap(u, v);
        parent[u] = v;
        if(rank[u] == rank[v]) rank[v]++;
    }
};

struct node{
    int u, v;
    double cost;
    node(int u, int v, double cost){
        this->u = u;
        this->v = v;
        this->cost = cost;
    }
};

bool compare(node a, node b){
    return a.cost < b.cost;
}

int n, m;
double adj[1000][1000];
double x[1000], y[1000];

double kruskal(){
    double ret = 0;
    vector<node> edges;
    for(int u = 0; u < n; u++)
        for(int v = 0; v < n; v++)
            if(adj[u][v] != 0)
                edges.push_back(node(u, v, adj[u][v]));
    sort(edges.begin(), edges.end(), compare);
    DisjointSet sets(n);
    int u, v;
    for(int i = 0; i < m; i++){
        cin >> u >> v;
        sets.merge(u-1, v-1);
    }
    for(int i = 0; i < edges.size(); i++){
        double cost = edges[i].cost;
        int u = edges[i].u;
        int v = edges[i].v;
        if(sets.find(u) == sets.find(v)) continue;
        sets.merge(u, v);
        ret += cost;
    }
    return ret;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> m;
    for(int i = 0; i < n; i++)
        cin >> x[i] >> y[i];
    for(int u = 0; u < n; u++)
        for(int v = 0; v < n; v++){
            double dist = sqrt(pow(x[u]-x[v], 2) + pow(y[u]-y[v], 2));
            adj[u][v] = dist;
            adj[v][u] = dist;
        }
    printf("%.2lf\n", kruskal());
    return 0;
}

이미 연결된 통로를 disjoint set 에 추가해주고 크루스칼 알고리즘을 수행하면 쉽게 ac 를 받을 줄 알았지만, cout 의 setprecision 함수를 사용하는 바람에 틀렸습니다가 출력되었다.

아마도 printf 와 다르게 소수점 이하 자릿수가 0일 땐 출력하지 않기 때문이 아닐까 싶다.