首页 > 代码库 > poj1125--Floyd

poj1125--Floyd

题解:

       有N个股票经济人可以互相传递消息,他们之间存在一些单向的通信路径。现在有一个消息要由某个人开始传递给其他所有人,问应该由哪一个人来传递,才能在最短时间内让所有人都接收到消息。

       显然,用Floyd算法,然后选出每个点到其他点的最长距离当中的最短距离。


/** \brief poj 1125 Floyd
 *
 * \param date 2014/7/31
 * \param state AC
 * \return memory 756k time 0ms
 *
 */

#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

const int MAXN=101;
int DistMap[MAXN][MAXN];
int n;
const int INF=20;
//int best;
//int num;

//bool Floyd()
void Floyd()
{
    for(int k=1;k<=n;k++)
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(i!=j && DistMap[i][j]>DistMap[i][k]+DistMap[k][j])
                    DistMap[i][j]=DistMap[i][k]+DistMap[k][j];
            }
        }
    }
    //
    int maxlength, min_in_max=INF,flag_source;
    for(int i=1;i<=n;i++)//以i点作为各通路源点
    {
        maxlength=0;
        for(int j=1;j<=n;j++)
        {
            if(i!=j && DistMap[i][j]>maxlength)//寻找i到j的最长路径
            {
                maxlength=DistMap[i][j];
            }
        }
        if(min_in_max>maxlength)
        {
            min_in_max=maxlength;//寻找最长路径中的最短路
            flag_source=i;
        }
    }

    /*Output*/
    if(min_in_max<INF)
        cout<<flag_source<<' '<<min_in_max<<endl;
    else
        cout<<"disjoint"<<endl;
}

int main()
{
    //cout << "Hello world!" << endl;
    //freopen("input.txt","r",stdin);
    while(scanf("%d",&n)!=EOF)
    {
        memset(DistMap,INF,sizeof(DistMap));
        if(n==0)break;
        int num,v,w;
        for(int i=1;i<=n;i++)
        {
            cin>>num;
            for(int j=0;j<num;j++)
            {
                //DistMap[][]
                scanf("%d%d",&v,&w);
                DistMap[i][v]=w;
            }
        }
        //Floyd
        //if(Floyd()==false)
        //    cout<<"disjoint"<<endl;
        //else cout<<num<<" "<<best<<endl;
        Floyd();
    }
    return 0;
}