一、题目大意

可以说理解题目比解题难~~明显的多源最短路径，我用的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 0x3f3f3f3f

using namespace std;

int map[MAXN][MAXN];

void Floyd(int sbNum) {

    //i to j
    for (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;

        //init
        for (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;
        else
            cout<<who<<" "<<time<<endl;
    }

    return 0;
}