http://www.lydsy.com/JudgeOnline/problem.php?id=2709
可以看出s到e的最短路关于v单调不减
二分v做最短路好了
注意精度,要卡到1e-7
program bzoj2709; const eps=1e-7; zl:array [1..4,1..2] of longint=((1,0),(-1,0),(0,1),(0,-1)); var p,l,v,s,e:double; t,x,y,tot,sx,sy,ex,ey,r,c,i,j,k:longint; dis:array [0..101,0..101] of double; map:array [0..101,0..101] of char; dl:array [0..1000001] of record x,y:longint; end; begin readln(t); while t>0 do begin dec(t); readln(l,r,c); for i:=0 to r+1 do for j:=0 to c+1 do map[i,j]:='#'; for i:=1 to r do begin for j:=1 to c do begin read(map[i,j]); if map[i,j]='S' then begin sx:=i; sy:=j; end; if map[i,j]='E' then begin ex:=i; ey:=j; end; end; readln; end; s:=0; e:=10; while abs(s-e)>eps do begin v:=(s+e)/2; fillchar(dis,sizeof(dis),87); dl[0].x:=sx; dl[0].y:=sy; tot:=0; dis[sx,sy]:=0; i:=0; while i<=tot do begin for j:=1 to 4 do begin if j<=2 then p:=v else p:=1; x:=dl[i].x+zl[j,1]; y:=dl[i].y+zl[j,2]; if (map[x,y]<>'#')and(dis[x,y]>dis[dl[i].x,dl[i].y]+p) then begin dis[x,y]:=dis[dl[i].x,dl[i].y]+p; inc(tot); dl[tot].x:=x; dl[tot].y:=y; end; end; inc(i); end; if dis[ex,ey]<l then s:=v else e:=v; end; writeln(s:0:5); end; end.