শুক্রবার, ২৮ জুলাই, ২০১৭

UVA 11631 - Dark roads

#include<bits/stdc++.h>
#define fr(i1,m) for(int i1=0;i1<m;i1++)
#define max 20000
using namespace std;
struct pq
{
    int node,cost;
    bool operator<(const pq &b)const
    {
        return cost>b.cost;
    }
};
int prims(vector<pq>mst[],int source,int node)
{
    priority_queue<pq>p;
    long taken[max]={0},sum,i,j,s;
    pq u,v;
    v.node=source;
    s=v.cost=0;
    p.push(v);
    while(!p.empty())
    {
        u=p.top();
        if(taken[u.node]==0)
        s+=u.cost;
        taken[u.node]=1;
        p.pop();
        for(i=0;i<mst[u.node].size();i++)
        {
            if(taken[mst[u.node][i].node]==0)
            {
                v.node=mst[u.node][i].node;
                v.cost=mst[u.node][i].cost;
                p.push(v);
            }
        }

    }
    return s;

}
int main()
{
    int nodes,edge,i,j,x,y,z,val;
    vector<pq>mst[max];
    pq v;
    while(scanf("%d%d",&nodes,&edge)==2)
    {
        if(nodes==0&&edge==0)break;
        long t=0;
        for(i=0;i<max;i++)
        mst[i].clear();
        for(i=0;i<edge;i++)
        {
            cin>>x>>y>>z;
            v.cost=z;
            v.node=y;
            mst[x].push_back(v);
            v.node=x;
            mst[y].push_back(v);
            t=t+z;

        }
        val=prims(mst,0,nodes);
        cout<<t-val<<endl;
    }
}

কোন মন্তব্য নেই:

একটি মন্তব্য পোস্ট করুন

Factorization with prime Sieve

vector <int> prime; char sieve[1000009]; int N=1000009; void primeSieve ( ) { sieve[0] = sieve[1] = 1; prime.push_back(2); ...