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

• 問題: No.3463 Beltway
• ユーザー: jupiter_68
• 提出日時: 2026-02-28 14:58:14
• 言語: C++17 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 146 ms / 2,000 ms
• コード長: 6,361 bytes
• コンパイル時間: 2,711 ms
• コンパイル使用メモリ: 239,000 KB
• 実行使用メモリ: 29,216 KB
• 最終ジャッジ日時: 2026-02-28 15:51:51
• 合計ジャッジ時間: 4,821 ms
• ジャッジサーバーID （参考情報）: judge3 / judge4

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

ソースコード

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using pll = pair<ll, ll>;
using vl = vector<ll>;
template <class T> using vec = vector<T>;
template <class T> using vv = vec<vec<T>>;
template <class T> using vvv = vv<vec<T>>;
template <class T> using minpq = priority_queue<T, vector<T>, greater<T>>;
#define all(a) (a).begin(),(a).end()
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define reps(i, l, r) for(ll i = (l); i < (r); ++i)
#define rrep(i, l, r) for(ll i = (r)-1; i >= (l); --i)
#define sz(x) (ll) (x).size()
template <typename T>
bool chmax(T &a, const T& b) { return a < b ? a = b, true : false; }
template <typename T>
bool chmin(T &a, const T& b) { return a > b ? a = b, true : false; }

struct Edge {
    ll from, to, cost;
    Edge (ll from, ll to, ll cost = 1ll) : from(from), to(to), cost(cost) {}
};
struct Graph {
    vector<vector<Edge>> G;
    Graph() = default;
    explicit Graph(ll N) : G(N) {}
    size_t size() const {
        return G.size();
    }
    void add(ll from, ll to, ll cost = 1ll, bool direct = 0) {
        G[from].emplace_back(from, to, cost);
        if (!direct) G[to].emplace_back(to, from, cost);
    }
    vector<Edge> &operator[](const int &k) {
        return G[k];
    }
};
using Edges = vector<Edge>;

const ll mod = 998244353; // 1000000007;

struct mint {
    ll x;
    mint(ll y = 0) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}
    mint &operator+=(const mint &p) {
        if ((x += p.x) >= mod) x -= mod;
        return *this;
    }
    mint &operator-=(const mint &p) {
        if ((x += mod - p.x) >= mod) x -= mod;
        return *this;
    }
    mint &operator*=(const mint &p) {
        x = (ll)(1ll * x * p.x % mod);
        return *this;
    }
    mint &operator/=(const mint &p) {
        *this *= p.inv();
        return *this;
    }
    mint operator-() const { return mint(-x); }
    mint operator+(const mint &p) const { return mint(*this) += p; }
    mint operator-(const mint &p) const { return mint(*this) -= p; }
    mint operator*(const mint &p) const { return mint(*this) *= p; }
    mint operator/(const mint &p) const { return mint(*this) /= p; }
    bool operator==(const mint &p) const { return x == p.x; }
    bool operator!=(const mint &p) const { return x != p.x; }
    friend ostream &operator<<(ostream &os, const mint &p) { return os << p.x; }
    friend istream &operator>>(istream &is, mint &a) {
        ll t; is >> t; a = mint(t); return (is);
    }
    mint inv() const { return pow(mod - 2); }
    mint pow(ll n) const {
        mint ret(1), mul(x);
        while (n > 0) {
            if (n & 1) ret *= mul;
            mul *= mul;
            n >>= 1;
        }
        return ret;
    }
};

struct UnionFind {
  vector<int> data;

  UnionFind() = default;

  explicit UnionFind(size_t sz) : data(sz, -1) {}

  bool unite(int x, int y) {
    x = find(x), y = find(y);
    if (x == y) return false;
    if (data[x] > data[y]) swap(x, y);
    data[x] += data[y];
    data[y] = x;
    return true;
  }

  int find(int k) {
    if (data[k] < 0) return (k);
    return data[k] = find(data[k]);
  }

  int size(int k) { return -data[find(k)]; }

  bool same(int x, int y) { return find(x) == find(y); }

  vector<vector<int> > groups() {
    int n = (int)data.size();
    vector<vector<int> > ret(n);
    for (int i = 0; i < n; i++) {
      ret[find(i)].emplace_back(i);
    }
    ret.erase(remove_if(begin(ret), end(ret),
                        [&](const vector<int>& v) { return v.empty(); }),
              end(ret));
    return ret;
  }
};

struct IncrementalBridgeConnectivity {
 private:
  UnionFind cc, bcc;
  vector<int> bbf;
  size_t bridge;

  int size() { return bbf.size(); }

  int par(int x) { return bbf[x] == size() ? size() : bcc.find(bbf[x]); }

  int lca(int x, int y) {
    unordered_set<int> used;
    for (;;) {
      if (x != size()) {
        if (!used.insert(x).second) return x;
        x = par(x);
      }
      swap(x, y);
    }
  }

  void compress(int x, int y) {
    while (bcc.find(x) != bcc.find(y)) {
      int nxt = par(x);
      bbf[x] = bbf[y];
      bcc.unite(x, y);
      x = nxt;
      --bridge;
    }
  }

  void link(int x, int y) {
    int v = x, pre = y;
    while (v != size()) {
      int nxt = par(v);
      bbf[v] = pre;
      pre = v;
      v = nxt;
    }
  }

 public:
  IncrementalBridgeConnectivity() = default;

  explicit IncrementalBridgeConnectivity(int sz)
      : cc(sz), bcc(sz), bbf(sz, sz), bridge(0) {}

  int find(int k) { return bcc.find(k); }

  size_t bridge_size() const { return bridge; }

  void add_edge(int x, int y) {
    x = bcc.find(x);
    y = bcc.find(y);
    if (cc.find(x) == cc.find(y)) {
      int w = lca(x, y);
      compress(x, w);
      compress(y, w);
    } else {
      if (cc.size(x) > cc.size(y)) swap(x, y);
      link(x, y);
      cc.unite(x, y);
      ++bridge;
    }
  }
};

ll INF = 4e18;
//need: Graph.cpp
void dijkstra(const Graph &G, ll s, vector<long long>& dis) {
    int N = G.size();
    dis.assign(N, INF);
    priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;
    dis[s] = 0;
    pq.emplace(dis[s], s);
    while (!pq.empty()) {
        pair<ll, ll> p = pq.top(); pq.pop();
        int v = p.second;
        if (dis[v] < p.first) {
            continue;
        }
        for (auto& e : G.G[v]) {
            if (dis[e.to] > dis[v] + e.cost) {
                dis[e.to] = dis[v] + e.cost;
                pq.emplace(dis[e.to], e.to);
            }
        }
    }
}

void solve(){
    ll N, M, X, Y; cin >> N >> M >> X >> Y; X--; Y--;
    IncrementalBridgeConnectivity G(N);
    vec<pll> E(M);
    rep(i, M){
        ll u, v; cin >> u >> v; u--; v--;
        E[i] = {u, v};
        G.add_edge(u, v);
    }
    vl cyc(M, 0);
    rep(i, M){
        auto [u, v] = E[i];
        if(G.find(u) != G.find(v)) cyc[i] = 1;
    }
    Graph Gr(N);
    rep(i, M){
        auto [u, v] = E[i];
        Gr.add(u, v, 10000000 + cyc[i]);
    }
    vl dis(N);
    dijkstra(Gr, X, dis);
    ll D = dis[Y];
    if(D == INF){
        cout << -1 << endl;
        return;
    }
    cout << D / 10000000 - D % 10000000 << endl;
}

int main(){
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    int t = 1;
    // cin >> t;
    while(t--){
        solve();
    }
}