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

• 問題: No.3463 Beltway
• ユーザー: 0214sh7
• 提出日時: 2026-02-28 15:27:48
• 言語: C++17 (gcc 15.2.0 + boost 1.89.0)
• 結果: WA
• 実行時間: -
• コード長: 3,726 bytes
• コンパイル時間: 1,758 ms
• コンパイル使用メモリ: 143,300 KB
• 実行使用メモリ: 94,704 KB
• 最終ジャッジ日時: 2026-02-28 15:53:28
• 合計ジャッジ時間: 5,880 ms
• ジャッジサーバーID （参考情報）: judge1 / judge3

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

ソースコード

// #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;
    }
};


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> dis(N,0);
    REP(i,M){
        ll a,b;
        cin >> a >> b;
        a--;b--;

        G[a].insert(b);
        G[b].insert(a);
        dis[a]++;
        dis[b]++;
    }
    vector<set<ll>> Gt = G; 

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

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

    REP(v,N){
        for(ll e:G[v]){
            ll c = B;
            if(Gt[v].find(e)!=Gt[v].end()){
                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%=B;
        Ans=(B-Ans)%B;

        cout << Ans << endl;
    }

    return 0;
    
}