AcWing 1125. 牛的旅行
原题链接
简单
作者:
Dear_You
,
2019-11-24 14:45:32
,
所有人可见
,
阅读 919
C++ 代码
#include<bits/stdc++.h>
#define N 160
using namespace std;
const int maxn=0x3f3f3f3f;
double f[N][N],maxdis[N],ma[N][N],temp,ans=0x3f3f3f3f;
int a[N][3],n;
char c;
double god(int i,int j) {
return sqrt((a[i][1]-a[j][1])*(a[i][1]-a[j][1])+(a[i][2]-a[j][2])*(a[i][2]-a[j][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>>c;
if(c=='1') ma[i][j]=god(i,j);
else ma[i][j]=maxn;
}
for (int k=1; k<=n; k++)
for (int i=1; i<=n; i++)
for (int j=1; j<=n; j++)
if(i!=j&&ma[i][j]>ma[i][k]+ma[k][j]) ma[i][j]=ma[i][k]+ma[k][j];
for (int i=1; i<=n; i++)
for (int j=1; j<=n; j++)
if(ma[i][j]!=maxn&&ma[i][j]>maxdis[i]) maxdis[i]=ma[i][j];
for (int i=1; i<=n; i++)
for (int j=1; j<=n; j++) {
if(i!=j&&ma[i][j]==maxn) {
temp=maxdis[i]+maxdis[j]+god(i,j);
if(temp<ans) ans=temp;
}
}
for (int i=1; i<=n; i++) if(ans<maxdis[i]) ans=maxdis[i];
cout<<fixed<<setprecision(6)<<ans<<endl;
return 0;
}
emmmm......
eeeee