[poj 1125]Stockbroker Grapevine[Floyd最短路]

題意:

股票經紀人之間傳遞謠言. 給出一個股票經紀人的聯系網絡: a聯系到b用時w.

求: 選擇哪一個人作為謠言的源頭可以使得謠言傳到所有人最快, 以及傳到所有人所用時間.

思路:

Floyd算法可以求出全源最短路. 只要枚舉每一個源s, 記錄s到其他人的最大時間t, 比較t, 最小的那個對應的s即為所求.

#include <cstdio>
#include <cstring>

using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 105;

int adj[MAXN][MAXN];
int n;

void Floyd()
{
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                if(adj[i][j]>adj[i][k] + adj[k][j])
                    adj[i][j] = adj[i][k] + adj[k][j];
}

int main()
{
    while(scanf("%d",&n),n)
    {
        memset(adj,0x3f,sizeof(adj));
        for(int i=1,m;i<=n;i++)
        {
            adj[i][i] = 0;//到自己的時間為0
            scanf("%d",&m);
            for(int k=1,j,w;k<=m;k++)
            {
                 scanf("%d %d",&j,&w);
                 adj[i][j] = w;
            }
        }
        Floyd();
        int s = 0,cost = INF;
        int tot;
        for(int i=1;i<=n;i++)
        {
            tot = 0;
            for(int j=1;j<=n;j++)
            {
                if(tot<adj[i][j])
                    tot = adj[i][j];
            }
            if(tot<cost)
            {
                cost = tot;
                s = i;
            }
        }
        if(cost == INF)
            printf("disjoint\n");
        else
            printf("%d %d\n",s,cost);
    }
}