POJ1125 Floyd

#include<iostream>
using namespace std;

const int MAX=105;
const int INF=1<<27;

int n;
int w[MAX][MAX];
int d[MAX][MAX];

void init(){
	int i,j;
	for(i=1;i<=n;i++){
		for(j=1;j<=n;j++){
			d[i][j]=w[i][j]=(i==j?0:INF);
		}
	}
}

void floyd(){
	int k,i,j;
	for(k=1;k<=n;k++){
		for(i=1;i<=n;i++){
			for(j=1;j<=n;j++){
				if(d[i][k]+d[k][j]<d[i][j])
					d[i][j]=d[i][k]+d[k][j];
			}
		}
	}
}

void output(){
	int startPos=-1;
	int minTime=INF;

	int i,j;
	for(i=1;i<=n;i++){
		int maxTime=-1;
		for(j=1;j<=n;j++){
			maxTime=(maxTime>d[i][j]?maxTime:d[i][j]);
		}
		if(maxTime<minTime){
			minTime=maxTime;
			startPos=i;
		}
	}

	if(minTime<INF){
		printf("%d %d\n",startPos,minTime);
	}else{
		printf("%s\n","\"disjoint\"");
	}
}

int main(){

	scanf("%d",&n);
	while(n>0){

		init();

		int i;
		for(i=1;i<=n;i++){
			int m=0;
			scanf("%d",&m);

			int count;
			for(count=1;count<=m;count++){
				int j,weight;
				scanf("%d%d",&j,&weight);
				d[i][j]=w[i][j]=weight;
			}
		}

		floyd();

		output();

		scanf("%d",&n);
	}

	system("pause");
	return 0;
}