最短経路問題として解いても構いませんが、今回は別の解法を紹介します。

0-1 BFS と呼ばれる手法を応用します。
移動にかかる時間が \(0,1,2\) 分のいずれかであることを利用します。
\(0,1,2\) の番号が付いた配列を用意します。
その上で、以下を繰り返します。

• 最初は \(0\) 番の配列に始点のみを入れる。
• \(i=0,1,2,\dots\) について、以下を繰り返す。
• \(i \% 3\) 番の配列が空になるまで以下を繰り返す。
  • 配列から要素を取り出し、そのマスから隣接したマスについての移動を考える。
  • その移動が最短経路を更新するなら、移動にかかる時間を \(t\) として \((i+t) \% 3\) 番の配列に移動後のマスを入れる。

これで priority_queue にかかる \(\log\) を取り除くことができ、全体で時間計算量 \(O(HW)\) で動作します。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;
using pi=pair<int,int>;

int dx4[4]={-1,1,0,0};
int dy4[4]={0,0,-1,1};

int wei(char x,char y){
  if(x=='V' && y=='V'){return 0;}
  if(y=='V'){return 2;}
  return 1;
}

int main(){
  int H,W;
  cin >> H >> W;
  pi S,G;
  vector<string> C(H);
  for(int i=0;i<H;i++){
    cin >> C[i];
    for(int j=0;j<W;j++){
      if(C[i][j]=='S'){S={i,j};}
      if(C[i][j]=='G'){G={i,j};}
    }
  }
  vector<vector<int>> fl(H,vector<int>(W,0));
  vector<vector<int>> dist(H,vector<int>(W,1e9));
  vector<vector<pi>> mem(3);
  int sz=1;
  dist[S.first][S.second]=0;
  mem[0].push_back(S);
  for(int d=0;sz>0;d++){
    while(!mem[d%3].empty()){
      auto od=mem[d%3].back();
      mem[d%3].pop_back();
      sz--;
      if(od==G){
        cout << d << "\n";
        return 0;
      }
      if(fl[od.first][od.second]){continue;}
      fl[od.first][od.second]=1;
      for(int k=0;k<4;k++){
        int nx=od.first+dx4[k];
        int ny=od.second+dy4[k];
        if(!(0<=nx && nx<H)){continue;}
        if(!(0<=ny && ny<W)){continue;}
        if(C[nx][ny]=='X'){continue;}
        int len=wei(C[od.first][od.second],C[nx][ny]);
        if(dist[nx][ny]>d+len){
          dist[nx][ny]=d+len;
          mem[dist[nx][ny]%3].push_back({nx,ny});
          sz++;
        }
      }
    }
  }
  cout << "NO\n";
  return 0;
}