Language: C++

#include <boost/multiprecision/cpp_int.hpp>
#include <boost/rational.hpp>
#include <bits/stdc++.h>
using namespace std;

#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))

typedef long long LL;

struct poLL{
  LL x;
  LL y;
  LL count;
};

int main(){
  LL houkou[5]={0,1,0,-1,0};
  LL w,h;
  cin >> w >> h;
  vector<vector<LL>> field(h,vector<LL>(w));
  list<struct poLL> spring;
  char c;
  LL sx,sy,gx,gy;
  LL numofFloor=0;
  for(LL i=0;i<h;i++){
    for(LL j=0;j<w;j++){
      cin >> c;
      if(c=='.'){
        field[i][j]=1;
        numofFloor++;
      }else if(c=='#'){
        field[i][j]=0;
      }else if(c=='*'){
        field[i][j]=2;
        spring.push_back({j,i,0});
      }else if(c=='s'){
        field[i][j]=1;
        sx=j;
        sy=i;
        numofFloor++;
      }else{
        field[i][j]=3;
        gx=j;
        gy=i;
      }
    }
  }
  vector<vector<LL>> toGoal(h,vector<LL>(w,0));
  vector<vector<LL>> toSpring(h,vector<LL>(w,0));
  queue<struct poLL> bfs;
  struct poLL now;
  LL nx,ny;
  bfs.push({gx,gy,0});
  while(!bfs.empty()){
    now=bfs.front();
    bfs.pop();
    for(LL i=0;i<4;i++){
      nx=now.x+houkou[i];
      ny=now.y+houkou[i+1];
      if(0<=nx&&nx<=w&&0<=ny&&ny<=h){
        if(toGoal[ny][nx]==0&&field[ny][nx]==1){
          toGoal[ny][nx]=now.count+1;
          bfs.push({nx,ny,now.count+1});
        }
      }
    }
  }
  for(auto itr=spring.begin();itr!=spring.end();itr++){
    bfs.push({(*itr).x,(*itr).y,0});
  }
  while(!bfs.empty()){
    now=bfs.front();
    bfs.pop();
    for(LL i=0;i<4;i++){
      nx=now.x+houkou[i];
      ny=now.y+houkou[i+1];
      if(0<=nx&&nx<=w&&0<=ny&&ny<=h){
        if(toSpring[ny][nx]==0&&field[ny][nx]==1){
          toSpring[ny][nx]=now.count+1;
          bfs.push({nx,ny,now.count+1});
        }
      }
    }
  }
  // for(LL i=0;i<h;i++){
  //   for(LL j=0;j<w;j++){
  //     cout << toGoal[i][j] << " ";
  //   }
  //   cout << endl;
  // }
  // cout << endl;
  // for(LL i=0;i<h;i++){
  //   for(LL j=0;j<w;j++){
  //     cout << toSpring[i][j] << " ";
  //   }
  //   cout << endl;
  // }
  // cout << numofFloor << endl;
  cout << fixed <<  setprecision(12);
  boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>> left=0;
  boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>> right=10000000000000000000;
   cout << left << endl;
   cout << right << endl;
  boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>> mid;
  boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>> count;
  while(right-left>0.0000000001){
    mid=(left+right)/2;
    count=0;
    for(LL i=1;i<h-1;i++){
      for(LL j=1;j<w-1;j++){
        if(field[i][j]==1){
          if(toGoal[i][j]!=0){
            if(toSpring[i][j]!=0){
              count+=min((boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>>)toGoal[i][j],(boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>>)toSpring[i][j]+(boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>>)mid/(boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>>)numofFloor);
            }else{
              count+=(boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>>)toGoal[i][j];
            }
          }else{
            if(toSpring[i][j]!=0) count+=(boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>>)toSpring[i][j]+(boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>>)mid/(boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>>)numofFloor;
          }
        }
      }
    }
    if(count<mid){
      right=mid;
    }else{
      left=mid;
    }
  }
   cout << left << endl;
   cout << right << endl;
   cout << count << endl;
  // for(LL i=0;i<h;i++){
  //   for(LL j=0;j<w;j++){
  //     if(field[i][j]==1){
  //       if(toGoal[i][j]!=0){
  //         if(toSpring[i][j]!=0){
  //           cout << min((boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>>)toGoal[i][j],(boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>>)toSpring[i][j]+(boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>>)left/(boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>>)numofFloor) << " ";
  //         }else{
  //           cout << (boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>>)toGoal[i][j] << " ";
  //         }
  //       }else{
  //         if(toSpring[sy][sx]!=0) cout << (boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>>)toSpring[i][j]+(boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>>)left/(boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>>)numofFloor << " ";
  //       }
  //     }else{
  //       cout << 0 << " ";
  //     }
  //   }
  //   cout << endl;
  // }
  if(toGoal[sy][sx]!=0){
    if(toSpring[sy][sx]!=0){
      cout << min((boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>>)toGoal[sy][sx],(boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>>)toSpring[sy][sx]+(boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>>)left/(boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>>)numofFloor) << endl;
    }else{
      cout << (boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>>)toGoal[sy][sx] << endl;
    }
  }else{
    if(toSpring[sy][sx]!=0) cout << (boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>>)toSpring[sy][sx]+(boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>>)left/(boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>>)numofFloor << endl;
  }

  return 0;
}



Compiler output:
a.cc:1:10: fatal error: boost/multiprecision/cpp_int.hpp: No such file or directory
    1 | #include <boost/multiprecision/cpp_int.hpp>
      |          ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
compilation terminated.