学步园

题意:

股票经纪人之间传递谣言. 给出一个股票经纪人的联系网络: 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);
    }
}

此题数据目测较弱= =