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

• 問題: No.3463 Beltway
• ユーザー: tetra4
• 提出日時: 2026-02-28 16:09:17
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 222 ms / 2,000 ms
• コード長: 3,533 bytes
• コンパイル時間: 4,342 ms
• コンパイル使用メモリ: 361,556 KB
• 実行使用メモリ: 70,540 KB
• 最終ジャッジ日時: 2026-02-28 16:09:27
• 合計ジャッジ時間: 7,256 ms
• ジャッジサーバーID （参考情報）: judge3 / judge7

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

ソースコード

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
[[maybe_unused]] constexpr ll INF = (1LL << 60) - 1;
constexpr ll CON = 1000000ll;

struct Edge {
    ll to;
};
using Graph = vector<vector<Edge>>;
using P = pair<ll, ll>;
/* Lowlink: グラフの関節点・橋を列挙する構造体
    作成: O(E+V)
    関節点の集合: vector<ll> aps
    橋の集合: vector<P> bridges
*/
struct LowLink {
    const Graph &G;
    vector<ll> used, ord, low;
    vector<ll> aps;  // articulation polls
    vector<P> bridges;
    LowLink(const Graph &G_) : G(G_) {
        used.assign(G.size(), 0);
        ord.assign(G.size(), 0);
        low.assign(G.size(), 0);
        ll k = 0;
        for (ll i = 0; i < (ll)G.size(); i++) {
            if (!used[i]) k = dfs(i, k, -1);
        }
        sort(aps.begin(), aps.end());          // 必要ならソートする
        sort(bridges.begin(), bridges.end());  // 必要ならソートする
    }
    ll dfs(ll id, ll k, ll par) {  // id:探索中の頂点, k:dfsで何番目に探索するか, par:idの親
        used[id] = true;
        ord[id] = k++;
        low[id] = ord[id];
        bool is_aps = false;
        ll count = 0;  // 子の数
        for (auto &e : G[id]) {
            if (!used[e.to]) {
                count++;
                k = dfs(e.to, k, id);
                low[id] = min(low[id], low[e.to]);
                if (par != -1 && ord[id] <= low[e.to]) is_aps = true;
                if (ord[id] < low[e.to])
                    bridges.emplace_back(min(id, e.to), max(id, e.to));  // 条件を満たすので橋
            } else if (e.to != par) {                                    // eが後退辺の時
                low[id] = min(low[id], ord[e.to]);
            }
        }
        if (par == -1 && count >= 2) is_aps = true;
        if (is_aps) aps.push_back(id);
        return k;
    }
};

void solve() {
    ll n, m, s, t;
    cin >> n >> m >> s >> t;
    --s, --t;
    Graph G(n);
    for (ll i = 0; i < m; ++i) {
        ll u, v;
        cin >> u >> v;
        --u, --v;
        G[u].push_back({v});
        G[v].push_back({u});
    }
    LowLink lowlink(G);

    vector<vector<pair<ll, ll>>> g(n);
    for (ll i = 0; i < n; ++i) {
        for (auto e : G[i]) {
            if (e.to < i) continue;
            bool f = binary_search(lowlink.bridges.begin(), lowlink.bridges.end(),
                                   pair<ll, ll>{i, e.to});
            ll w = f ? CON + 1 : CON;
            g[i].emplace_back(e.to, w);
            g[e.to].emplace_back(i, w);
        }
    }

    vector<ll> cost(n, INF);

    auto dijkstra = [&](const vector<ll> &starts) -> void {
        priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> que;
        for (auto s : starts) {
            cost[s] = 0;
            que.emplace(0, s);
        }
        while (!que.empty()) {
            auto [c, cur] = que.top();
            que.pop();
            if (c > cost[cur]) continue;
            for (auto [nxt, w] : g[cur]) {
                if (cost[nxt] <= c + w) continue;
                cost[nxt] = c + w;
                que.emplace(cost[nxt], nxt);
            }
        }
    };

    dijkstra({s});
    if (cost[t] == INF) {
        cout << -1 << "\n";
        return;
    }
    ll len = cost[t] / CON;
    ll bri = cost[t] % CON;
    cout << len - bri << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}