LRY2
LRY
2020-08-04 10:51:49
3
返回题目
#include<bits/stdc++.h>
using namespace std;
struct plac{
int x,y;
};
int n;
plac pl[160];
double jl[160][160];
double mdis[160];
double ans;
string ch;
double diss(int a,int b)
{
return sqrt((pl[a].x-pl[b].x)*(pl[a].x-pl[b].x)+(pl[a].y-pl[b].y)*(pl[a].y-pl[b].y));
}
void lj(int i)
{
int k;
for(k=1;k<=n;k++)
{
if(ch[k-1]=='1')
{
jl[i][k]=sqrt((pl[i].x-pl[k].x)*(pl[i].x-pl[k].x)+(pl[i].y-pl[k].y)*(pl[i].y-pl[k].y));
jl[k][i]=jl[i][k];
}
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
pl[i].x=x;
pl[i].y=y;
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
jl[i][j]=INT_MAX/3;
}
}
for(int i=1;i<=n;i++)
{
cin>>ch;
lj(i);
}
for(int k=1;k<=n;k++)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(jl[i][k]!=INT_MAX/3&&jl[j][k]!=INT_MAX/3)
{
if(jl[i][j]>jl[i][k]+jl[k][j])
{
jl[i][j]=jl[i][k]+jl[k][j];
}
}
}
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(jl[i][j]!=INT_MAX/3)
{
ans=max(ans,jl[i][j]);
mdis[i]=max(jl[i][j],mdis[i]);
}
}
}
double d=DBL_MAX;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(jl[i][j]!=INT_MAX/3&&i!=j)
{
if(d>mdis[i]+mdis[j]+diss(i,j))
d=mdis[i]+mdis[j]+diss(i,j);
}
}
}
printf("%.6lf",ans);
return 0;
}
{{ vote && vote.total.up }}