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

• 問題: No.3463 Beltway
• ユーザー: harurun
• 提出日時: 2026-02-28 15:44:35
• 言語: C++17 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 261 ms / 2,000 ms
• コード長: 3,619 bytes
• コンパイル時間: 8,954 ms
• コンパイル使用メモリ: 592,464 KB
• 実行使用メモリ: 54,356 KB
• 最終ジャッジ日時: 2026-02-28 15:54:07
• 合計ジャッジ時間: 11,597 ms
• ジャッジサーバーID （参考情報）: judge4 / judge2

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

ソースコード

#ifndef ONLINE_JUDGE
#include "header.hpp"
#else
#include <bits/stdc++.h>
#include <atcoder/all>
#include <boost/multiprecision/cpp_int.hpp>
using cpp_int=boost::multiprecision::cpp_int;
#include <boost/multiprecision/cpp_dec_float.hpp>
template<unsigned size>using cpp_float=boost::multiprecision::number<boost::multiprecision::cpp_dec_float<size>>;
template<unsigned size>using cpp_double=boost::multiprecision::number<boost::multiprecision::cpp_dec_float<size,long long>>;
#endif

using namespace std;
using ll=long long;
inline void yn(bool x){if(x){cout<<"Yes"<<endl;}else{cout<<"No"<<endl;}}
#define double_out(x) fixed << setprecision(x)
template<class T> inline void erase_duplicate(vector<T>& A){sort(A.begin(),A.end());A.erase(unique(A.begin(),A.end()),A.end());}
inline ll powll(ll x,ll n){ll r=1;while(n>0){if(n&1){r*=x;};x*=x;n>>=1;};return r;}

using namespace std;
using ll=long long;

// https://ei1333.github.io/luzhiled/snippets/graph/lowlink.html

template< typename G >
struct LowLink {
  const G &g;
  vector< int > used, ord, low;
  vector< int > articulation;
  vector< pair< int, int > > bridge;
 
  LowLink(const G &g) : g(g) {}
 
  int dfs(int idx, int k, int par) {
    used[idx] = true;
    ord[idx] = k++;
    low[idx] = ord[idx];
    bool is_articulation = false;
    int cnt = 0;
    for(auto &to : g[idx]) {
      if(!used[to]) {
        ++cnt;
        k = dfs(to, k, idx);
        low[idx] = min(low[idx], low[to]);
        is_articulation |= ~par && low[to] >= ord[idx];
        if(ord[idx] < low[to]) bridge.emplace_back(minmax(idx, (int) to));
      } else if(to != par) {
        low[idx] = min(low[idx], ord[to]);
      }
    }
    is_articulation |= par == -1 && cnt > 1;
    if(is_articulation) articulation.push_back(idx);
    return k;
  }
 
  virtual void build() {
    used.assign(g.size(), 0);
    ord.assign(g.size(), 0);
    low.assign(g.size(), 0);
    int k = 0;
    for(int i = 0; i < g.size(); i++) {
      if(!used[i]) k = dfs(i, k, -1);
    }
  }
};



int main(){
    ll N,M;
    cin>>N>>M;
    ll start,goal;
    cin>>start>>goal;
    start--;
    goal--;
    vector<vector<ll>> 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 LL(G);
    LL.build();
    for(ll i=0;i<LL.bridge.size();i++){
        if(LL.bridge[i].first>LL.bridge[i].second){
            swap(LL.bridge[i].first, LL.bridge[i].second);
        }
    }
    sort(LL.bridge.begin(),LL.bridge.end());
    vector<pair<ll,ll>> res(N, {1LL<<60,1LL<<60});
    priority_queue<pair<pair<ll,ll>,ll>, vector<pair<pair<ll,ll>,ll>>, greater<pair<pair<ll,ll>,ll>>> pq;
    res[start]={0,0};
    pq.push({{0,0},start});
    while(!pq.empty()){
        auto [cc,idx]=pq.top();
        auto [d,c]=cc;
        pq.pop();
        if(res[idx]<cc){
            continue;
        }
        for(ll to:G[idx]){
            pair<int,int> key={min(idx,to),max(idx,to)};
            ll xx=lower_bound(LL.bridge.begin(),LL.bridge.end(),key)-LL.bridge.begin();
            ll cost=(xx<LL.bridge.size() && LL.bridge[xx]==key);
            if(res[to].first>res[idx].first+1){
                res[to]={res[idx].first+1, res[idx].second+cost};
                pq.push({res[to],to});
            }else if(res[to].first==res[idx].first && res[to].second>res[idx].second+cost){
                res[to].second=res[idx].second+cost;
                pq.push({res[to],to});
            }
        }
    }
    if(res[goal].first==1LL<<60){
        cout<<-1<<endl;
    }else{
        cout<<res[goal].first-res[goal].second<<endl;
    }
}