Stockbroker Grapevine--POJ 1125

时间：2010-08-19 来源：勇泽

1、题目类型：图论、最短路径、Floyd算法。

2、解题思路：Floyd算法的简单应用

3、注意事项：注意n为0的特殊情况。

4、实现方法:

#include<iostream>
#define inf 9999999
#include<algorithm>
using namespace std;

int n,map[110][110];

void Floyd()
{
    int i,j,k,dis[110][110];
    memset(dis,0,sizeof(dis));
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
            dis[i][j]=inf;
    }
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
        {
            if(i!=j)
                dis[i][j]=map[i][j];
        }
    }
    for(k=1;k<=n;k++)
    {
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
            {
                if(dis[i][j]>dis[i][k]+dis[k][j])
                    dis[i][j]=dis[i][k]+dis[k][j];
            }
    }
    int ans=-1,pos=0,arr[110];
    for(i=1;i<=n;i++)
    {
        ans=-1;
        for(j=1;j<=n;j++)
        {
            if(i!=j)
                if(ans<dis[i][j])
                {
                    ans=dis[i][j];
                    pos=i;
                }        
        }
        arr[pos]=ans;
    }
    pos=min_element(arr+1,arr+n+1)-arr;
    if(*min_element(arr+1,arr+n+1)==inf)
        cout<<"disjoint"<<endl;
    else
        cout<<pos<<' '<<*min_element(arr+1,arr+n+1)<<endl;
}
int main()
{
    while(cin>>n && n)
    {
        int i,j,m,a,t;
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
                map[i][j]=inf;
            for(i=1;i<=n;i++)
            {
                cin>>m;
                for(j=0;j<m;j++)
                {
                    cin>>a>>t;
                    map[i][a]=t;
                }
            }
            if(n==1)
            {
                cout<<n<<' '<<'0'<<endl;
                continue;
            }
            Floyd();
    }
    return 0;
}