Prims

/**
* E:\Dropbox\Profession\SUST\CSE_138_2017\Prims.cpp
* Created on: 2017-11-22-15.45.44, Wednesday
* Verdict: Not Solved
* Author: Enamul Hassan
**/

#include <bits/stdc++.h>
#define _ ios_base::sync_with_stdio(0);cin.tie(0);

#define SZ(a) ((ll)a.size())
#define sz 200005
#define pb push_back
#define pp pop_back()
#define all(a) a.begin(),a.end()
#define ll long long
#define cntbit(mask) __builtin_popcount(mask)
#define unify(a) stable_sort(a.begin(),a.end());a.resize(distance(a.begin(),unique(all(a))));
#define fread freopen("input.txt","r",stdin)
#define fwrite freopen("output.txt","w",stdout)
#define inf (1e18)
#define chng(a,b) a^=b^=a^=b;
#define clr(abc,z) memset(abc,z,sizeof(abc))
#define PI acos(-1)
#define pi 3.14159265358979323846264338327950288419716939937510
#define fr(i,a,b) for(i=a;i<=b;i++)
#define cspf printf("Case %d:", cas++);
#define csco cout<<"Case "<<cas++<<": ";
#define mod 1000000007

#ifdef ENAM
#define deb(args...) {dbg,args; cerr<<endl;}
#else
#define deb(args...)
#endif
using namespace std;

struct _deb{
    template<typename T> _deb& operator , (const T& _temp){
        cerr<<_temp<<" ";
        return *this;
    }
}dbg;

/// debug template credit: Bidhan Roy

ll bigmod(ll sonkha,ll ghat,ll vag_const){ll vag_shesh=1;while(ghat>0){if(ghat%2==1){vag_shesh=(vag_shesh*sonkha)%vag_const;}ghat/=2;sonkha=(sonkha*sonkha)%vag_const;}return vag_shesh;}
ll inverse_mod(ll bivajok, ll vag_const){return bigmod(bivajok,vag_const-2, vag_const);}

vector<int>adj[sz],cost[sz];
int par[sz], col[sz];

priority_queue< pair<int, pair<int,int> > ,
vector< pair<int, pair<int,int> > >,
greater< pair<int,pair<int,int> > > >pq;

int prims(int st)
{
    for (int i = 0; i<adj[st].size(); i++)
        pq.push({cost[st][i], {st,adj[st][i]}});
    vector< pair<int, pair<int,int>  > > ans;
    col[st]=1;

    int c, u, v, tot=0;
    while(!pq.empty())
    {
        c = pq.top().first;
        u = pq.top().second.first;
        v = pq.top().second.second;
        pq.pop();
        if(!col[u] || !col[v])
        {
            ans.pb( {c, {u,v} } );
            tot+=c;
            u = col[u]?v:u;
            col[u]=1;
            for (int i = 0; i<adj[u].size(); i++)
            {
                if(! col[ adj[u][i] ])
                    pq.push({cost[u][i],
                            {u,adj[u][i]} });
            }
        }
    }

    for (int i = 0; i<ans.size(); i++)
    {
        cout<<i<<":"<<ans[i].first<<" -> ("
        <<ans[i].second.first << "," <<
        ans[i].second.second << ")\n";
    }
    return tot;
}
int main()
{
    _
    int cas = 1,st,n,m,x,y,z;


    cin>>n>>m;

    for (int i = 0; i<m; i++)
    {
        cin>>x>>y>>z;
        adj[x].pb(y);
        cost[x].pb(z);
        adj[y].pb(x);
        cost[y].pb(z);
    }

    cin>>st;

    cout<<"Total Cost of MST = "<<prims(st)<<"\n";


//    end = clock();
//    time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
//    cerr<<"Time spent = "<<time_spent<<endl;

   return 0;
}
/**
6 8
1 2 1
1 3 1
1 5 1
2 4 3
2 5 2
3 6 2
4 6 3
5 6 5
1
*/