#include<iostream>
#include<string>

using namespace std;

#define SIZE (101)
#define INF  (1<<29)
int n;
int map[SIZE][SIZE];

int findMax(int a,int b)
{
    return a>b?a:b;
}
int findMin(int a,int b)
{
    return a<b?a:b;
}
int ReadIn(void)
{
    string a; cin>>a;
    if(a=="x") return INF;
    else
    {
        int ans=0;
        for(int i=0,l=a.length();l-i>0;i++)
        {
            ans*=10;
            ans+=(a[i]-'0');
        }
        return ans;
    }
}
int floyd(void)
{
    for(int i=0;n-i>0;i++)
    {
        for(int j=0;n-j>0;j++)
        {
            for(int k=0;n-k>0;k++)
            {
                map[j][k]=findMin(map[j][k],map[j][i]+map[i][k]);
            }
        }
    }
    int ans=0;
    for(int i=1;n-i>0;i++)
    {
        ans=findMax(ans,map[0][i]);
    }
    return ans;
}         
int main()
{
    scanf("%d",&n);
    for(int i=0;n-i>0;i++)
    {
        map[i][i]=INF;
        for(int j=0;i-j>0;j++)
        {
            map[i][j]=map[j][i]=ReadIn();
        }
    }
    
    printf("%d\n",floyd());
    
    //system("pause");
    return 0;
}

• Re:Floyd为何也能16MS (1296) chenxuan123456789 2012-09-12 11:27:12