ACM竞赛最小生成树(MST)问题的扩展.pdf

: .
最小生成树(MST)问题的扩展
k;
int w;
};

bool operator < ( const CNode & d1, const CNode & d2 ) {
return > ; //priority_queue总是将最大的元素出列
}
int aDist[30010];
priority_queue<CNode> pq;
bool bUsed[30010]={0};
//vector<CNode> v[30010]; error,如果用这个，则在poj山会超时。说明vector对象的初始化，也是需要可观时间的
vector<vector<CNode> > v;
const unsigned int INFINITE = 100000000;
int main()
{
int N,M,a,b,c;
int i,j,k;

CNode p, q;

scanf("%d%d", & N, & M );

();
(N+1);

memset( bUsed,0,sizeof(bUsed));
for( i = 1;i <= M; i ++ ) {

scanf("%d%d%d", & a, & b, & c);
= b;
= c;
v[a].push_back( p);
}
= 1;
= 0;
( p);
while( ! ()) {
p = ();
();
if( bUsed[])
continue;