一、题目大意
可以说理解题目比解题难~~明显的多源最短路径，我用的Floyd，Floyd也可以算是dp的一种。
题目可能有多组测试数据，每个测试数据的第一行为经纪人数量N（当N=0时，输入数据结束），然后接下来N行描述第i（1<=i<=N）个经纪人与其他经纪人的关系。每行开头数字M为该行对应的经纪人有多少个经纪人朋友（该节点的出度，可以为0），然后紧接着M对整数，每对整数表示成a,b,则表明该经纪人向第a个经纪人传递信息需要b单位时间（即第i号结点到第a号结点的孤长为b），整张图为有向图，即弧Vij 可能不等于弧Vji。当构图完毕后，求当从该图中某点出发，将“消息”传播到整个经纪人网络的最小时间，输出这个经纪人号和最小时间。最小时间的判定方式为——从这个经纪人（结点）出发，整个经纪人网络中最后一个人接到消息的时。如果有一个或一个以上经纪人无论如何无法收到消息，输出“disjoint”（有关图的连通性，你们懂得，但据其他同学说，POJ测试数据中不会有，就是说，你不判定，一样能过，题目数据够水的）。
二、AC code
题目要求传遍整个网络的时间，我没有在Floyd算法中处理，是之后再来一个二层循环，但是鉴于Floyd本身的复杂度，来一个 O(n^2)也显得不那么耗时了。当然也可以用空间换时间，申请一个数组保存从这个人开始传遍网络最快的时间，在每次Floyd处理中存储，最后一次遍历这个数组就可以得出结果。
#include <stdio.h>
#include <iostream>
#define MAXN 102
#define INF 0x3f3f3f3fusing namespace std;int map[MAXN][MAXN];void Floyd(int sbNum) {//i to jfor (int k=0;k<sbNum;++k) {for (int i=0;i<sbNum;++i) {for (int j = 0; j < sbNum; j++) {map[i][j] = (map[i][k]+map[k][j]) < map[i][j] ?map[i][k]+map[k][j]:map[i][j];}}}}int main()
{//freopen("input.txt","r",stdin);while (1) {int sbNum;cin>>sbNum;if( !sbNum )break;//initfor (int i=0;i<sbNum;++i) {for (int j = 0; j < sbNum; j++) {map[i][j] = INF;}}for (int i=0;i<sbNum;++i) {int n;cin>>n;for (int j = 0; j < n; j++) { //具体到哪个人int otherContact;cin>>otherContact;cin>>map[i][otherContact-1];}}//输入完毕Floyd(sbNum);int who = -1, time =INF;for (int i=0;i<sbNum;++i) {int tmpMax = -1;for (int j = 0; j < sbNum; j++) { //到其他人最大的作为最快速度if( i == j )continue;tmpMax = tmpMax>map[i][j]? tmpMax:map[i][j];}if( time > tmpMax ) {time = tmpMax;who = i+1;}}if( INF == time )cout<<"disjoint"<<endl;elsecout<<who<<" "<<time<<endl;}return 0;
}