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

• 問題: No.3463 Beltway
• ユーザー: hato336
• 提出日時: 2026-02-28 15:22:26
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: WA
• 実行時間: -
• コード長: 3,000 bytes
• コンパイル時間: 4,216 ms
• コンパイル使用メモリ: 359,640 KB
• 実行使用メモリ: 83,828 KB
• 最終ジャッジ日時: 2026-02-28 15:53:16
• 合計ジャッジ時間: 8,335 ms
• ジャッジサーバーID （参考情報）: judge1 / judge7

ファイルパターン	結果
sample	AC * 1
other	AC * 11 WA * 6

ソースコード

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
#define ov4(a, b, c, d, name, ...) name
#define rep3(i, a, b, c) for(ll i = (a); i < (b); i += (c))
#define rep2(i, a, b) rep3(i, a, b, 1)
#define rep1(i, n) rep2(i, 0, n)
#define rep0(n) rep1(aaaaa, n)
#define rep(...) ov4(__VA_ARGS__, rep3, rep2, rep1, rep0)(__VA_ARGS__)
#define per(i, a, b) for(ll i = (a)-1; i >= (b); i--)
#define fore(e, v) for(auto&& e : v)
#define all(a) begin(a), end(a)
#define si(a) (int)(size(a))
#define lb(v, x) (lower_bound(all(v), x) - begin(v))
#define eb emplace_back

template<typename T, typename S> bool chmin(T& a, const S& b) { return a > b ? a = b, 1 : 0; }
template<typename T, typename S> bool chmax(T& a, const S& b) { return a < b ? a = b, 1 : 0; }

const int INF = 1e9 + 100;
const ll INFL = 3e18 + 100;

#define i128 __int128_t

template<typename G> struct LL {
   int n;
   const G g;
   vi ord, low, arti;
   vector<pii> bridge;

   LL(G g) : n(si(g)), g(g), ord(si(g), -1), low(si(g), -1) {
      int k = 0;
      rep(i, n) {
         if(ord[i] == -1) k = dfs(i, k, -1);
      }
   }

   int dfs(int x, int k, int p) {
      low[x] = (ord[x] = k++);
      int cnt = 0;
      bool is_arti = false, second = false;
      fore(e, g[x]) {
         if(ord[e] == -1) {
            cnt++;
            k = dfs(e, k, x);
            chmin(low[x], low[e]);
            is_arti |= (p != -1) && (low[e] >= ord[x]);
            if(ord[x] < low[e]) bridge.eb(minmax(x, e));
         } else if(e != p or second) {
            chmin(low[x], ord[e]);
         } else {
            second = true;
         }
      }
      is_arti |= p == -1 && cnt > 1;
      if(is_arti) arti.eb(x);
      return k;
   }
};


int main() { 
    cin.tie(0)->sync_with_stdio(0);
    ll n,m,s,g;
    cin >> n >> m >> s >> g;
    s--;
    g--;
    vector<vector<int>> edge(n);
    
    rep(i,m){
        ll u,v;
        cin >> u >> v;
        u--;
        v--;
        edge[u].push_back(v);
        edge[v].push_back(u);
    }
    LL<vector<vector<int>>> lowlink(edge);
    set<pll> se;
    for(auto [u,v]:lowlink.bridge){
        se.emplace(u,v);
        se.emplace(v,u);
    }

    vl dist(n,1LL<<60);
    dist[s] = 0;
    priority_queue<pll,vector<pll>, greater<pll>> q;
    q.emplace(s,0);
    while(!q.empty()){
        auto [v,now] = q.top();
        q.pop();
        if(v > dist[now]){continue;}
        ll x = dist[now] / n;
        ll y = dist[now] % n;
        for(auto to:edge[now]){
            ll cost = 0;
            if(se.count(make_pair(now,to)) == 1){
                cost = 1;
            }
            if(chmin(dist[to], (x + 1) * n + (y + cost))){
                q.emplace(dist[to],to);
            }
        }
    }
    ll ans;
    if(dist[g] == (1LL<<60)){
        ans = -1;
    }
    else{
        ans = dist[g] / n - dist[g] % n;
    }
    cerr << dist[g] << endl;
    cout << ans << endl;



}