UVa:10803 Thunder Mountain(floyd求多源最短路)

我了解錯題意了，其實是水題一道。

問你所有頂點之間最短距離中最大的那一個是多少。如果任意兩頂點之間沒有最短距離那麼輸出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;
}