結果

問題 No.1069 電柱 / Pole (Hard)
コンテスト
ユーザー bin101
提出日時 2022-07-07 12:36:16
言語 C++17(clang)
(17.0.6 + boost 1.87.0)
結果
AC  
実行時間 107 ms / 2,000 ms
コード長 4,930 bytes
コンパイル時間 5,103 ms
コンパイル使用メモリ 174,464 KB
実行使用メモリ 15,104 KB
最終ジャッジ日時 2024-07-23 15:10:31
合計ジャッジ時間 7,347 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 79
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

/*
1~k番目のs-t shortest pathを求める
pathがk個存在しない場合、できる限り求めて返す
O(NK((N+M)logN))ぐらい？ logついてそう
参考
https://qiita.com/nariaki3551/items/821dc6ffdc552d3d5f22
https://yamakuramun.info/2021/02/24/309/
*/
#include<bits/stdc++.h> 
using namespace std;
using ll=long long int;
//using Int=__int128;
#define ALL(A) A.begin(),A.end()
template<typename T1,typename T2> bool chmin(T1 &a,T2 b){if(a<=b)return 0; a=b; return 1;}
template<typename T1,typename T2> bool chmax(T1 &a,T2 b){if(a>=b)return 0; a=b; return 1;}
template<typename T> constexpr int bitUP(T x,int a){return (x>>a)&1;}

template<typename T >
struct edge {
	int to;
	T cost;
	edge()=default;
	edge(int to, T cost) : to(to), cost(cost) {}

};
template<typename T>
using WeightGraph=vector<vector<edge<T>>>;

//https://qiita.com/nariaki3551/items/821dc6ffdc552d3d5f22
//https://yamakuramun.info/2021/02/24/309/
template<typename T>
vector<pair<T,vector<int>>> YenAlgorithm(const WeightGraph<T> &graph,int k,int s,int t){
    assert(k>=1);
    int N=graph.size();
    const auto max_inf = numeric_limits< T >::max();
    const auto min_inf = numeric_limits< T >::lowest();

    assert(0<=s and s<N);
    assert(0<=t and t<N);
    using P=pair<T,vector<int>>;

    map<vector<int>,unordered_set<int>> ban_edge;
    //Pを返す
    auto dijkstra=[&](const vector<int> &spur_path){
        using pti=pair<T,int>;
        vector<pti> dist(N,pti(max_inf,-1));
        for(int v:spur_path){
            dist[v].first=min_inf;
        }
        priority_queue<pti,vector<pti>,greater<pti>> que;
        int start=s;
        if(spur_path.size()) start=spur_path.back();
        dist[start].first=0;
        auto &ban=ban_edge[spur_path];

        que.emplace(0,start);
        while(!que.empty()){
            T cost;
            int v;
            tie(cost,v)=que.top();
            if(v==t) break;
            que.pop();
            if(dist[v].first<cost) continue;
            for(auto &e:graph[v]){
                if(v==start and ban.count(e.to)) continue;
                auto next_cost=cost+e.cost;
                if(chmin(dist[e.to].first,next_cost)){
                    dist[e.to].second=v;
                    que.emplace(dist[e.to].first,e.to);
                }
            }
        }
        vector<int> path;
        if(dist[t].first==max_inf){
            return P(dist[t].first,path);
        }
        int now=t;
        while(now!=start){
            path.push_back(now);
            now=dist[now].second;
        }
        //reverse(path.begin(),path.end());
        return P(dist[t].first,path);    
    };
    vector<P> ans;
    auto compare=[](P a,P b){
        return a.first>b.first;
    };
    priority_queue<P,vector<P>,decltype(compare)> candidate(compare);
    vector<int> prev_path;
    vector<int> spur_path;
    set<vector<int>> set_ans;
    while(k--){
        if(ans.size()==0){
            auto c=dijkstra(spur_path);
            c.second.push_back(s);
            reverse(c.second.begin(),c.second.end());
            if(c.first!=max_inf) candidate.push(c);
        }else{
            T prev_cost=0;
            for(int i=0;i<int(prev_path.size())-1;i++){
                spur_path.push_back(prev_path[i]);
                ban_edge[spur_path].insert(prev_path[i+1]);
                auto c=dijkstra(spur_path);
                for(int j=i;j>=0;j--) c.second.push_back(prev_path[j]);
                reverse(c.second.begin(),c.second.end());
                c.first+=prev_cost;
                if(c.first!=max_inf) candidate.push(c);
                for(auto &e:graph[prev_path[i]]){
                    if(e.to==prev_path[i+1]) prev_cost+=e.cost;
                }
            }
        }
        bool ok=false;
        while(candidate.size()){
            auto c=candidate.top();
            candidate.pop();
            if(set_ans.count(c.second)) continue;
            ans.push_back(c);
            prev_path=c.second;
            ok=true;
            set_ans.insert(c.second);
            break;
        }
        if(not ok) break;
        spur_path.clear();
    }
    return ans;
}


void solve(){
    int N,M,K;
    cin>>N>>M>>K;
    int s,t;
    cin>>s>>t;
    s--; t--;
    WeightGraph<double> graph(N);
    vector<int> p(N),q(N);
    for(int i=0;i<N;i++){
        cin>>p[i]>>q[i];
    }
    for(int i=0;i<M;i++){
        int a,b;
        cin>>a>>b;
        a--; b--;
        double dp=p[a]-p[b],dq=q[a]-q[b];
        double cost=sqrt(dp*dp+dq*dq);
        graph[a].emplace_back(b,cost);
        graph[b].emplace_back(a,cost);
    }
    auto ans=YenAlgorithm(graph,K,s,t);
    for(int i=0;i<K;i++){
        if(i>=int(ans.size())){
            cout<<-1<<endl;
        }else{
            cout<<ans[i].first<<endl;
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(20);
    int T=1;
    while(T--) solve();
}
0