【BZOJ1295】[SCOI2009]最长距离（最短路）

时间：2023-03-09 19:48:10
【BZOJ1295】[SCOI2009]最长距离（最短路）

【BZOJ1295】[SCOI2009]最长距离（最短路）

题面

BZOJ

洛谷

题解

这题很妙啊。

我们枚举一个点，只需要考虑到他的最远点就行了，显然只需要考虑一个点即可。那么这两个点之前联通的最小代价显然就是连接这两个点的路径中\(1\)最少的那条，那么直接跑一遍最短路就好了。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<queue>

using namespace std;

#define MAX 35

int n,m,T;

char g[MAX][MAX];

int dis[MAX][MAX];

bool vis[MAX][MAX];

int d[4][2]={1,0,-1,0,0,-1,0,1};

struct Node{int x,y;};

double ans;

double Sqr(double x){return x*x;}

double Dis(Node a,Node b){return sqrt(Sqr(a.x-b.x)+Sqr(a.y-b.y));}

void SPFA(int x,int y)

{

	queue<Node> Q;memset(dis,63,sizeof(dis));

	dis[x][y]=0;vis[x][y]=true;Q.push((Node){x,y});

	while(!Q.empty())

	{

		int x=Q.front().x,y=Q.front().y;Q.pop();

		for(int i=0;i<4;++i)

		{

			int xx=x+d[i][0],yy=y+d[i][1];

			if(xx<1||yy<1||xx>n||yy>m)continue;

			int w=g[xx][yy]-48;

			if(dis[xx][yy]>dis[x][y]+w)

			{

				dis[xx][yy]=dis[x][y]+w;

				if(!vis[xx][yy])vis[xx][yy]=true,Q.push((Node){xx,yy});

			}

		}

		vis[x][y]=false;

	}

	for(int i=1;i<=n;++i)

		for(int j=1;j<=m;++j)

			if(dis[i][j]<=T)

				ans=max(ans,Dis((Node){x,y},(Node){i,j}));

}

int main()

{

	scanf("%d%d%d",&n,&m,&T);

	for(int i=1;i<=n;++i)scanf("%s",g[i]+1);

	for(int i=1;i<=n;++i)

		for(int j=1;j<=m;++j)

			if(g[i][j]=='0')

				SPFA(i,j);

	printf("%.6lf\n",ans);

	return 0;

}

相关文章