Light oj 1059 solution

MST & BFS Combine
লাইট অজ ১০৫৯
এমনিতে মিনিমাম ডিসট্যান্স বের করে +কত গুলোর জন্য বি এফ এস আলাদা ভাবে চালান লাগছে সেইগুলোর সাথে   এইচ বার বার গুন
2
4 4 100
1 2 10
4 3 12
4 1 41
2 3 23

উত্তর আসছে ১০+১২+২৩+(১০০*১)=১৪৫
আউটপুট ঃ Case 1: 145 1

5 3 1000
1 2 20
4 5 40
3 2 30

উত্তর আসছে ঃ ২০+৪০+৩০+(১০০০*২)=২০৯০
আউটপুট ঃ Case 2: 2090 2




#include<bits/stdc++.h>
#define fr(i1,m) for(int i1=0;i1<m;i1++)
using namespace std;
struct edge
{
    int u,v,w;
    bool operator < ( const edge& p ) const
    {
        return w < p.w;
    }
};
int pr[100107],aa[100010];
long kk,f,g,h;
vector<edge>e;
int find(int r)
{
    return (pr[r]==r) ? r:  find(pr[r]);
}
int mst(int n)
{
    sort(e.begin(),e.end());
    for(int i=1; i<=n; i++)
        pr[i]=i;

    long long count=0,s=0;                                                                                                                                                           "Fuck\n";
    for(int i=0; i<(int)e.size(); i++)
    {
        int u=find(e[i].v);

        int v=find(e[i].u);

        if(u!=v)
        {
            pr[u]=v;
            count++;
            if(e[i].w>=h)
            {
                if(aa[v]==0)
                {
                    kk++;
                    aa[v]=1;
                }

                if(aa[u]==0)
                {
                    kk++;
                    aa[u]=1;
                }
            }
            else
                s+=e[i].w;
            if(count==n-1)
                break;
        }
    }
    return s;
}
vector<int>vc[100100];
long long ff[100008],l;
void bfs(int n)
{
    queue<int>q;

    q.push(n);

    while(!q.empty())
    {
        int u=q.front();

        ff[u]=1;

        if(aa[u]==1)
            l=1;

        for(int i=0; i<vc[u].size(); i++)
        {
            int v=vc[u][i];

            if(ff[v]==0)
            {
                ff[v]=1;

                q.push(v);
            }
        }
        q.pop();
    }
}
int main()
{
    long  m;

    cin>>m;

    fr(ii,m)
    {
        long long i,u,v,w,cc=0;
        kk=0;

        cin>>f>>g>>h;

        for(i=1; i<=g; i++)
        {
            cin>>u>>v>>w;

            edge get;

            get.u=u;
            get.v=v;
            get.w=w;

            e.push_back(get);

            vc[u].push_back(v);

            vc[v].push_back(u);
        }
        long xx=mst(f);

        for(i=1; i<=f; i++)
        {
            if(ff[i]==0)
            {
                l=0;
                bfs(i);
                //cout<<i<<" "<<l<<"\n";
                if(l==0)
                    cc++;
            }
        }

        printf("Case %ld: ",ii+1);
        cout<<xx+kk*h+cc*h<<" "<<kk+cc<<"\n";
        e.clear();
        fr(i,f+3)
        {
            aa[i]=0;
            vc[i].clear();
            ff[i]=0;

        }
    }
    return 0;

}