10034 - Freckles

Problem Link

এখানে N টা points দেওয়া থাকবে , প্রতিটা point কে একেকটা নোড ধরবো আর একটা থেকে আরেকটার distance হবে একটা edge এর weight। যদি (x₁,y₁) & (x₂,y₂) দুইটা point হয়, তাহলে-
                               distance between two points = √( (x₁ - x₂)² + (y₁-y₂)² )
বাকিটা কি করতে হবে এটা বুঝে যাওয়ার কথা ... না বুঝলেও সমস্যা নাই। এখন আমরা minimum weight পেতে MST ব্যবহার করব।

আরেকটা জিনিস খেয়াল রাখতে হবে, শেষ test case এর output print করার পর কোনো নতুন লাইন প্রিন্ট হবে না।

My Code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pii pair<double, int>
const int MAX = 1005;
vector<pii> adj[MAX];
bool marked[MAX];

double Prim(int x)
{
    priority_queue<pii, vector<pii>, greater<pii> > Q;
    memset(marked, false, sizeof(marked));
    int y;
    double minimumcost = 0;
    pii p;
    Q.push(mp(0, x));

    while(!Q.empty())
    {
        p = Q.top();
        Q.pop();
        x = p.second;
        if(marked[x]==true)
            continue;
        minimumcost += p.first;
        marked[x] = true;
        for(int i = 0; i < adj[x].size(); i++)
        {
            y = adj[x][i].second;
            if(marked[y]==false)
                Q.push(adj[x][i]);
        }
    }
    return minimumcost;
}

int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        for(int i = 0; i < MAX; i++)
            adj[i].clear();
        int n;
        double minimumcost;
        double x[105], y[105];
        cin>>n;
        for(int i = 1; i <= n; i++)
            cin>>x[i]>>y[i];
        for(int i = 1; i <= n; i++)
        {
            for(int j = i+1; j <= n; j++)
            {
                double s;
                s = sqrt(pow(x[j]-x[i],2) + pow(y[j]-y[i],2));
                adj[i].push_back(mp(s,j));
                adj[j].push_back(mp(s,i));
            }
        }

        minimumcost = Prim(1);
        cout<<fixed<<setprecision(2)<<minimumcost<<endl;
        if(T)
            cout<<endl;
    }

    return 0;
}