Language: C++

#include<bits/stdc++.h>
/*
*/

using namespace std;

typedef pair<long long int, pair<long long int, long long int>>one;

#define mod 1000000007LL
int main() {
	long long int W, H;
	cin >> W >> H;
	vector<string>D( H );
	long long int counttile = 0;
	pair<long long int, long long int>start, goal;
	vector<pair<long long int, long long int>>warp;
	vector<vector<pair<long long int, long long int>>>len( H, vector<pair<long long int, long long int>>( W, make_pair( LLONG_MAX / 500 / 500 / 500, LLONG_MAX / 500 / 500 / 500 ) ) );
	vector<pair<long long int, long long int>>tile;
	for( size_t i = 0; i < H; i++ ) {
		cin >> D[i];
		for( size_t j = 0; j < D[i].length(); j++ ) {
			if( D[i][j] == 's' ) {
				D[i][j] = '.';
				tile.push_back( make_pair( i, j ) );
				start.first = i;
				start.second = j;
				counttile++;
			} else if( D[i][j] == 'g' ) {
				goal.first = i;
				goal.second = j;
			} else if( D[i][j] == '*' ) {
				warp.push_back( make_pair( i, j ) );
			} else if( D[i][j] == '.' ) {
				counttile++;
				tile.push_back( make_pair( i, j ) );
			}
		}
	}
	int dx[] = {0,1,0,-1};
	int dy[] = {1,0,-1,0};
	{
		priority_queue<one, vector<one>, greater<one>>que;
		que.push( make_pair( 0, goal ) );
		while( que.size() ) {
			auto now = que.top(); que.pop();
			for( size_t i = 0; i < 4; i++ ) {
				auto next = now;
				next.first++;
				next.second.first += dx[i];
				next.second.second += dy[i];
				if( 0 <= next.second.first&&next.second.first < H && 0 <= next.second.second &&next.second.second < W ) {
					if( D[next.second.first][next.second.second] == '.' ) {
						if( len[next.second.first][next.second.second].first > next.first ) {
							len[next.second.first][next.second.second].first = next.first;
							que.push( next );
						}
					}
				}
			}
		}
	}
	queue<one, vector<one>>que;
	for( auto x : warp ) {
		que.push( make_pair( 0, x ) );
	}
	while( que.size() ) {
		auto now = que.front(); que.pop();
		if( len[now.second.first][now.second.second].second < now.first ) {
			continue;
		}
		for( size_t i = 0; i < 4; i++ ) {
			auto next = now;
			next.first++;
			next.second.first += dx[i];
			next.second.second += dy[i];
			if( 0 <= next.second.first&&next.second.first < H && 0 <= next.second.second &&next.second.second < W ) {
				if( D[next.second.first][next.second.second] == '.' ) {
					if( len[next.second.first][next.second.second].second > next.first ) {
						len[next.second.first][next.second.second].second = next.first;
						que.push( next );
					}
				}
			}
		}
	}

	long double maxExpectedValue = LDBL_MAX / 6, minExpectedValue = 0;
	for( size_t indexindex = 0; indexindex < 16500; indexindex++ ) {
		long double midExpectedValue = ( maxExpectedValue + minExpectedValue ) / 2.L;
		//cout << fixed << setprecision( 20 ) << maxExpectedValue << " " << minExpectedValue << endl;
		long double countExpectedValue = 0;
		for( auto point : tile ) {
			long long int i = point.first, j = point.second;
			countExpectedValue += min( 1.L* len[i][j].first, len[i][j].second + midExpectedValue );
		}
		countExpectedValue /= counttile;
		if( midExpectedValue < countExpectedValue ) {
			minExpectedValue = midExpectedValue;
		} else {
			maxExpectedValue = midExpectedValue;
		}
	}
	//cout << fixed << setprecision( 20 ) << 1.L* len[start.first][start.second].first << " " << len[start.first][start.second].second + maxExpectedValue << endl;
	cout << fixed << setprecision( 20 ) << min( 1.L* len[start.first][start.second].first, len[start.first][start.second].second + maxExpectedValue ) << endl;
}

Compiler output:
In file included from /usr/include/c++/14/queue:66,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:157,
                 from a.cc:1:
/usr/include/c++/14/bits/stl_queue.h: In instantiation of 'void std::queue<_Tp, _Sequence>::pop() [with _Tp = std::pair<long long int, std::pair<long long int, long long int> >; _Sequence = std::vector<std::pair<long long int, std::pair<long long int, long long int> > >]':
a.cc:67:34:   required from here
   67 |                 auto now = que.front(); que.pop();
      |                                         ~~~~~~~^~
/usr/include/c++/14/bits/stl_queue.h:319:11: error: 'class std::vector<std::pair<long long int, std::pair<long long int, long long int> > >' has no member named 'pop_front'
  319 |         c.pop_front();
      |         ~~^~~~~~~~~