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

• 問題: No.3463 Beltway
• ユーザー: kwm_t
• 提出日時: 2026-02-28 16:42:14
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 177 ms / 2,000 ms
• コード長: 4,327 bytes
• コンパイル時間: 4,225 ms
• コンパイル使用メモリ: 364,212 KB
• 実行使用メモリ: 80,324 KB
• 最終ジャッジ日時: 2026-02-28 16:42:22
• 合計ジャッジ時間: 7,602 ms
• ジャッジサーバーID （参考情報）: judge3 / judge4

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

ソースコード

#include <bits/stdc++.h>
//#include <atcoder/all>
using namespace std;
// using namespace atcoder;
// using mint = modint1000000007;
// const int mod = 1000000007;
// using mint = modint998244353;
// const int mod = 998244353;
const int INF = 1e9;
// const long long LINF = 1e18;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep2(i, l, r) for (int i = (l); i < (r); ++i)
#define rrep(i, n) for (int i = (n)-1; i >= 0; --i)
#define rrep2(i, l, r) for (int i = (r)-1; i >= (l); --i)
#define all(x) (x).begin(), (x).end()
#define allR(x) (x).rbegin(), (x).rend()
#define P pair<int, int>
template<typename A, typename B> inline bool chmax(A &a, const B &b) { if (a < b) { a = b; return true; } return false; }
template<typename A, typename B> inline bool chmin(A &a, const B &b) { if (a > b) { a = b; return true; } return false; }
class Lowlink {
	typedef std::vector<std::vector<std::pair<int, int>>> Edge;
public:
	// 頂点数
	int sz;
	// 木
	Edge G;
	// 関節点
	std::vector<int>articulation_points;
	// 橋(Key:idx,Value:child)
	// in[親] < low[子]なら、橋となる。
	std::unordered_map<int, int> bridge;
	// roots
	std::unordered_set<int>roots;
private:
	// dfs順
	std::vector<int>in;
	std::vector<int>out;
	std::vector<int>low;
	// bfs木上で子のリスト
	std::vector<std::vector<int>> child;
public:
	// コンストラクタ
	Lowlink(const Edge &G) : G(G) {}
	// 構築
	void build() {
		sz = G.size();
		in.assign(sz, -1);
		out.assign(sz, -1);
		low.assign(sz, -1);
		child.resize(sz);
		int k = 0;
		for (int i = 0; i < sz; ++i) {
			if (in[i] < 0) {
				roots.insert(i);
				dfs(i, -1, k);
			}
		}
	}
	// 頂点vを取り除いたときに連結成分が1->retになる
	int remove(int v) {
		int c = 0;
		for (auto nv : child[v]) {
			if (in[v] <= low[nv])c++;
		}
		if (!roots.count(v))c++;
		return c;
	}
	// G 上において、s-t パスは必ず辺 a を含むかどうか判定
	bool query(int a, int s, int t) {
		if (!bridge.count(a)) return false;
		int l = in[bridge[a]], r = out[bridge[a]];
		s = in[s], t = in[t];
		return (l <= s and s < r) xor (l <= t and t < r);
	}
	void dump() {
		std::cout << "edge" << std::endl;
		for (int i = 0; i < sz; ++i) for (int j = 0; j < (int)G[i].size(); ++j) std::cout << i << " " << G[i][j].first << " " << G[i][j].second << std::endl;
		std::cout << "in" << std::endl;
		for (int i = 0; i < sz; ++i)std::cout << in[i] << " ";
		std::cout << std::endl;
		std::cout << "out" << std::endl;
		for (int i = 0; i < sz; ++i)std::cout << out[i] << " ";
		std::cout << std::endl;
		std::cout << "low" << std::endl;
		for (int i = 0; i < sz; ++i)std::cout << low[i] << " ";
		std::cout << std::endl;
		std::cout << "bridge" << std::endl;
		for (auto[k, v] : bridge)std::cout << k << " " << v << std::endl;
		std::cout << "articulation_points" << std::endl;
		for (int i = 0; i < (int)articulation_points.size(); ++i) {
			std::cout << articulation_points[i] << " ";
		}std::cout << std::endl;
	}
private:
	void dfs(int v, int p, int &k) {
		in[v] = low[v] = k++;
		bool is_art = false;// 関節点判定
		for (auto[nv, id] : G[v]) {
			if (in[nv] < 0) {
				child[v].push_back(nv);
				dfs(nv, id, k);
				low[v] = std::min(low[v], low[nv]);
				// is関節点?
				if (-1 != p && in[v] <= low[nv]) {
					is_art = true;
				}
				// is橋?
				if (in[v] < low[nv]) {
					bridge[id] = nv;
				}
			}
			else if (id != p) {
				low[v] = std::min(low[v], in[nv]);
			}
		}
		// 根の場合、2つ以上の子があるなら、関節点
		if (-1 == p && child[v].size() >= 2) {
			is_art = true;
		}
		if (is_art) {
			articulation_points.push_back(v);
		}
		out[v] = k++;
	}
};
int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	int v, e, s, g; cin >> v >> e >> s >> g;
	s--, g--;
	vector to(v, vector<P>());
	rep(i, e) {
		int p, q; cin >> p >> q;
		p--, q--;
		to[p].emplace_back(q, i);
		to[q].emplace_back(p, i);
	}
	Lowlink ll(to);
	ll.build();
	vector<int> dp(v, INF);
	dp[s] = 0;
	queue<int>q;
	q.push(s);
	while (!q.empty()) {
		auto v = q.front();
		q.pop();
		for (auto[nv, idx] : to[v]) {
			if (chmin(dp[nv], dp[v] + 1))q.push(nv);
		}
	}
	int ans = dp[g];
	if (ans == INF) {
		cout << -1 << endl;
		return 0;
	}
	rep(i, e) {
		if (ll.query(i, s, g) && ll.bridge[i])ans--;
	}
	cout << ans << endl;
	return 0;
}