#776509 (C++17(clang)) No.1069 電柱 / Pole (Hard)

提出ソース

結果

問題	No.1069 電柱 / Pole (Hard)
ユーザー	bin101
提出日時	2022-07-07 12:36:16
言語	C++17(clang) (17.0.6 + boost 1.83.0)
結果	AC
実行時間	105 ms / 2,000 ms
コード長	4,930 bytes
コンパイル時間	6,954 ms
コンパイル使用メモリ	146,340 KB
実行使用メモリ	15,280 KB
最終ジャッジ日時	2023-09-30 21:23:23
合計ジャッジ時間	10,472 ms
ジャッジサーバーID （参考情報）	judge13 / judge15

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 4,376 KB
testcase_01	AC	2 ms 4,376 KB
testcase_02	AC	2 ms 4,376 KB
testcase_03	AC	2 ms 4,380 KB
testcase_04	AC	105 ms 7,852 KB
testcase_05	AC	84 ms 15,280 KB
testcase_06	AC	5 ms 4,376 KB
testcase_07	AC	6 ms 4,380 KB
testcase_08	AC	3 ms 4,376 KB
testcase_09	AC	4 ms 4,380 KB
testcase_10	AC	4 ms 4,380 KB
testcase_11	AC	2 ms 4,376 KB
testcase_12	AC	2 ms 4,376 KB
testcase_13	AC	3 ms 4,380 KB
testcase_14	AC	2 ms 4,376 KB
testcase_15	AC	3 ms 4,376 KB
testcase_16	AC	3 ms 4,376 KB
testcase_17	AC	3 ms 4,380 KB
testcase_18	AC	3 ms 4,380 KB
testcase_19	AC	5 ms 4,380 KB
testcase_20	AC	2 ms 4,376 KB
testcase_21	AC	3 ms 4,380 KB
testcase_22	AC	3 ms 4,376 KB
testcase_23	AC	6 ms 4,376 KB
testcase_24	AC	5 ms 4,380 KB
testcase_25	AC	5 ms 4,380 KB
testcase_26	AC	4 ms 4,380 KB
testcase_27	AC	5 ms 4,380 KB
testcase_28	AC	5 ms 4,376 KB
testcase_29	AC	3 ms 4,376 KB
testcase_30	AC	2 ms 4,376 KB
testcase_31	AC	2 ms 4,376 KB
testcase_32	AC	2 ms 4,380 KB
testcase_33	AC	2 ms 4,380 KB
testcase_34	AC	2 ms 4,380 KB
testcase_35	AC	2 ms 4,380 KB
testcase_36	AC	2 ms 4,380 KB
testcase_37	AC	2 ms 4,376 KB
testcase_38	AC	2 ms 4,376 KB
testcase_39	AC	2 ms 4,380 KB
testcase_40	AC	2 ms 4,380 KB
testcase_41	AC	2 ms 4,376 KB
testcase_42	AC	2 ms 4,376 KB
testcase_43	AC	2 ms 4,376 KB
testcase_44	AC	5 ms 4,376 KB
testcase_45	AC	3 ms 4,380 KB
testcase_46	AC	4 ms 4,380 KB
testcase_47	AC	4 ms 4,376 KB
testcase_48	AC	4 ms 4,376 KB
testcase_49	AC	3 ms 4,380 KB
testcase_50	AC	2 ms 4,380 KB
testcase_51	AC	4 ms 4,376 KB
testcase_52	AC	2 ms 4,376 KB
testcase_53	AC	4 ms 4,380 KB
testcase_54	AC	2 ms 4,380 KB
testcase_55	AC	2 ms 4,380 KB
testcase_56	AC	1 ms 4,380 KB
testcase_57	AC	2 ms 4,380 KB
testcase_58	AC	2 ms 4,376 KB
testcase_59	AC	2 ms 4,376 KB
testcase_60	AC	2 ms 4,376 KB
testcase_61	AC	2 ms 4,376 KB
testcase_62	AC	1 ms 4,376 KB
testcase_63	AC	2 ms 4,376 KB
testcase_64	AC	2 ms 4,376 KB
testcase_65	AC	2 ms 4,376 KB
testcase_66	AC	2 ms 4,376 KB
testcase_67	AC	2 ms 4,376 KB
testcase_68	AC	2 ms 4,376 KB
testcase_69	AC	3 ms 4,376 KB
testcase_70	AC	3 ms 4,380 KB
testcase_71	AC	2 ms 4,380 KB
testcase_72	AC	3 ms 4,376 KB
testcase_73	AC	3 ms 4,376 KB
testcase_74	AC	3 ms 4,380 KB
testcase_75	AC	3 ms 4,380 KB
testcase_76	AC	4 ms 4,376 KB
testcase_77	AC	5 ms 4,376 KB
testcase_78	AC	2 ms 4,380 KB
testcase_79	AC	4 ms 4,376 KB
testcase_80	AC	5 ms 4,376 KB
testcase_81	AC	3 ms 4,380 KB
testcase_82	AC	3 ms 4,376 KB

権限があれば一括ダウンロードができます

ソースコード

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();
}

yukicoder

結果

テストケース

ソースコード