Minimum spanning tree

Prim.cpp

//Prim - Minimum spanning tree

#include<iostream>
#include<algorithm>
#include<functional>
#include<set>
#include<vector>
#include<queue>
#include<cstring>

using namespace std;

const int MAX_POINT_NUMBER=100000;
const int MAX_EDGE_NUMBER=10000000;
class edge
{
public:
	int dest,ori;
	int length;
	int id;
};

bool operator< (const edge &a,const edge &b)
{
	return a.length>b.length;
}

vector<edge>g[MAX_POINT_NUMBER];
priority_queue<edge>GraphSet;
bool usedEdgeId[MAX_EDGE_NUMBER];
bool connected[MAX_POINT_NUMBER];
int m,n;

int prim()
{
	int point=0;
	int cost=0;
	while(!GraphSet.empty())GraphSet.pop();
	memset(usedEdgeId,0,sizeof(usedEdgeId));
	memset(connected,0,sizeof(connected));
	connected[point]=true;
	for(int i=0;i<n-1;i++)
	{
		for(vector<edge>::iterator iter=g[point].begin();iter!=g[point].end();iter++)
		{
			if(!usedEdgeId[(*iter).id])
			{
				usedEdgeId[(*iter).id]=true;
				GraphSet.push(*iter);
			}
		}
		while(!GraphSet.empty())
		{
			edge tmp=GraphSet.top();
			GraphSet.pop();
			if(!connected[tmp.dest])
			{
				connected[tmp.dest]=true;
				//cout <<"Connected: "<<tmp.ori<<" "<<tmp.dest<<endl;
				cost+=tmp.length;
				point=tmp.dest;
				break;
			}
		}
	}
	return cost;
}

int main()
{
	cin >>n>>m;
	for(int i=0,id=0;i<m;i++)
	{
		int a,b,v;
		cin >>a>>b>>v;a--;b--;
		edge e;
		e.id=id++;
		e.ori=a;e.dest=b;e.length=v;
		g[a].push_back(e);
		e.ori=b;e.dest=a;e.length=v;
		g[b].push_back(e);
	}
	cout <<prim()<<endl;
	return 0;
}