二分+最短路判定 BZOJ 2709: [Violet 1]迷宫花园

BZOJ 2709: [Violet 1]迷宫花园

Sample Input

5

10.28

#########

#       #

# # # # #

#S#     #

##### # #

##  #   #

# ### ###

##E     #

#########

4.67

#########

#  ##  ##

### #S# #

#  # E ##

# # #####

# ##  ###

# ##### #

#    #  #

#########

39.06

#########

#       #

# # # # #

# E# #  #

# # # # #

## ###  #

# # #S# #

#####   #

#########

24.00

#########

#      ##

# # ## ##

#   #  ##

###S## E#

### #  ##

# #   # #

##### # #

#########

25.28

#########

# S##E# #

# ### # #

# ##    #

# ##  ###

# #  ####

# # # ###

#       #

#########

Sample Output

0.41000

4.67000

3.34000

5.00000

1.69000

HINT

 /*

 分析：符合二分的原理：当v变大，dis一定变大，而且v的具体范围很小，才是0--10，符合二分原理。

 二分出一个V，就用spfa求一次最短路，看看最短的长度与L大小关系，以此来二分。

 */

 #include<cmath>

 #include<iostream>

 using namespace std;

 #include<cstdio>

 #include<queue>

 #include<cstring>

 #define R 110

 int T,r,c;

 bool inque[R*R];

 char ditu[R][R];

 double L,z,y;

 double dist[R*R];

 int head[],bh=,sta,endd,bhh[R][R];

 struct Edge{

     int v,last;

     double w;

 }edge[];

 int t=;

 void input()

 {

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

     for(int i=;i<=r;++i)

     {

         for(int j=;j<=c;++j)

         {

             scanf("%c",&ditu[i][j]);

             if(ditu[i][j]==)

             {

                 bh++;

                 bhh[i][j]=bh;

             }

             if(ditu[i][j]=='S')bhh[i][j]=sta=++bh;

             if(ditu[i][j]=='E')bhh[i][j]=endd=++bh;

          }

         scanf("\n");

      }

 }

 void add_edge(int i,int j)

 {

     if(i->&&ditu[i-][j]!='#') {++t;edge[t].v=bhh[i-][j];edge[t].w=-;edge[t].last=head[bhh[i][j]];head[bhh[i][j]]=t;}

     if(i<r&&ditu[i+][j]!='#')   {++t;edge[t].v=bhh[i+][j];edge[t].w=-;edge[t].last=head[bhh[i][j]];head[bhh[i][j]]=t;}

     if(j->&&ditu[i][j-]!='#') {++t;edge[t].v=bhh[i][j-];edge[t].w=;edge[t].last=head[bhh[i][j]];head[bhh[i][j]]=t;}

     if(j<c&&ditu[i][j+]!='#')   {++t;edge[t].v=bhh[i][j+];edge[t].w=;edge[t].last=head[bhh[i][j]];head[bhh[i][j]]=t;}

 }

 void build_tu()

 {

    for(int i=;i<=r;++i)

      for(int j=;j<=c;++j)

      if(ditu[i][j]!='#')

      {

          add_edge(i,j);

      }

 }

 double SPFA(double ww)

 {

     for(int i=;i<=bh;++i)

       dist[i]=(<<)-;

     dist[sta]=;

     memset(inque,false,sizeof(inque));

     queue<int>Q;

     Q.push(sta);

     inque[sta]=true;

     while(!Q.empty())

     {

         int nowt=Q.front();

         Q.pop();

         inque[nowt]=false;

         for(int l=head[nowt];l;l=edge[l].last)

         {

             if(edge[l].w<)

             {

                 if(dist[edge[l].v]>dist[nowt]+ww)

                 {

                     dist[edge[l].v]=dist[nowt]+ww;

                     if(!inque[edge[l].v])

                     {

                         inque[edge[l].v]=true;

                         Q.push(edge[l].v);

                     }

                 }

             }

             else {

                 if(dist[edge[l].v]>dist[nowt]+edge[l].w)

                 {

                     dist[edge[l].v]=dist[nowt]+edge[l].w;

                     if(!inque[edge[l].v])

                     {

                         inque[edge[l].v]=true;

                         Q.push(edge[l].v);

                     }

                 }

             }

         }

     }

     return dist[endd];

 }

 int main()

 {

     cin>>T;

     while(T--)

     {

       input();

       build_tu();

       z=;y=;

       while(z<=y)

       {

           double mid=(z+y)/;

           double ans=SPFA(mid);

           if(ans>=L) y=mid-0.000001;/*注意这里要加0.000001，之前的二分加1，是为了去一个区间（int），但是现在是double，所以要+0

 .000001。*/

           else z=mid+0.000001;

       }

       printf("%0.5lf\n",y);

     }

     return ;

 }