1343：【例4-2】牛的旅行

1343：【例4-2】牛的旅行

弗洛伊德算法：

（1）弗洛伊德算法求出任意两点间的最短路，然后求出每个点到所有可到达点的最大距离，记为           m[i]

（2）r1=max( m [ i ] )

（3）枚举不联通的两个点 i , j，把它们联通，则新的直径是m[i]+m[j]+dist(i,j)

 （4）r2=min( m[i] + m[j] + dist( i , j ) )

（5）re=max ( r1 , r2 ) 

代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
using namespace std;
int n;
char ch;
int a[151][3];
double f[151][151],maxt=1e12,minx=1e20,temp,m[151];
double dist(int x,int y)
{
    return sqrt(pow(double(a[x][1]-a[y][1]),2)+pow(double(a[x][2]-a[y][2]),2));
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
      cin>>a[i][1]>>a[i][2];
    for(int i=1;i<=n;i++)
      for(int j=1;j<=n;j++)
      {
          cin>>ch;
          if(ch=='1')
          f[i][j]=dist(i,j);
          else
          f[i][j]=maxt;
      }
    
    for(int k=1;k<=n;k++)
      for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        if(i!=k&&i!=j&&j!=k)
        if(f[i][k]<maxt-1&&f[k][j]<maxt-1)  //确保连通 
        if(f[i][j]>f[i][k]+f[k][j])
            f[i][j]=f[i][k]+f[k][j];
    
    for(int i=1;i<=n;i++)
      for(int j=1;j<=n;j++)
      if(f[i][j]<maxt-1&&m[i]<f[i][j]) m[i]=f[i][j];  //(1) 
      
    for(int i=1;i<=n;i++)
      for(int j=1;j<=n;j++)
      if(i!=j&&f[i][j]>maxt-1)
      {
          temp=dist(i,j);
          if(minx>m[i]+m[j]+temp)
          minx=m[i]+m[j]+temp;
      }  //(4)
      
    for(int i=1;i<=n;i++)
      if(m[i]>minx)  //(2)(5)
      minx=m[i];
    
    printf("%.6lf",minx);
    return 0;     
    
    
    
}