POJ 1125(用floyd算法的 + 贪心)_floyd算法采用贪心

/*
	先求出每对顶点的最短距离，再取出每组（一点到全部点的最短距离为一级） 的最大距离，再在这些最大距离中，取出最小距离，即可； 
*/
#include <iostream>
#include <fstream>
#include <cstring>
#include <algorithm>
using namespace std;
const int INF = 0xffffff;
int map[105][105];
void init(int count){
	for(int i=1; i<=count; ++i){
		for(int j=1; j<=count; ++j){
			if(i!=j){
				map[i][j] = INF;
			}else{
				map[i][j] = 0;
			}
		}
	}
}
void floyd(int n){
	for(int k=1; k<=n; ++k){
		for(int i=1; i<=n; ++i){
			for(int j=1; j<=n; ++j){
				map[i][j] = min(map[i][j], map[i][k] + map[k][j]);
			}
		}
	}
}
int main(){
	int count,path,y,temp;
	while(1){	
		scanf("%d",&count);
		if(count == 0) break;
		init(count);
		for(int i=1; i<=count; ++i){		
			cin>>path;
			for(int j=1; j<=path; ++j){
				cin>>y>>temp;
				map[i][y] = temp;
			}
		}	
		floyd(count);	
		int res = INF, loc;
		for(int i=1; i<=count; ++i){
			temp = -(1<<30);
			for(int j=1; j<=count; ++j){
				temp = max(temp, map[i][j]);
			}
			if(res > temp){
				loc = i;
				res = temp;
			}
		}
		if(res == INF){
			printf("disjoint\n");
			continue;
		}
		printf("%d %d\n",loc, res);
	}
	return 0;
}