Language: C++

#include <iostream>
#include <complex>
#include <sstream>
#include <string>
#include <algorithm>
#include <deque>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <vector>
#include <set>
#include <limits>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <ctime>
using namespace std;
#define REP(i, j) for(int i = 0; i < (int)(j); ++i)
#define FOR(i, j, k) for(int i = (int)(j); i < (int)(k); ++i)
#define SORT(v) sort((v).begin(), (v).end())
#define REVERSE(v) reverse((v).begin(), (v).end())
#define y first
#define x second
typedef pair<int, int> P;
const int INF = 1e9;

int my3[8] = {0, 0, 1, -1, 1, 1, -1, -1};
int mx3[8] = {1, -1, 0, 0, -1, 1, 1, -1};
int my2[16] = {-2, -2, -2, -2, -2, -1, 0, 1, 2, 2, 2, 2, 2, 1, 0, -1};
int mx2[16] = {-2, -1, 0, 1, 2, 2, 2, 2, 2, 1, 0, -1, -2, -2, -2, -2};
int my[4] = {0, 0, 1, -1};
int mx[4] = {1, -1, 0, 0};

int H, W;

void dfs(int y, int x, vector< vector<int> > &v, vector< vector<int> > &step, int cnt){
  step[y][x] = cnt;
  REP(i, 4){
    int ny = y + my[i], nx = x + mx[i];
    if(ny >= 0 && nx >= 0 && ny < H && nx < W && v[ny][nx] != INF && step[ny][nx] > cnt + v[y][x]) dfs(ny, nx, v, step, cnt + v[y][x]);
  }
}

int dist(P &a, P &b, vector< vector<int> > &v){
  vector< vector<int> > step(H, vector<int>(W, INF));
  dfs(a.y, a.x, v, step, 0);
  return step[b.y][b.x];
}

int solve(vector< vector<int> > &d, int m, P &g, vector<P> &ms, vector< vector<int> > &v){
  vector< vector<int> > dp((1 << m), vector<int>(m + 1, INF));
  dp[0][0] = 0;
  REP(i, (1 << m)){
    REP(j, m + 1){
      if(dp[i][j] == INF) continue;
      bitset<4> bs(i);
      REP(next, m){
        if(((1 << next) & i) != 0) continue;
        int c = d[j][next + 1], n = ((1 << next) | i);
        dp[n][next + 1] = min(dp[n][next + 1], dp[i][j] + c);
      }
    }
  }
  int res = INF;
  FOR(i, 1, m + 1) res = min(res, dp[(1 << m) - 1][i] + dist(ms[i - 1], g, v));
  return res;
}

int main() {
  cin >>W >>H;
  vector<string> cv(H);
  REP(i, H) cin >>cv[i];
  vector< vector<int> > v(H, vector<int>(W, 1));
  vector<P> ms;
  P s, g;
  REP(y, H){
    REP(x, W){
      if(cv[y][x] == 'M') ms.push_back(P(y, x));
      if(cv[y][x] == 'S') s = P(y, x);
      if(cv[y][x] == 'G') g = P(y, x);
      if(cv[y][x] != '#') continue;
      v[y][x] = INF;
      REP(i, 8){
        int ny = y + my3[i], nx = x + mx3[i];
        if(ny >= 0 && nx >= 0 && ny < H && nx < W) v[ny][nx] = max(3, v[ny][nx]);
      }
      REP(i, 16){
        int ny = y + my2[i], nx = x + mx2[i];
        if(ny >= 0 && nx >= 0 && ny < H && nx < W) v[ny][nx] = max(2, v[ny][nx]);
      }
    }
  }
  int msl = ms.size();
  vector< vector<int> > d(msl + 1, vector<int>(msl + 1, 0));
  REP(i, msl) d[0][i + 1] = d[i + 1][0] = dist(s, ms[i], v);
  REP(i, msl) FOR(j, i + 1, msl) d[i + 1][j + 1] = d[j + 1][i + 1] = dist(ms[i], ms[j], v);
  cout <<solve(d, msl, g, ms, v) <<endl;
  return 0;
}

Compiler output:
a.cc: In function 'int solve(std::vector<std::vector<int> >&, int, P&, std::vector<std::pair<int, int> >&, std::vector<std::vector<int> >&)':
a.cc:59:7: error: 'bitset' was not declared in this scope
   59 |       bitset<4> bs(i);
      |       ^~~~~~
a.cc:20:1: note: 'std::bitset' is defined in header '<bitset>'; this is probably fixable by adding '#include <bitset>'
   19 | #include <ctime>
  +++ |+#include <bitset>
   20 | using namespace std;
a.cc:59:17: error: 'bs' was not declared in this scope; did you mean 'ms'?
   59 |       bitset<4> bs(i);
      |                 ^~
      |                 ms