POJ 1125 Stockbroker Grapevine(Floyd)

POJ 1125 Stockbroker Grapevine(Floyd)

http://poj.org/problem?id=1125

题意:给你一个有向图,现在要你找一个起点来传播消息,问你要找那个点传播能使得其他所有点最快时间收到消息.即求到其他所有点的最短距离中的最大值最小的那个点.

分析:

建图,Floyd算法求解.然后一次求出所有点作为源点时的最短距离最大值即可.然后比较.

注意如果图中没有任何一个节点能完全的到达其他n-1个节点,那么这个输出” disjoint”.

AC代码:

#include<cstdio>
#include<cstring>
#include<algorithm>
#define INF 1e9
using namespace std;
const int maxn = 100+10;
int n;
int d[maxn][maxn];
int time[maxn];
void floyd()
{
    for(int k=1;k<=n;k++)
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
        if(d[i][k]<INF && d[k][j]<INF)
            d[i][j] = min(d[i][j],d[i][k]+d[k][j]);

    for(int i=1;i<=n;i++)//time保存个点到其他点的最短距离的最大值
        time[i]=-1;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)if(i!=j)
        time[i]=max(time[i],d[i][j]);
}
int main()
{
    while(scanf("%d",&n)==1&&n)
    {
        for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            d[i][j]= i==j?0:INF;

        for(int i=1;i<=n;i++)
        {
            int m; scanf("%d",&m);
            while(m--)
            {
                int u,t;
                scanf("%d%d",&u,&t);
                d[i][u]=t;
            }
        }
        floyd();
        int id=-1,min_val=INF;//最小传播时间
        for(int i=1;i<=n;i++)
        if(min_val > time[i])
        {
            id=i;
            min_val = time[i];
        }
        if(min_val==INF) printf("disjoint\n");
        else printf("%d %d\n",id,min_val);
    }
    return 0;
}