poj 1125 Stockbroker Grapevine（多源最短）

题意：输入n个经纪人，以及他们之间传播谣言所需的时间，

问从哪个人開始传播使得全部人知道所需时间最少。这个最少时间是多少

分析：由于谣言传播是同一时候的，对于某条路径使得全部人都知道的时间。不是时间的总和，而是路径中最长的边

从多条路径的最长边，找出最小值。由于为多源最短路，用Floyd比較方便

#include<stdio.h>

#include<limits.h>

int a[105][105];

void floyd(int n)

{

    int i,j,k,s,pos;

    for(k=1;k<=n;k++)

        for(i=1;i<=n;i++)

            for(j=1;j<=n;j++)

                if(a[i][k]!=INT_MAX&&a[k][j]!=INT_MAX&&a[i][k]+a[k][j]<a[i][j])

                    a[i][j]=a[i][k]+a[k][j];

    k=INT_MAX;

    pos=0;

    for(i=1;i<=n;i++){

        s=0;

        for(j=1;j<=n;j++)             //先求出路径中的最长边为总传播时间

            if(i!=j&&a[i][j]>s)

                s=a[i][j];

        if(s<k){            //再找出传播时间的最小值

            k=s;

            pos=i;

        }

    }

    if(k==INT_MAX)

        printf("disjoint\n");

    else

        printf("%d %d\n",pos,k);

}

int main()

{

    int n,m,i,j,b,t;

    while(scanf("%d",&n)!=EOF){

        if(n==0)

            break;

        for(i=1;i<=n;i++)

            for(j=1;j<=n;j++)

                a[i][j]=INT_MAX;

        for(i=1;i<=n;i++){

            scanf("%d",&m);

            for(j=1;j<=m;j++){

                scanf("%d%d",&b,&t);

                a[i][b]=t;              //单程

            }

        }

        floyd(n);

    }

    return 0;

}