bzoj2709 [Violet 1]迷宫花园

题目链接：bzoj2709
题目大意：
就给一个迷宫，#不能走，空格能走，S是起点，E是终点。水平方向的速度恒为1(即走一格所花的时间都为1)，而竖直方向的速度v由你来定，使从起点到终点所花的最短时间为L（L是给定的）。

题解：
二分+spfa
下面的范围有说保证0≤v≤10，就直接二分v。
修改竖直方向的边的边权之后跑最短路判定就好了。
诶二分那里好迷。。
这样子就WA了

 double ans,l=0,r=10;
 while(r-l>=eps)
 {
	 double mid=(l+r)/2.0;
     spfa(mid);
     if(dis[ed]>L) r=mid-eps;
     else {ans=mid;l=mid+eps;}
}
printf("%.5lf\n",ans);

而这样子是AC的

double ans,l=0,r=10;
while(r-l>=eps)
{
	double mid=(l+r)/2.0;
    spfa(mid);
    if(dis[ed]>L) r=mid-eps;
    else l=mid+eps;
}
printf("%.5lf\n",l);

大概是我不怎么会二分吧。。QwQ
代码里那些奇怪的实际上并不需要的判断是对拍的时候用的。。
并不知道怎么出一定合法的数据。。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<queue>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
#define N 110
#define maxn 10010

const int fx[4]={0,0,1,-1};
const int fy[4]={1,-1,0,0};
const double eps=1e-7;
struct node
{
	int x,y,next;double c;
}a[maxn*4];int len,first[maxn];
int S,E,cnt,num[N][N],ln,ver[maxn*2];
void ins(int x,int y,double c)
{
	len++;a[len].x=x;a[len].y=y;a[len].c=c;
	a[len].next=first[x];first[x]=len;
}
queue<int> q;double d[maxn];bool vis[maxn];
bool spfa()
{
	for (int i=1;i<=cnt;i++) d[i]=-1;
	d[S]=0;vis[S]=true;q.push(S);
	while (!q.empty())
	{
		int x=q.front();q.pop();
		for (int k=first[x];k!=-1;k=a[k].next)
		{
			int y=a[k].y;
			if (d[y]==-1 || d[y]>d[x]+a[k].c)
			{
				d[y]=d[x]+a[k].c;
				if (!vis[y])
				{
					vis[y]=true;
					q.push(y);
				}
			}
		}vis[x]=false;
	}
	return d[E]!=-1;
}
bool check(double v)
{
	for (int i=1;i<=ln;i++) a[ver[i]].c=v;
	return spfa();
}
int main()
{
	//freopen("a.in","r",stdin);
	//freopen("a.out","w",stdout);
	int T,n,m,i,j,k;char s[110];
	double lim,ans,l,r;
	scanf("%d",&T);
	while (T--)
	{
		ln=cnt=len=0;
		memset(first,-1,sizeof(first));
		scanf("%lf%d%d\n",&lim,&n,&m);
		for (i=1;i<=n;i++)
		{
			gets(s+1);
			for (j=1;j<=m;j++)
			if (s[j]=='#') num[i][j]=-1;
			else 
			{
				 num[i][j]=++cnt;
				 if (s[j]=='S') S=cnt;
				 else if (s[j]=='E') E=cnt;
			}
		}
		for (i=1;i<=n;i++)
		 for (j=1;j<=m;j++)
		  if (num[i][j]!=-1)
		   for (k=0;k<4;k++)
			if (i+fx[k]>=1 && i+fx[k]<=n && j+fy[k]>=1 && j+fy[k]<=m)
			 if (num[i+fx[k]][j+fy[k]]!=-1)
			 {
				 ins(num[i][j],num[i+fx[k]][j+fy[k]],1.0);
				 if (k>1) ver[++ln]=len;
			 }
		l=0,r=10;
		while(r-l>eps)
		{
			double mid=(l+r)/2.0;
			if (!check(mid)) {l=0;break;}
			if(d[E]>=lim) r=mid;
			else l=mid;
		}
		printf("%.5lf\n",l);
	}
	return 0;
}