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

• 問題: No.3463 Beltway
• ユーザー: 0214sh7
• 提出日時: 2026-02-28 16:30:55
• 言語: C++17 (gcc 15.2.0 + boost 1.89.0)
• 結果: WA
• 実行時間: -
• コード長: 4,944 bytes
• コンパイル時間: 1,842 ms
• コンパイル使用メモリ: 148,280 KB
• 実行使用メモリ: 102,040 KB
• 最終ジャッジ日時: 2026-02-28 16:31:02
• 合計ジャッジ時間: 6,143 ms
• ジャッジサーバーID （参考情報）: judge4 / judge2

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

ソースコード

// #include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <algorithm>
#include <cassert>
#include <functional>
#include <numeric>
#include <bitset>
#include <iomanip>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll,ll> PP;
// #define MOD 1000000007
#define MOD 998244353
#define INF 2305843009213693951ll
#define PI 3.141592653589
#define setdouble setprecision
#define REP(i,n) for(ll i=0;i<(n);++i)
#define OREP(i,n) for(ll i=1;i<=(n);++i)
#define RREP(i,n) for(ll i=(n)-1;i>=0;--i)
#define ORREP(i,n) for(ll i=(n);i>=1;--i)
#define rep(i,a,b) for(ll i=(a);i<=(b);++i)
#define ALL(v) (v).begin(), (v).end()
#define chmin(k,m) k = min(k,m)
#define chmax(k,m) k = max(k,m)
#define GOODBYE do { cout << "-1" << endl; return 0; } while (false)
#define MM <<" "<<
#define Endl endl

class Dijkstra{
    // Copyright (c) 2023 0214sh7
    // https://github.com/0214sh7/library/
    private:
    typedef std::pair<long long,int> P;
    std::vector<std::vector<P>> G;
    int V;
    std::priority_queue<P,std::vector<P>,std::greater<P>> que;
    
    public:
    void init(int N,std::vector<std::pair<std::pair<int,int>,long long>> edge){
        //頂点数を決定する
        V=N;
        
        //辺集合を扱いやすい形式に変換する
        G.resize(V);
        for(int i=0;i<edge.size();i++){
            int from=edge[i].first.first,to=edge[i].first.second;
            long long cost=edge[i].second;
            G[from].push_back({cost,to});
        }
    }
    
    Dijkstra(int N,std::vector<std::pair<std::pair<int,int>,long long>> edge){
        init(N,edge);
    }

    std::vector<long long> solve(int s){
        std::vector<long long> d;
        //INFで初期化する
        for(int i=0;i<V;i++){
            d.push_back(INF);
        }
        d[s]=0;
        que.push({0,s});
        //queは{cost,to}をコストが小さい順に出す
        while(!que.empty()){
            P p = que.top();
            que.pop();
            int v=p.second;
            if(d[v]<p.first)continue;
            for(int i=0;i<G[v].size();i++){
                P e = G[v][i];
                if(d[e.second]>d[v]+e.first){
                    d[e.second] = d[v]+e.first;
                    que.push({d[e.second],e.second});
                }
            }
        }
        return d;
    }
};

class unionfind{
    // Copyright (c) 2024 0214sh7
    // https://github.com/0214sh7/library/
    private:
    std::vector<int> par,rank,size_;

    public:

    void init(int N){
        par.assign(N,0);
        rank.assign(N,0);
        size_.assign(N,1);
        for(int i=0;i<N;i++){
            par[i] = i;
        }
    }

    unionfind(int N){
        init(N);
    }

    int leader(int k){
        if(par[k]==k){
            return k;
        }
        par[k] = leader(par[k]);
        return par[k];
    }

    bool same(int p,int q){
        return leader(p)==leader(q);
    }

    int size(int k){
        return size_[leader(k)];
    }

    void merge(int p, int q){
        p = leader(p);
        q = leader(q);
        if(p==q)return;
        if(rank[p]<rank[q])std::swap(p,q);
        par[q]=p;
        if(rank[p]==rank[q])rank[p]++;
        size_[p] += size_[q];
        size_[q] = 0;
    }

};

int main(void){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    ll N,M,S,T;
    cin >> N >> M >> S >> T;
    S--;T--;
    vector<set<ll>> G(N); 
    vector<ll> A(M),B(M);
    vector<ll> dis(N,0);

    REP(i,M){
        ll a,b;
        cin >> a >> b;
        a--;b--;
        A[i] = a;
        B[i] = b;
        
            G[a].insert(b);
            G[b].insert(a);
    }
    vector<set<ll>> Gt = G; 

    unionfind UF(N);
    REP(i,N){
        for(ll e:G[i]){
            UF.merge(i,e);
        }
    }

    vector<ll> loop(N,0);
    REP(i,M){
        if(A[i]==B[i]){
            loop[UF.leader(A[i])]=1;
        }
    }

    queue<ll> que;
    REP(i,N){
        if(G[i].size()==1){
            que.push(i);
        }
    }
    
    while(!que.empty()){
        ll q = que.front();
        que.pop();
        if(Gt[q].size()!=1)continue;
        ll e = *Gt[q].begin();
        Gt[e].erase(Gt[e].find(q));
        Gt[q].erase(Gt[q].find(e));
        if(Gt[e].size()==1){
            que.push(e);
        }
    }

    std::vector<std::pair<std::pair<int,int>,long long>> E;
    
    const ll Bs = 10'000'000;

    REP(v,N){
        for(ll e:G[v]){
            ll c = Bs;
            if(Gt[v].find(e)!=Gt[v].end() || loop[UF.leader(v)]==1){
                c--;
            }
            E.push_back({{v,e},c});
        }
    }

    Dijkstra dijk(N,E);
    vector<ll> d = dijk.solve(S);
    ll Ans = d[T];
    if(Ans==INF){
        cout << -1 << endl;
    }else{
        Ans%=Bs;
        Ans=(Bs-Ans)%Bs;

        cout << Ans << endl;
    }

    return 0;
    
}