我理解错题意了,其实是水题一道。
问你所有顶点之间最短距离中最大的那一个是多少。如果任意两顶点之间没有最短距离那么输出Send Kurdy。
floyd算法轻松搞定。。
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
int main()
{
int T,kase=0;
scanf("%d",&T);
while(T--)
{
int n;
double gl[105][105];
memset(gl,0x7f,sizeof(gl));
double INF=gl[0][0];
int x[105],y[105];
scanf("%d",&n);
for(int i=0; i<n; ++i)
scanf("%d%d",&x[i],&y[i]);
for(int i=0; i<n; ++i)
for(int j=0; j<n; ++j)
{
double dis=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
if(dis<=10.0)
gl[i][j]=dis;
}
for(int k=0; k<n; ++k)
for(int i=0; i<n; ++i)
for(int j=0; j<n; ++j)
if(gl[i][k]<INF&&gl[k][j]<INF)
gl[i][j]=min(gl[i][j],gl[i][k]+gl[k][j]);
double mxn=0;
bool ok=true;
for(int i=0; i<n; ++i)
for(int j=0; j<n; ++j)
if(gl[i][j]<INF)
mxn=max(mxn,gl[i][j]);
else ok=false;
printf("Case #%d:\n",++kase);
if(!ok) puts("Send Kurdy");
else printf("%.4lf\n",mxn);
printf("\n");
}
return 0;
}