Floyd算法
Shinonome Akebono(讨论 | 贡献)2020年7月4日 (六) 20:25的版本
一个求图中各个点之间最短距离的算法
<source lang="cpp"> // 洛谷某道题的题解
- 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;
} </source>