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

提出ソース

結果

問題	No.1069 電柱 / Pole (Hard)
ユーザー	kimiyuki
提出日時	2020-05-30 02:49:13
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	384 ms / 2,000 ms
コード長	5,744 bytes
コンパイル時間	2,978 ms
コンパイル使用メモリ	247,516 KB
実行使用メモリ	4,384 KB
最終ジャッジ日時	2023-09-30 21:20:37
合計ジャッジ時間	6,466 ms
ジャッジサーバーID （参考情報）	judge14 / judge11

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

テストケース

テストケース表示

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

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

ソースコード

raw source code

#line 1 "main.cpp"
#define PROBELM "https://yukicoder.me/problems/no/1069"
#define ERROR 1e-4
#include <bits/stdc++.h>
#line 2 "/home/user/GitHub/competitive-programming-library/utils/macros.hpp"
#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))
#define REP3(i, m, n) for (int i = (m); (i) < (int)(n); ++ (i))
#define REP_R(i, n) for (int i = (int)(n) - 1; (i) >= 0; -- (i))
#define REP3R(i, m, n) for (int i = (int)(n) - 1; (i) >= (int)(m); -- (i))
#define ALL(x) std::begin(x), std::end(x)
#line 9 "/home/user/GitHub/competitive-programming-library/graph/yen_algorithm.hpp"

/**
 * @brief K shortest simple paths (Yen's algorithm + Dijkstra, $O(K V (E + V) \log V)$)
 * @param g is an adjacent list of a simple undirected graph
 * @return simple paths. If there are only less than K paths, return all paths in sorted order.
 */
template <class T>
std::vector<std::vector<int> > yen_algorithm_with_dijkstra(const std::vector<std::vector<std::pair<int, T> > > & g, int start, int goal, int k) {
    using namespace std;
    using reversed_priority_queue = priority_queue<pair<T, int> , vector<pair<T, int> >, greater<pair<T, int> > >;

    // trivial cases
    if (k == 0) return vector<vector<int> >();
    if (start == goal) {
        return vector<vector<int> >(1, vector<int>(1, start));
    }
    assert (k >= 1);

    // prepare
    int n = g.size();
    auto dijkstra = [&](int start, const set<int> & removed_vertices, const set<pair<int, int> > & removed_edges) -> pair<T, vector<int> > {
        // dijkstra
        vector<pair<T, int> > dist(n, make_pair(numeric_limits<T>::max(), -1));
        reversed_priority_queue que;
        dist[start] = make_pair(0, -1);
        que.emplace(0, start);
        while (not que.empty()) {
            auto [dist_x, x] = que.top();
            que.pop();
            if (dist[x].first < dist_x) continue;
            for (auto [y, cost] : g[x]) if (not removed_vertices.count(y) and not removed_edges.count(make_pair(x, y))) {
                if (dist_x + cost < dist[y].first) {
                    dist[y] = make_pair(dist_x + cost, x);
                    que.emplace(dist_x + cost, y);
                }
            }
        }

        // reconstruct the path
        if (start != goal and dist[goal].second == -1) {
            // failure
            return make_pair(dist[goal].first, vector<int>());
        }
        vector<int> path;
        for (int x = goal; x != -1; x = dist[x].second) {
            path.push_back(x);
        }
        reverse(ALL(path));
        return make_pair(dist[goal].first, path);
    };
    map<pair<int, int>, double> lookup;
    REP (i, n) {
        for (auto [j, cost] : g[i]) {
            lookup[make_pair(i, j)] = cost;
        }
    }

    // run Yen's algorithm
    vector<vector<int> > result;
    set<pair<T, vector<int> > > que;
    result.push_back(dijkstra(start, set<int>(), set<pair<int, int> >()).second);
    while ((int)result.size() < k) {
        auto & root = result.back();

        T root_cost = 0;
        set<int> removed_vertices;
        vector<int> prefix(result.size());
        iota(ALL(prefix), 0);
        REP (i, (int)root.size() - 1) {
            // remove edges used in other shortest paths from the graph
            set<pair<int, int> > removed_edges;
            vector<int> next_prefix;
            for (int j : prefix) {
                if (i + 1 < result[j].size() and result[j][i] == root[i]) {
                    int x = result[j][i];
                    int y = result[j][i + 1];
                    removed_edges.emplace(x, y);
                    removed_edges.emplace(y, x);
                    next_prefix.push_back(j);
                }
            }
            prefix.swap(next_prefix);

            // make the new path
            auto [spur_cost, spur] = dijkstra(root[i], removed_vertices, removed_edges);
            if (not spur.empty()) {
                vector<int> path(i + spur.size());
                copy(root.begin(), root.begin() + i, path.begin());
                copy(ALL(spur), path.begin() + i);
                que.emplace(root_cost + spur_cost, path);
                if (que.size() > k - (int)result.size()) {
                    que.erase(prev(que.end()));
                }
            }

            // remove vertices in root from the graph
            removed_vertices.insert(root[i]);
            root_cost += lookup[make_pair(root[i], root[i + 1])];
        }

        // found i-th smallest path
        if (que.empty()) {
            return result;
        }
        result.push_back(que.begin()->second);
        que.erase(que.begin());
    }
    return result;
}
#line 6 "main.cpp"
using namespace std;

int main() {
    // input
    int n, m, k; scanf("%d%d%d", &n, &m, &k);
    int start, goal; scanf("%d%d", &start, &goal);
    -- start;
    -- goal;
    vector<long long> x(n), y(n);
    REP (i, n) {
        scanf("%lld%lld", &x[i], &y[i]);
    }
    vector<vector<pair<int, double> > > g(n);
    REP (i, m) {
        int p, q; cin >> p >> q;
        -- p;
        -- q;
        double cost = sqrt(pow(x[p] - x[q], 2) + pow(y[p] - y[q], 2));
        g[p].emplace_back(q, cost);
        g[q].emplace_back(p, cost);
    }

    // solve
    auto path = yen_algorithm_with_dijkstra(g, start, goal, k);
    vector<double> cost(k, -1);
    map<pair<int, int>, double> lookup;
    REP (i, n) {
        for (auto [j, cost] : g[i]) {
            lookup[make_pair(i, j)] = cost;
        }
    }
    REP (i, path.size()) {
        cost[i] = 0;
        REP (j, (int)path[i].size() - 1) {
            cost[i] += lookup[make_pair(path[i][j], path[i][j + 1])];
        }
    }

    // output
    REP (i, k) {
        printf("%.12lf\n", cost[i]);
    }
    return 0;
}