Dijkstra+优先队列优化，代码如下

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
typedef unsigned long long int UL;
typedef long long int LL;
typedef unsigned short US;
typedef double DB;
struct Node
{
    LL x;
    LL y;
};
LL n;
DB dis[152]={0},g[152][152]={0};
Node loc[152]={0};
const DB DB_MAX=1e18;
int main()
{
    //ios::sync_with_stdio(false);
    char ch;
    DB maxn=0,minn=DB_MAX;
    cin>>n;
    for (LL n1=1;n1<=n;n1++)
    {
        cin>>loc[n1].x>>loc[n1].y;
    }
    for (LL n1=1;n1<=n;n1++)
    {
        for (LL n2=1;n2<=n;n2++)
        {
            if (n1==n2)
              g[n1][n2]=0;
            else
              g[n1][n2]=DB_MAX;
        }
    }
    for (LL n1=1;n1<=n;n1++)
    {
        for (LL n2=1;n2<=n;n2++)
        {
            cin>>ch;
            if (ch=='1')
              g[n1][n2]=sqrt((loc[n1].x-loc[n2].x)*(loc[n1].x-loc[n2].x)+(loc[n1].y-loc[n2].y)*(loc[n1].y-loc[n2].y));
        }
    }
    for (LL i=1;i<=n;i++)
    {
        for (LL j=1;j<=n;j++)
        {
            for (LL k=1;k<=n;k++)
            {
                if (g[j][i]+g[i][k]<g[j][k])
                  g[j][k]=g[j][i]+g[i][k];
            }
        }
    }
    for (LL n1=1;n1<=n;n1++)
    {
        dis[n1]=0;
        for (LL n2=1;n2<=n;n2++)
        {
            if (g[n1][n2]<DB_MAX)
              dis[n1]=max(dis[n1],g[n1][n2]);
        }
        maxn=max(maxn,dis[n1]);
    }
    for (LL n1=1;n1<=n;n1++)
    {
        for (LL n2=1;n2<=n;n2++)
        {
            if (g[n1][n2]==DB_MAX)
            {
                if (dis[n1]+sqrt((loc[n1].x-loc[n2].x)*(loc[n1].x-loc[n2].x)+(loc[n1].y-loc[n2].y)*(loc[n1].y-loc[n2].y))+dis[n2]<minn)
                  minn=dis[n1]+sqrt((loc[n1].x-loc[n2].x)*(loc[n1].x-loc[n2].x)+(loc[n1].y-loc[n2].y)*(loc[n1].y-loc[n2].y))+dis[n2];
            }
        }
    }
    printf("%.6lf",max(maxn,minn));
    cout<<endl;
    return 0;
}