#1150281 (C++23) No.3463 Beltway

• 問題: No.3463 Beltway
• ユーザー: テナガザル
• 提出日時: 2026-02-28 14:41:21
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 285 ms / 2,000 ms
• コード長: 2,788 bytes
• コンパイル時間: 2,687 ms
• コンパイル使用メモリ: 213,976 KB
• 実行使用メモリ: 48,112 KB
• 最終ジャッジ日時: 2026-02-28 15:51:35
• 合計ジャッジ時間: 6,054 ms
• ジャッジサーバーID （参考情報）: judge2 / judge1

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

コンパイルメッセージ

main.cpp: In constructor 'lowlink::lowlink(int, std::vector<std::pair<int, int> >&)':
main.cpp:26:27: warning: narrowing conversion of '(&((lowlink*)this)->lowlink::g.std::vector<std::vector<lowlink::edge> >::operator[](((std::vector<std::vector<lowlink::edge> >::size_type)b)))->std::vector<lowlink::edge>::size()' from 'std::vector<lowlink::edge>::size_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
   26 |       edge e1{b, g[b].size(), 0}, e2{a, g[a].size(), 0};
      |                  ~~~~~~~~~^~
main.cpp:26:50: warning: narrowing conversion of '(&((lowlink*)this)->lowlink::g.std::vector<std::vector<lowlink::edge> >::operator[](((std::vector<std::vector<lowlink::edge> >::size_type)a)))->std::vector<lowlink::edge>::size()' from 'std::vector<lowlink::edge>::size_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
   26 |       edge e1{b, g[b].size(), 0}, e2{a, g[a].size(), 0};
      |                                         ~~~~~~~~~^~

ソースコード

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <set>

using namespace std;

struct lowlink
{
  struct edge {int to, rev, stat;}; //stat: 0-back 1-child 2-par
  int n, num;
  std::vector<std::vector<edge>> g;
  std::vector<int> ord, low, art;
  std::vector<std::pair<int, int>> bri;
  // vsiz:|V|, e:E
  lowlink(int vsiz, std::vector<std::pair<int, int>> &e)
  {
    n = vsiz;
    g.resize(n);
    ord.resize(n);
    low.assign(n, n + 1);
    for (auto &v : e)
    {
      int a = v.first, b = v.second;
      edge e1{b, g[b].size(), 0}, e2{a, g[a].size(), 0};
      g[a].push_back(e1);
      g[b].push_back(e2);
    }
    num = 0;
    for (int i = 0; i < n; ++i)
    {
      if (ord[i] == 0)
      {
        dfs(i);
        ord[i] = -ord[i];
      }
    }
    for (int i = 0; i < n; ++i)
    {
      // articulation & bridge
      bool isroot = ord[i] < 0, flag = false;
      if (isroot)
      {
        ord[i] = -ord[i];
        int cnt = 0;
        for (auto &v : g[i]) cnt += v.stat == 1;
        flag = cnt > 1;
      }
      for (auto &v : g[i])
      {
        if (v.stat == 1)
        {
          if (!isroot && ord[i] <= low[v.to]) flag = true;
          if (ord[i] < low[v.to]) bri.push_back({min(i, v.to), max(i, v.to)});
        }
      }
      if (flag) art.push_back(i);
    }
  }
private:
  void dfs(int now)
  {
    ord[now] = ++num;
    int mi = ord[now];
    for (auto &v : g[now])
    {
      if (ord[v.to] == 0)
      {
        v.stat = 1;
        g[v.to][v.rev].stat = 2;
        dfs(v.to);
      }
      if (v.stat == 0) mi = std::min(mi, ord[v.to]);
      else if (v.stat == 1) mi = std::min(mi, low[v.to]);
    }
    low[now] = mi;
  }
};


int main()
{
  int n, m, s, t;
  cin >> n >> m >> s >> t;
  --s, --t;
  vector<pair<int, int>> e(m);
  vector<vector<int>> g(n);
  for (int i = 0; i < m; ++i)
  {
    int u, v;
    cin >> u >> v;
    --u, --v;
    if (u > v) swap(u, v);
    e[i] = {u, v};
    g[u].push_back(v);
    g[v].push_back(u);
  }
  lowlink lw(n, e);
  vector<int> dis(n, 1e9);
  {
    dis[s] = 0;
    queue<int> q;
    for (q.push(s); !q.empty(); q.pop())
    {
      auto now = q.front();
      for (auto to : g[now])
      {
        if (dis[to] > dis[now] + 1)
        {
          dis[to] = dis[now] + 1;
          q.push(to);
        }
      }
    }
  }
  if (dis[t] >= 1e9)
  {
    cout << -1 << endl;
    return 0;
  }
  set<pair<int, int>> st;
  for (auto [u, v] : lw.bri) st.insert({u, v});
  int now = t, ans = dis[t];
  while (now != s)
  {
    for (auto to : g[now])
    {
      if (dis[now] - 1 == dis[to])
      {
        int u = now, v = to;
        if (u > v) swap(u, v);
        if (st.find({u, v}) != st.end()) --ans;
        now = to;
        break;
      }
    }
  }
  cout << ans << endl;
}