【二分答案】【Heap-Dijkstra】bzoj2709 [Violet 1]迷宫花园

显然最短路长度随着v的变化是单调的，于是可以二分答案，据说spfa在网格图上表现较差。

#include<cstdio>

#include<cstring>

#include<queue>

using namespace std;

typedef double db;

typedef long long ll;

#define N 101

#define INF 2147483647.0

#define EPS 0.0000001

struct Point{db d;int u;};

bool operator < (Point a,Point b){return a.d>b.d;}

priority_queue<Point>q;

int T,n,m;

db L;

char a[N][N];

int en,v[N*N*4],first[N*N],next[N*N*4];

db w[N*N*4];

void AddEdge(int U,int V,db W)

{

	v[++en]=V;

	w[en]=W;

	next[en]=first[U];

	first[U]=en;

}

db d[N*N];

bool vis[N*N];

void dijkstra(int S)

{

	for(int i=1;i<=n*m;++i) d[i]=INF;

	d[S]=0; q.push((Point){0.0,S});

	while(!q.empty())

	  {

	  	Point x=q.top(); q.pop();

	  	if(!vis[x.u])

	  	  {

	  	  	vis[x.u]=1;

	  	  	for(int i=first[x.u];i;i=next[i])

	  	  	  if(d[v[i]]>d[x.u]+w[i])

	  	  	    {

	  	  	      d[v[i]]=d[x.u]+w[i];

	  	  	      q.push((Point){d[v[i]],v[i]});

	  	  	    }

	  	  }

	  }

}

int id[N][N],Sta,End;

const int dx[]={0,0,-1,1},dy[]={-1,1,0,0};

bool check(db x)

{

	en=0;

	memset(first,0,sizeof(int)*(n*m+1));

	memset(vis,0,sizeof(bool)*(n*m+1));

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

	  for(int j=1;j<=m;++j) if(a[i][j]!='#')

	    {

	      for(int k=0;k<2;++k)

	        if(i+dx[k]>0&&i+dx[k]<=n&&j+dy[k]>0&&j+dy[k]<=m&&a[i+dx[k]][j+dy[k]]!='#')

	          AddEdge(id[i][j],id[i+dx[k]][j+dy[k]],1.0);

	      for(int k=2;k<4;++k)

	        if(i+dx[k]>0&&i+dx[k]<=n&&j+dy[k]>0&&j+dy[k]<=m&&a[i+dx[k]][j+dy[k]]!='#')

	          AddEdge(id[i][j],id[i+dx[k]][j+dy[k]],x);

	    }

	dijkstra(Sta);

	return L-d[End]<EPS;

}

int main()

{

	scanf("%d",&T);

	for(;T;--T)

	  {

	  	scanf("%lf%d%d\n",&L,&n,&m);

	  	en=0;

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

	  	  gets(a[i]+1);

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

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

	  	    {

	  	      id[i][j]=++en;

	  	      if(a[i][j]=='S') Sta=id[i][j];

	  	      else if(a[i][j]=='E') End=id[i][j];

	  	    }

	  	db l=0.0,r=10.0;

	  	while(r-l>EPS)

	  	  {

	  	  	db mid=(l+r)/2.0;

	  	  	if(check(mid)) r=mid;

	  	  	else l=mid+EPS;

	  	  }

	  	printf("%.5lf\n",l);

	  }

	return 0;

}