#include<iostream>
#include<vector>
using namespace std;

const int MAX_TIME = 100000;

void floyd(vector< vector<int> > &distances){
	int sz = distances.size();
	for(int i = 0; i < sz; i++)
		for(int j = 0; j < sz; j++)
			for(int k = 0; k < sz; k++){
				int t_dis = distances[i][k] + distances[k][j];
				if(distances[i][j] > t_dis)
					distances[i][j] = t_dis;
			}
}

int main(){
	int p_num;
	while(cin >> p_num,p_num){
		vector< vector<int> > matrix;
		int i,j;

		for(i = 0; i < p_num; i++){
			vector<int> vp;
			for(j = 0; j < p_num; j++)
				if(i == j)
					vp.push_back(0);
				else
					vp.push_back(MAX_TIME);
			matrix.push_back(vp);
		}

		int n;
		for(i = 0; i < p_num; i++){
			cin >> n;
			int p,t;
			for(j = 0; j < n; j++){
				cin >> p >> t;
				matrix[i][p-1] = t;
			}
		}

		floyd(matrix);
		
		int min = MAX_TIME;
		int min_index = 0;

		for(i = 0; i < p_num; i++){
			int max = 0;
			
			for(j = 0; j < p_num; j++){
				if( max < matrix[i][j] )
					max = matrix[i][j];
			}

			if(min > max){
				min = max;
				min_index = i;
			}
		}

		if(min == MAX_TIME)
			cout << "disjoint" << endl;
		else
			cout << min_index + 1 << " " << min << endl;
	}
	return 0;
}

各位大侠帮看看。

• 这是floyed算法的一种标准错误写法 (371) fanhqme 2009-04-11 20:59:35
  • Re:这是floyd算法的一种标准错误写法: floyed (0) lijinwu 2010-03-10 11:31:55
• Re:无语了，wa了n次，真不知道哪地方出问题了！！！ (9) autumncat 2010-02-17 22:13:41