[SCOI2009]最长距离

最短路用的是

#include <bits/stdc++.h>
using namespace std;
#define id(i,j) (i-1)*m+j 
const int maxn=2e5+10;
const int inf=1e9;
int a[109][109],n,ju[109][109],vis[maxn],dis[maxn],m;
int x[5]={0,0,1,-1},y[5]={1,-1,0,0},T;
double ans;
struct edge{
    int to,nxt,w;
}d[maxn]; int head[maxn],cnt=1;
void add(int u,int v,int w)
{
    d[++cnt] = (edge){v,head[u],w},head[u] = cnt;
}
typedef pair<int,int>p;
priority_queue<p,vector<p>,greater<p> >q;
void dij(int s,int x,int y)
{
    for(int i=1;i<=n*m;i++)    dis[i]=inf,vis[i]=0;
    dis[s]=0;
    q.push( p(0,s) );
    while( !q.empty() )
    {
        int u=q.top().second; q.pop();
        for(int i=head[u];i;i=d[i].nxt )
        {
            int v=d[i].to;
            if( dis[u]+d[i].w<dis[v] )
            {
                dis[v] = dis[u]+d[i].w;
                if( !vis[v] )
                    vis[v]=1,q.push( p(dis[v],v) );
            }
        }
    }
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    {
        if( dis[id(i,j)]+a[x][y]<=T )
        {
            ans = max( ans,sqrt((x-i)*(x-i)*1.0+(y-j)*(y-j)*1.0) );
        }
    }
}
int main()
{
    cin >> n >> m >>  T;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    {
        char ff; cin >> ff;
        a[i][j] = ff-'0';
    }
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    {
        for(int q=0;q<4;q++)
        {
            int nx = i +x[q],ny = j+y[q];
            if( nx<1||ny<1||nx>n||ny>n )    continue;
            add( id(i,j),id(nx,ny),a[nx][ny]==1 );
        }
    }
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)    dij( id(i,j),i,j );
    printf("%.6lf",ans);
}