二分答案，spfa check就行了。
gb题卡精度。
#include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> using namespace std; const int dx[4]={-1,0,1,0}; const int dy[4]={0,1,0,-1}; double L;int n,m; char mp[110][110]; int stx,sty,edx,edy; struct node { int x,y; }list[11000]; bool v[110][110]; double d[110][110]; bool check(double kk) { for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) d[i][j]=999999999.9; d[stx][sty]=0; memset(v,false,sizeof(v)); v[stx][sty]=true; int head=1,tail=2; list[1].x=stx;list[1].y=sty; while(head!=tail) { int x=list[head].x,y=list[head].y; for(int i=0;i<=3;i++) { int tx=x+dx[i],ty=y+dy[i]; if(tx>0&&tx<=n&&ty>0&&ty<=m&&mp[tx][ty]!='#') { double dis; if(x==tx)dis=1.0; else dis=kk; if(d[tx][ty]>d[x][y]+dis) { d[tx][ty]=d[x][y]+dis; if(v[tx][ty]==false) { v[tx][ty]=true; list[tail].x=tx;list[tail].y=ty; tail++;if(tail==10500)tail=1; } } } } v[x][y]=false; head++;if(head==10500)head=1; } if(d[edx][edy]<L||fabs(d[edx][edy]-L)<=1e-8)return true; return false; } int main() { int T; scanf("%d",&T); while(T--) { scanf("%lf%d%d",&L,&n,&m);gets(mp[0]+1); for(int i=1;i<=n;i++) { gets(mp[i]+1); for(int j=1;j<=m;j++) if(mp[i][j]=='S') stx=i, sty=j; else if(mp[i][j]=='E') edx=i, edy=j; } double l=0.0,r=10.0,ans=0; while(r-l>1e-7) { double mid=(l+r)/2; if(check(mid)==true) l=mid+0.0000001, ans=mid; else r=mid-0.0000001; } printf("%.5lf ",ans); } return 0; }