POJ 1125(マルチソース最短パス-Floydアルゴリズム)

http://poj.org/problem?id=1125
最初のFloyd記念.
題意分析:
すべての株式マネージャーはすべてデマを伝えるのが好きで、すべての株式マネージャーはすべて知人の言うことだけを信じて、デマは時間が必要で、これらの株式マネージャーの中の一人にデマを教えて、彼はこのデマを伝えて、どのようにこの人を選んで、他のすべての人に知っていて、しかも最後にその人が知っている時間は最も少ないです.
解決方法:
一度遍歴して、各点をソース点として算出する場合、最長パスはいくらですか.その中で最も短いものを求めればよい.

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn =100+5;
const int inf =1000000;
int map[maxn][maxn],dist[maxn][maxn],Max[maxn],n;
void floyd()
{
    memset(dist,0,sizeof(dist));
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++){
            if(i==j) continue;
            dist[i][j]=map[i][j];
       }
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                if(dist[i][j]>dist[i][k]+dist[k][j])
                    dist[i][j]=dist[i][k]+dist[k][j];
}
int main()
{
    while(~scanf("%d",&n)&&n)
    {
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                 map[i][j]=inf;
        int num,u,val;
        for(int i=1;i<=n;i++){
            scanf("%d",&num);
            while(num--){
                scanf("%d%d",&u,&val);
                map[i][u]=val;
            }
        }
        floyd();
        memset(Max,0,sizeof(Max));
        for(int i=1;i<=n;i++)//     
            for(int j=1;j<=n;j++)
                Max[i]=max(Max[i],dist[i][j]);
        int Min=inf,idx;
        for(int i=1;i<=n;i++)//      
            if(Min>Max[i]) Min=Max[i],idx=i;
        if(Min==inf) printf("disjoint
");
        else printf("%d %d
",idx,Min);
    }
    return 0;
}