【AtCoder】幅優先探索（BFS）

シンプルBFS

例題：ABC007C - 幅優先探索

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

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

int main() {
  int H, W; cin >> H >> W;
  int sy, sx, gy, gx;
  cin >> sy >> sx >> gy >> gx;
  sy--; sx--; gy--; gx--;
  vs C(H); rep(i, H) cin >> C[i];
  
  vector<vi> dist(H, vi(W, -1));
  queue<P> q;
  q.emplace(sy, sx); dist[sy][sx] = 0;
  while (!q.empty()) {
    auto [y, x] = q.front();
    q.pop();
    rep(k, 4) {
      int ny = y + dy[k], nx = x + dx[k];
      if (C[ny][nx] == '#') continue;
      if (dist[ny][nx] != -1) continue;
      
      q.emplace(ny, nx); dist[ny][nx] = dist[y][x] + 1;
    }
  }
  
  cout << dist[gy][gx] << endl;
}

ダイクストラ法

例題１：ABC340D - Super Takahashi Bros.

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

int main() {
  int N; cin >> N;
  vi A(N-1), B(N-1), X(N-1);
  rep(i, N-1) {
    cin >> A[i] >> B[i] >> X[i];
    X[i]--;
  }
  
  vector<ll> cost(N, -1);
  priority_queue<P, vector<P>, greater<P>> pq;
  pq.emplace(0, 0);
  while (!pq.empty()) {
    auto [c, pos] = pq.top();
    pq.pop();
    if (cost[pos] != -1) continue;
    cost[pos] = c;
    if (pos == N - 1) break;
    int npos1 = pos + 1, npos2 = X[pos];
    if (cost[npos1] == -1) pq.emplace(c + A[pos], npos1);
    if (cost[npos2] == -1) pq.emplace(c + B[pos], npos2);
  }
  
  cout << cost[N-1] << endl;
}

類題：ABC362D - Shortest Path 3

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

下記はdequeで実装しているが、構造体同士の比較演算を定義すればpriority_queueでも実装できる。

#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 State { int x, y, dir; };

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)));
  deque<State> dq;
  rep(k, 4) { cnt[sx][sy][k] = 0; dq.push_back({ sx, sy, k }); }
  while (!dq.empty()) {
    State t = dq.front();
    dq.pop_front();
    rep(k, 4) {
      int nx = t.x + dx[k], ny = t.y + dy[k], cost = cnt[t.x][t.y][t.dir] + (t.dir == k ? 0 : 1);
      if (nx >= 0 && nx < H && ny >= 0 && ny < W && S[nx][ny] == '.' && cost < cnt[nx][ny][k]) {
        cnt[nx][ny][k] = cost;
        if (t.dir == k) dq.push_front({ nx, ny, k });
        else dq.push_back({ nx, ny, k });
      }
    }
  }
  
  int ans = INF;
  rep(k, 4) ans = min(ans, cnt[gx][gy][k]);
  cout << ans << endl;
}