Floyd算法问题
#include<cstdio> #include<iostream> #include<cstring> #define MAXN 220 #define INF 123456789 #include<math.h> #include<iomanip> using namespace std; int n; double dis[MAXN][MAXN]; struct Point { double x,y; } point[MAXN]; double getDis(Point Pt1,Point Pt2) { return sqrt(((Pt1.x-Pt2.x)*(Pt1.x-Pt2.x)+(Pt1.y-Pt2.y)*(Pt1.y-Pt2.y))); } int main() { int cases=1; while(cin>>n&&n) { for(int i=1; i<=n; ++i) { cin>>point[i].x; cin>>point[i].y; } memset(dis,0,sizeof(dis)); for(int i=1; i<=n; ++i) for(int j=1+1; j<=n; ++j) { dis[i][j]=dis[j][i]=getDis(point[i],point[j]); } int i,j,k; for(k=1; k<=n; k++) for(i=1; i<=n-1; i++) for(j=i+1; j<=n; j++) if(dis[i][k]<dis[i][j] && dis[k][j]<dis[i][j]) if(dis[i][k]<dis[k][j]) dis[i][j]=dis[j][i]=dis[k][j]; else dis[i][j]=dis[j][i]=dis[i][k]; cout<<"Scenario #"<<cases++<<endl; cout<<fixed<<setprecision(3)<<"Frog Distance = "<<dis[1][2]<<endl; cout<<endl; } }
