4650940_ce.cpp

部分PKU上的源码

#include<iostream>
using namespace std;
bool open[105];
int time[105][105];
int dis[105];
int n;
bool disjoint;
bool have;
int max;
int person,min;
int pickmin()
{
	int tmin=1000000,re=-1;
	for(int count=1;count<=n;count++)
	{
		if(dis[count]<tmin&&open[count]==false)
		{
			re=count;
			tmin=dis[count];
		}
	}
	return re;
}
void dj(int x)
{
	int count;
	for(count=1;count<=n;count++) {dis[count]=10000000;open[count]=false;}
	dis[x]=0;
	int opn=0;
	while(opn<n)
	{
		int temp=pickmin();
		if(temp==-1) break;
		open[temp]=true;
		opn++;
		for(int i=1;i<=n;i++)
		{
			if(i!=temp&&time[temp][i]!=-1)
			{
				if(dis[i]>dis[temp]+time[temp][i])
				{
					dis[i]=dis[temp]+time[temp][i];
				}
			}
		}
	}
	max=-1;
	disjoint=false;
	for( count=1;count<=n;count++)
	{
		if(dis[count]!=1000000)
		{
			if(dis[count]>max) max=dis[count];
		}
		else {disjoint=true;return;}
	}
}
int main()
{
	while(cin>>n)
	{
		if(n==0) return 0;
		memset(time,-1,sizeof(time));
		int i,j,temp,t1,t2;
		for(i=1;i<=n;i++)
		{
			cin>>temp;
			for(j=1;j<=temp;j++)
			{
				cin>>t1>>t2;
				time[i][t1]=t2;
			}
		}
		have=false;
		min=10000000;
		for(i=1;i<=n;i++)
		{
			dj(i);
			if(disjoint==false&&max<min)
			{
				person=i;
				min=max;
				have=true;
			}
		}
		if(have) cout<<person<<" "<<min<<endl;
		else cout<<"disjoint"<<endl;
	}
	return 0;
}