poj 1125

 poj 1125

题目大意是股票经纪人要在一群人中散布一个谣言，而谣言只能在亲密的人中传递，题目各处了人与人之间的关系及传递谣言所用的时间，要求程序给出应以那个人为起点，可以在最短的时间内让所有的人都得知这个谣言。要注意从a到b传递的时间不一定等于从b到a的时间，如果没有方案能够让每一个人都知道谣言，则输出"disjoint"。（有关图的连通性，你懂得！但好像不用考虑这种情况一样能AC，只能说测试数据有点小水！）
题目数据的输入第一行为n，代表总人数，当n=0时结束程序，接着n行，第i+1行的第一个是一个整数t，表示第i个人与t个人的关系要好，接着有t对整数，每对的第一个数是j，表示i与j要好，第二个数是从i直接传递谣言到j所用的时间，数据的输出是两个整数，第一个为选点的散布谣言的起点，第二个整数时所有人得知谣言的最短时间
例如，对于数据1，
可知如果从3开始传播，则1，2得知谣言的时间都是2，所用的时间比从1，2开始传播所用的时间要短，故程序的输出时3 2；
代码如下：

#include<iostream>
using namespace std;
const int Max = 105;



int main()
{
    int n, m, i, j, k, minute;
    int map[Max][Max];
	
    while(cin >> n && n != 0)
	{
        for(i = 1; i <= n; i ++)
            for(j = 1; j <= n; j ++)
                map[i][j] = 999; 
			for(i = 1; i <= n; i ++)
			{
				cin >> m;
				while(m --)
				{
					cin >> j >> minute;
					map[i][j] = minute;
				}
			}
			
			
			
			for(k = 1; k <= n; k ++)   //  floyd。
				for(i = 1; i <= n; i ++)
					for(j = 1; j <= n; j ++)
						if(map[i][k] + map[k][j] < map[i][j])
							map[i][j] = map[i][k] + map[k][j];
						
						
						
						int sum, stockbroker, time = 9999;
						for(i = 1; i <= n; i ++)
						{
							sum = 0;
							for(j = 1; j <= n; j ++)    //  求出以第i个stockbroker为起点的所用最少时间。
								if(i != j && map[i][j] > sum)
									sum = map[i][j];
								if(sum < time)
								{
									stockbroker = i;
									time = sum;
								}
						}
						cout << stockbroker << ' ' << time << endl;
	}
	return 0;
}