#1150911 (C++17) No.3463 Beltway

• 問題: No.3463 Beltway
• ユーザー: tnakao0123
• 提出日時: 2026-03-01 17:48:02
• 言語: C++17 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 82 ms / 2,000 ms
• コード長: 2,815 bytes
• コンパイル時間: 861 ms
• コンパイル使用メモリ: 88,020 KB
• 実行使用メモリ: 75,568 KB
• 最終ジャッジ日時: 2026-03-01 17:48:18
• 合計ジャッジ時間: 1,875 ms
• ジャッジサーバーID （参考情報）: judge2 / judge1

ファイルパターン	結果
sample	AC * 1
other	AC * 17

ソースコード

/* -*- coding: utf-8 -*-
 *
 * 3463.cc:  No.3463 Beltway - yukicoder
 */

#include<cstdio>
#include<vector>
#include<stack>
#include<queue>
#include<algorithm>
#include<utility>

using namespace std;

/* constant */

const int MAX_N = 200000;
const int MAX_M = 200000;

/* typedef */

using qi = queue<int>;
using vi = vector<int>;
using vb = vector<bool>;
using vvi = vector<vi>;
using pii = pair<int,int>;
using vpii = vector<pii>;
using si = stack<int>;

/* global variables */

vpii nbrs[MAX_N];
pii es[MAX_M];
int ds[MAX_N], gids[MAX_N];
vi gnbrs[MAX_N];

/* subroutines */

void bcc_visit(const vpii nbrs[], int v, int ei, vi& brdg, vvi& tecomp,
	       si& roots, si& S, vb& inS, vi& num, int& time) {
  num[v] = ++time;
  S.push(v); inS[v] = true;
  roots.push(v);

  for (const auto [w, wei]: nbrs[v]) {
    if (num[w] == 0)
      bcc_visit(nbrs, w, wei, brdg, tecomp, roots, S, inS, num, time);
    else if (ei != wei && inS[w])
      while (num[roots.top()] > num[w]) roots.pop();
  }

  if (v == roots.top()) {
    brdg.push_back(ei);
    tecomp.push_back(vi());
    for (;;) {
      int w = S.top(); S.pop(); inS[w] = false;
      tecomp.back().push_back(w);
      if (v == w) break;
    }
    roots.pop();
  }
}

void calc_bcc(const int n, const vpii nbrs[], vi& brdg, vvi& tecomp) {
  vi num(n);
  vb inS(n);
  si roots, S;
  int time = 0;

  for (int u = 0; u < n; u++)
    if (num[u] == 0) {
      bcc_visit(nbrs, u, -1, brdg, tecomp, roots, S, inS, num, time);
      brdg.pop_back();
    }
}

int bfs(int n, int st, int gl) {
  fill(ds, ds + n, -1);
  ds[st] = 0;
  qi q;
  q.push(st);

  while (! q.empty()) {
    int u = q.front(); q.pop();
    if (u == gl) return ds[u];

    for (auto [v, ei]: nbrs[u])
      if (ds[v] < 0) ds[v] = ds[u] + 1, q.push(v);
  }

  return -1;
}

/* main */

int main() {
  int n, m, st, gl;
  scanf("%d%d%d%d", &n, &m, &st, &gl);
  st--, gl--;
  for (int i = 0; i < m; i++) {
    int u, v;
    scanf("%d%d", &u, &v);
    u--, v--;
    nbrs[u].push_back({v, i});
    nbrs[v].push_back({u, i});
    es[i] = {u, v};
  }

  int gd = bfs(n, st, gl);
  if (gd < 0) { puts("-1"); return 0; }
  
  vi brdg;
  vvi tcmp;
  calc_bcc(n, nbrs, brdg, tcmp);
  //for (auto ei: brdg) printf(" %d", ei); putchar('\n');

  int gn = tcmp.size();
  for (int i = 0; i < gn; i++)
    for (auto u: tcmp[i]) gids[u] = i;

  for (auto ei: brdg) {
    auto [u, v] = es[ei];
    int gu = gids[u], gv = gids[v];
    gnbrs[gu].push_back(gv);
    gnbrs[gv].push_back(gu);
  }

  int gst = gids[st], ggl = gids[gl];
  fill(ds, ds + gn, -1);
  ds[gst] = 0;
  qi q;
  q.push(gst);

  while (! q.empty()) {
    int u = q.front(); q.pop();
    if (u == ggl) break;

    for (auto v: gnbrs[u])
      if (ds[v] < 0) ds[v] = ds[u] + 1, q.push(v);
  }

  printf("%d\n", gd - ds[ggl]);
  
  return 0;
}