poj1125 Stockbroker Grapevine 圖論，任意兩點間最短路徑，floyd

題目連結：http://poj.org/problem?id=1125

題目大意：翻譯來自小優師姐^_^

        衆所周知，證券經紀業依靠的就是過度的傳言。您需要想出股票經紀人中傳播假情報的方法，讓您的雇主在股票市場的占據優勢。為了獲得最大的效果，你必須蔓延最快的方式謠言。 

        不幸的是你，股票經紀人資訊隻信任他們的“可靠來源”，這意味着你在你傳播謠言之前必須考慮到他們的接觸結構。它需要特定股票經紀人和一定的時間把謠言傳遞給他的每一位同僚。你的任務将是寫一個程式，告訴您選擇哪一個股票經紀人作為謠言的出發點和所花費多少時間将謠言擴散到整個社會的股票經紀人。這一期限是衡量過去的人收到資訊所需的時間。 

輸入 

        你的程式包含多組股票經紀人的輸入資料。每組以股票經紀人的人數開始。接下來的幾行是每個經紀人與其他人接觸的一些資訊，包括這些人都是誰，以及将訊息傳達到他們所需的時間。每個經紀人與其他人接觸資訊的格式如下：開頭的第一個數表示共有n個聯系人，接下來就有n對整數。每對整數列出的第一個數字指的是一個聯系人（例如，一個'1'是指編号1的人），其次是在傳遞一個資訊給那個人時所采取分鐘的時間。沒有特殊的标點符号或空格規則。 

        每個人的編号為1至經紀人數目。所花費的傳遞時間是從1到10分鐘（含10分種）。股票經紀的人數範圍是從1到100。當輸入股票經紀人的人數為0時，程式終止。 

        輸出 

        在對于每一組資料，你的程式必須輸出一行，包括的資訊有傳輸速度最快的人，以及在最後一個人收到消息後，所總共使用的時間（整數分鐘計算）。 

        你的程式可能會收到的一些關系會排除一些人，也就是有些人可能無法通路。如果你的程式檢測到這樣一個破碎的網絡，隻需輸出消息“disjoint”。請注意，所花費的時間是從A傳遞消息到B，B傳遞資訊到A不一定是花費同樣的傳遞時間，但此類傳播也是可能的。

思路：抽象為圖論問題，通過floyd算法求得人一兩點間的最短路，然後枚舉每一點作為源點，求得相對應的到達任意一點的最長路，然後求得這些最長路中的最短的一個，就得到了答案。如果求得的這個最長路中的最短的一個小于一開始假定的無限長，則說明根本不是連通圖，就是題目所說的 “disjoint“ 的情況。

///2014.7.19
///poj1125

//Accepted  740K    0MS G++ 1554B   2014-07-19 20:21:10

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

/*=====   Floyd算法       ======*/
const int MAXL = 0x3f3f3f3f;  //假設的無窮遠
int n;  //點數
const int N = 100;   //問題情況中最大的點數——————由實際問題情況修改
int dist[N+5][N+5];
void floyd(){
    for(int k=0 ; k<n ; k++){
        for(int i=0 ; i<n ; i++){
            for(int j=0 ; j<n ; j++){
                if( i!=j && dist[i][j] > dist[i][k]+dist[k][j] )
                    dist[i][j] = dist[i][k]+dist[k][j];
            }
        }
    }
}

void init(){
    for(int i=0 ; i<n ; i++)
        for(int j=0 ; j<n ; j++)
            if( i==j )
                dist[i][j] = 0;
            else
                dist[i][j] = MAXL;

    for(int i=0 ; i<n ; i++){
        int nn,num,t;
        scanf("%d",&nn);
        for(int j=0 ; j<nn ; j++){
            scanf("%d%d",&num,&t);
            num --;
            dist[i][num] = t;
        }
    }
}

void output(){
    int maxlength;
    int min_in_max = MAXL;
    int aim;
    for(int i=0 ; i<n ; i++){
        maxlength = 0;
        for(int j=0 ; j<n ; j++)
            if( maxlength < dist[i][j] )
                maxlength = dist[i][j];
        if( maxlength < min_in_max )
            min_in_max = maxlength, aim = i;
    }

    if( min_in_max < MAXL )
        cout<<aim+1<<' '<<min_in_max<<endl;
    else
        cout<<"disjoint"<<endl;
}

int main(){
    while( cin>>n && n ){
        init();
        floyd();
        output();
    }
    return 0;
}