【質問】典型90問043 - Maze Challenge with Lack of Sleep（★4）

質問があります。
以下のコードを提出した所TLEが4つ出たのですが、原因が分かりません。
どなたか分かる方がいれば、ご教授いただけると幸いです。

典型90問043 - Maze Challenge with Lack of Sleep（★4）

#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vs = vector<string>;
#define rep(i, n) for (int i = 0; i < (n); ++i)

const int INF = 1001001001;
const vi dx = { -1, 0, 1, 0 };
const vi dy = { 0, 1, 0, -1 };

struct Edge {
  int x, y, dir, cost;
  Edge(int x, int y, int dir, int cost): x(x), y(y), dir(dir), cost(cost) {}
  bool operator==(const Edge &e) const { return cost == e.cost; }
  bool operator<(const Edge &e) const { return cost < e.cost; }
  bool operator>(const Edge &e) const { return cost > e.cost; }
  
};

int main() {
  int H, W; cin >> H >> W;
  int sx, sy, gx, gy;
  cin >> sx >> sy >> gx >> gy;
  sx--; sy--; gx--; gy--;
  vs S(H); rep(i, H) cin >> S[i];
  
  vector<vector<vi>> cnt(H, vector<vi>(W, vi(4, INF)));
  priority_queue<Edge, vector<Edge>, greater<Edge>> pq;
  rep(k, 4) pq.push({ sx, sy, k, 0 });
  while (!pq.empty()) {
    Edge e = pq.top();
    pq.pop();
    if (e.cost >= cnt[e.x][e.y][e.dir]) continue;
    
    cnt[e.x][e.y][e.dir] = e.cost;
    rep(k, 4) {
      int nx = e.x + dx[k], ny = e.y + dy[k];
      if (nx < 0 || nx >= H || ny < 0 || ny >= W) continue;
      if (S[nx][ny] == '#') continue;
      
      int ncost = (e.dir == k) ? e.cost : e.cost + 1;
      if (ncost < cnt[nx][ny][k]) pq.push({ nx, ny, k, ncost });
    }
  }
  
  int ans = INF;
  rep(k, 4) ans = min(ans, cnt[gx][gy][k]);
  cout << ans << endl;
}