[1774] 우주신과의 교감

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

1774번: 우주신과의 교감

<문제>

이미 연결된 간선 가중치테이블의 값을 0으로 설정해둔다.

모든 (i, j)에 대해서, 두 점 사이의 거리를 가중치를 갖는 간선을 생성해주면 남는것은 mst를 구하는 일 밖에 없다.

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pi = pair<ll, ll>;
using p = pair<double, ll>;
vector<pi> v;
priority_queue<p, vector<p>, greater<p>> q;
ll n, m;
bool vst[1003];
double cost[1003][1003], ans;
double c(ll A, ll B) {
    return sqrt(pow(v[A].first - v[B].first, 2) +
                pow(v[A].second - v[B].second, 2));
}
void prim(void) {
    vst[1] = true;
    ll i;
    for (i = 2; i <= n; i++) q.push({cost[1][i], i});
    while (!q.empty()) {
        double curCost = q.top().first;
        ll curIdx = q.top().second;
        q.pop();
        if (vst[curIdx] == true) continue;
        vst[curIdx] = true;
        ans += curCost;
        for (i = 1; i <= n; i++)
            if (vst[i] == false) q.push({cost[curIdx][i], i});
    }
}
int main(void) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    ll i, j;
    v.resize(n);
    for (i = 0; i < n; i++) cin >> v[i].first >> v[i].second;
    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++) {
            if (i == j) continue;
            cost[i + 1][j + 1] = c(i, j);
        }
    for (i = 0; i < m; i++) {
        ll A, B;
        cin >> A >> B;
        cost[A][B] = 0;
        cost[B][A] = 0;
    }
    prim();
    cout << fixed, cout.precision(2);
    cout << ans;
    return 0;
}