4671794_ac_47ms_324k.cpp

部分PKU上的源码

#include<iostream>
using namespace std;
int map[105][105];
int n;
bool used[105];
int dis[105];
int pickmin()
{
	int re=0,tmin=1000009;
	for(int count=1;count<=n;count++)
	{
		if(dis[count]<tmin&&used[count]==false)
		{
			re=count;
			tmin=dis[count];
		}
	}
	return re;
}
void prim()
{
	memset(used, false,sizeof(used));
	int count;
	for(count=1;count<=n;count++) dis[count]=map[1][count];
	used[1]=true;
	int length=0;
	for(count=1;count<=n-1;count++)
	{
		int temp=pickmin();
		//if(temp==0) cout<<"worng"<<endl;
		length+=dis[temp];
		used[temp]=true;
		for(int i=1;i<=n;i++) if(dis[i]>map[temp][i]) dis[i]=map[temp][i];
	}
	cout<<length<<endl;
}
int main()
{
	while(cin>>n)
	{
		int i,j;
		for(i=1;i<=n;i++)
		{
			for(j=1;j<=n;j++)
			{
				cin>>map[i][j];
			}
		}
		prim();
	}
	return 0;
}