今天是2024年11月6日 第45周 星期三
代人,时大变了。
我们生活在大地上,但我们的梦想超越天空。
Floyd算法
RainbowDash(讨论 | 贡献)2020年6月14日 (日) 06:42的版本 (创建页面,内容为“一个求图 (数据结构)中各个点之间最短距离的算法 <pre lang="cpp"> // 洛谷某道题的题解 #include <cstdio> #include <cmath> #include <qu…”)
一个求图中各个点之间最短距离的算法
// 洛谷某道题的题解
#include <cstdio>
#include <cmath>
#include <queue>
#include <utility>
#define FOR(i,a,b) for(int i=a,__endi=b;i<__endi;i++)
using namespace std;
typedef long double real;
bool link[155][155];
real dis[155][155],maxdis[155],d_before;
const real inf=HUGE_VALL;
int n;
typedef pair<int,int> point;
point farms[155];
char tmp[155];
real disEuclid(point a,point b)
{return hypot(a.first-b.first,a.second-b.second);}
int main(){
#ifndef ONLINE_JUDGE
freopen("C:\\Users\\dell\\Downloads\\P1522_7.in","r",stdin);
#endif // ONLINE_JUDGE
scanf("%d",&n);
FOR(i,0,n)
scanf("%d %d",&farms[i].first,&farms[i].second);
FOR(i,0,n){
scanf("%s",tmp);
FOR(j,0,n){
link[i][j]=(tmp[j]=='1');
dis[i][j]=link[i][j]?disEuclid(farms[i],farms[j]):inf;
if(i==j)dis[i][j]=0;
}
}
FOR(k,0,n)
FOR(i,0,n)
FOR(j,0,n)
if( dis[i][j]>dis[i][k]+dis[j][k]){
dis[i][j]=dis[i][k]+dis[j][k];
link[i][j]=true;
}
FOR(i,0,n){
FOR(j,0,n)
if( maxdis[i]<dis[i][j]&&link[i][j])
maxdis[i]=dis[i][j];
if( d_before<maxdis[i])
d_before=maxdis[i];
}
real res=inf;
FOR(i,0,n){
FOR(j,0,i){
if(!link[i][j]){
real disij=disEuclid(farms[i],farms[j]);
if( res>maxdis[i]+disij+maxdis[j])
res=maxdis[i]+disij+maxdis[j];
}
}
}
if( res<d_before)
res=d_before;
printf("%.6Lf",res);
return 0;
}