g++是0Ms，C++ 16MS

#include<cstdio>
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<numeric>
#include<cmath>
#include<bitset>
#include<set>
#include<queue>

using namespace std;

int w[30][30];

typedef struct Node
{
	int sequenceNumber;
	int weight;
};

bool cmp(Node* n1,Node* n2)
{
	if(n1->weight <= n2->weight)
		return false;
	else
		return true;
}

long long prim(int n)
{
	long long min_len =0;
	int u,v,i,j;
	bitset<101> bit;//判断节点是否还在队列中
	vector<Node*> Prqueue;//优先级队列
	Node* node = new Node();
	node->sequenceNumber = 0;
	node->weight = 0;
	Prqueue.push_back(node);
	for(i = 1; i < n; ++i)
	{
		Node* node = new Node();
		node->sequenceNumber = i;
		node->weight = 400000000;
		Prqueue.push_back(node);
	}
	
	Node* tmp;
	while(!Prqueue.empty())
	{
		tmp = Prqueue.front();
		min_len += tmp->weight;
		Prqueue.erase(Prqueue.begin());
		u = tmp->sequenceNumber;
		bit.set(u);
		for(i = 0; i < n; ++i)
		{
			if(w[u][i] != 0) //节点u的所有邻接节点
			{
				v = i;
				if( !bit.test(v)) //&& w[u][v] < 
				{
					//for(j = 1; i < Prqueue.size(); ++j)
					j = 0;
					while(j < Prqueue.size())
					{
						if(Prqueue[j]->sequenceNumber == v && w[u][v] < Prqueue[j]->weight)
						{
							Prqueue[j]->weight = w[u][v];
							break;
						}
						++j;
					}
				}
			}
		}
		make_heap(Prqueue.begin(),Prqueue.end(),cmp);
	}
	return min_len;
}

int main(int argc, char* argv[])
{
	int n,i,j,num,x,y,dist;
	char base,other;
	int tmp;
	while(true)
	{
		scanf("%d",&n);
		if(n == 0)
			break;
		tmp = n;
		//getchar();
		cin.get();
		while(n > 1)
		{
			//scanf("%c %d",&base,&num);
			//getchar();
			cin>>base>>num;
			for(i = 0; i < num; ++i)
			{
				//scanf("%c %d",&other,&dist);
				cin>>other>>dist;
				//getchar();
				x = abs(base - 'A');
				y = abs(other - 'A');
				w[x][y] = w[y][x] = dist;
			}
			--n;
		}
		cout<<prim(tmp)<<endl;
		for(i = 0; i <= 28; ++i)
			for(j = 0; j <= 28; ++j)
				w[i][j] = 0;
	}
	return 0;
}

• Re:Prim超时果真是scanf+getchar，换成cin就可以了 (2322) laintime 2009-10-29 21:44:31
• Re:Prim超时果真是scanf+getchar，换成cin就可以了 (9) laintime 2009-10-29 21:45:25