1251 하나로

https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15StKqAQkCFAYD

가능한 간선을 모두 저장한 후 MST를 만든다.

#include <cstdio>
#include <vector>
#include <algorithm>
typedef long long ll;
using namespace std;
 
struct Edge
{
    ll start,end,cost;
    bool operator < (const Edge &other) const { return cost<other.cost; }
};
 
ll t,n,m,ans,p[1001],x[1001],y[1001];
double E;
ll Find(ll x) { return x==p[x]?x:p[x]=Find(p[x]); }
void Union(ll x,ll y) { p[Find(x)]=Find(y); }
ll dist(ll x1,ll y1,ll x2,ll y2)
{
    ll a=abs(x1-x2),b=abs(y1-y2);
    return a*a+b*b;
}
 
int main()
{
    scanf("%lld",&t);
    for(ll k=1;k<=t;k++)
    {
        scanf("%lld",&n);
        for(ll i=1;i<=n;i++) scanf("%lld",&x[i]);
        for(ll i=1;i<=n;i++) scanf("%lld",&y[i]);
        scanf("%lf",&E);
        for(ll i=1;i<=n;i++) p[i]=i;
        vector<Edge> a;
        for(ll i=1;i<=n;i++) for(ll j=i+1;j<=n;j++)
            a.push_back({i,j,dist(x[i],y[i],x[j],y[j])});
        sort(a.begin(),a.end());
        m=a.size(),ans=0;
        for(ll i=0;i<m;i++)
        {
            Edge e=a[i];
            ll x=Find(e.start),y=Find(e.end);
            if(x!=y) Union(e.start,e.end),ans+=e.cost;
        }
        printf("#%lld %.0f\n",k,ans*E);
    }
    return 0;
}