4667609_ac_766ms_684k.cpp

部分PKU上的源码

#include<iostream>
#define MAXNUM 99999999
using namespace std;
int n;
int map[505][505];
int dis[505];
bool used[505];
int pickmin()
{
	int tmin=MAXNUM,re=0;
	for(int count=1;count<=n;count++)
	{
		if(dis[count]<tmin&&used[count]==false)
		{
			tmin=dis[count];
			re=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 longness=0;
	for(count=1;count<=n-1;count++)
	{
		int temp=pickmin();
		used[temp]=true;
		if(dis[temp]>longness) longness=dis[temp];
		for(int i=1;i<=n;i++)
		{
			if(dis[i]>map[temp][i]) dis[i]=map[temp][i];
		}
	}
	cout<<longness<<endl;
}
int main()
{
	int testnumber;
	cin>>testnumber;
	int count;
	for(count=0;count<testnumber;count++)
	{
		cin>>n;
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				cin>>map[i][j];
		prim();
	}
	return 0;
}