#864915 (C++17(gcc12)) No.5007 Steiner Space Travel

• 問題: No.5007 Steiner Space Travel
• ユーザー: tmikada
• 提出日時: 2023-04-30 10:56:51
• 言語: C++17(gcc12) (gcc 12.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 15 ms / 1,000 ms
• コード長: 7,636 bytes
• コンパイル時間: 2,846 ms
• コンパイル使用メモリ: 221,144 KB
• 実行使用メモリ: 4,372 KB
• スコア: 6,485,937
• 最終ジャッジ日時: 2023-04-30 10:56:58
• 合計ジャッジ時間: 5,455 ms
• ジャッジサーバーID （参考情報）: judge17 / judge13

ファイルパターン	結果
other	AC * 30

ソースコード

#include <bits/stdc++.h>
#ifdef LOCAL
#include <debug_print.hpp>
#define debug(...) debug_print::multi_print(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...) (static_cast<void>(0))
#endif

using namespace std;
using ll=long long;

// Start 2023.04.23 21:00 
// End   
// Time  min

// MTK005

constexpr ll TYPE_PLANET = 1;
constexpr ll TYPE_STATION = 2;
constexpr ll ALPHA = 5;
constexpr ll INF = (1LL << 60);

struct Pos {
    int x,y;
    ll type;
    Pos(int x, int y, ll type) : x(x), y(y), type(type) {}
};
std::ostream& operator<<(std::ostream& os, const Pos& pos) {
    std::ostringstream oss;
    oss << "(" << pos.x << ", " << pos.y << "), " << pos.type << "";
    os << oss.str();
    return os;
}

struct Solver {
	int N = 0;
	int M = 0;
    vector<Pos> points;

    Solver(int n, int m, vector<Pos>& points) : N(n),M(m),points(points) {}

    void test() {
        debug(N,M,points);
    }

    void solve() {

        // 貪欲法
        set_station();
        // debug(points);


        // 全点間エネルギーを計算
        vector<vector<int>> distances(N+M,vector<int>(N+M));
        for(int i=0; i<N+M; i++) {
            for(int j=0; j<N+M; j++) {
                distances[i][j] = calc_energy(i,j);
            }
        }
        // debug(distances);

        // ワーシャルフロイド
        // kを経由した方がエネルギーが少ない場合もある
        for(int k=0; k<N+M; k++) {
            for(int i=0; i<N+M; i++) {
                for(int j=0; j<N+M; j++) {
                    int d = distances[i][k] + distances[k][j];
                    distances[i][j] = min(distances[i][j],d);
                }
            }
        }
        // debug(distances);

        // 惑星1からスタートする
        // 一番近い惑星＋宇宙ステーションを選び続ける
        vector<int> visited(N+M,0);
        vector<int> route;
        visited[0]++;
        route.push_back(0);

        int v = 0;
        for(int i=0; i<N-1; i++) {
            int nearest_dist = INT_MAX;
            int nearest_v = -1;

            // 一番近い惑星を探す
            for(int next=0; next<N; next++) {
                if(visited[next] > 0) continue;

                // int d = calc_energy(v,next);
                int d = distances[v][next];
                if(d < nearest_dist) {
                    nearest_dist = d;
                    nearest_v = next;
                }
                // debug(d);
            }
            // 次の頂点に移動
            // dijkstraで経路を復元
            vector<int> path = djikstra(v,nearest_v);
            for(auto p : path) {
                route.push_back(p);
            }

            v = nearest_v;
            visited[v]++;
            // route.push_back(nearest_v);
        }
        // 最後に惑星1に戻る
        route.push_back(0);
        // debug(visited);
        debug(route);  

        // ここから2-opt？
        TwoOpt(route,distances);
        debug(route);  

        output(route);      
    }

    void output(vector<int>& route) {
        // 宇宙ステーションの座標
        for(int i=N; i<N+M; i++) {
            if(points[i].type == TYPE_STATION) {
                cout << points[i].x << " " << points[i].y << endl;
            }
        }

        // 経路の長さ
        cout << route.size() << endl;

        // 経路
        for(auto i : route) {
            Pos pos = points[i];
            if(pos.type == TYPE_PLANET) {
                cout << pos.type << " " << i+1 << endl;
            }
            else {
                cout << pos.type << " " << i+1-N << endl;
            }
        }
    }

    void set_station() {
        // 宇宙ステーションの座標は適当に決め打ち
        vector<pair<int,int>> v;
        v.push_back({300,300});
        v.push_back({300,500});
        v.push_back({300,700});
        v.push_back({500,300});
        v.push_back({500,700});
        v.push_back({700,300});
        v.push_back({700,500});
        v.push_back({700,700});
        for(int i=0; i<M; i++) {
            // points.emplace_back(Pos(v[i].first,v[i].second,TYPE_STATION));
            points.emplace_back(v[i].first,v[i].second,TYPE_STATION);
            // points.emplace_back(RandInt(0,1000),RandInt(0,1000),TYPE_STATION);
        }
    }

    void TwoOpt(vector<int>& route, vector<vector<int>>& distances) {
        debug(route.size());
        for(int i=1; i<route.size()-3; i++) {
            for(int j=i+2; j<route.size()-1; j++) {
                debug(i,j);
                if(distances[route[i]][route[j]] + distances[route[i+1]][route[j+1]] 
                    < distances[route[i]][route[i+1]] + distances[route[j]][route[j+1]]) {
                    for(int k=0; k<(j-i)/2; k++) {
                        // int temp = route[i+1+k];
                        // route[i+1+k] = route[j-k];
                        // route[j-k] = temp;
                        debug(route[i+1+k],route[j-k]);
                        swap(route[i+1+k],route[j-k]);
                    }
                }
            }
        }

    }

    // a以上b以下のランダム
    int RandInt(int a, int b) {
        return a + rand() % (b-a+1);
    }

    int calc_energy(int i, int j) {
        int dx, dy;
        int energy;
        auto [x1, y1, type1] = points[i];
        auto [x2, y2, type2] = points[j];
        dx = x1 - x2;
        dy = y1 - y2;
        energy = dx * dx + dy * dy;

        // 惑星かどうか判定
        if (type1 == TYPE_PLANET)
        {
            energy *= 5;
        }
        if (type2 == TYPE_PLANET)
        {
            energy *= 5;
        }
        return energy;
    }

    vector<int> djikstra(int i, int j) {

       	// 二点間の最短距離
        // vector<vector<ll>> dij(N+M);

        // 経路復元用　1つ前にいた頂点を保存
        vector<int> prev_points(N+M,-1);


        // int k = 0;
        // for(int k=0; k<N+M; k++) {
            vector<ll> cur(N+M,INF);
            vector<bool> kakutei(N+M+1,false);
            priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> Q;

            int start = i;
            cur[start] = 0;
            Q.push(make_pair(cur[start],start));

            while(!Q.empty()) {
                auto[d, pos] = Q.top();
                Q.pop();

                if(kakutei[pos] == true) continue;

                kakutei[pos] = true;
                for(int next=0; next<N+M; next++) {
                    int cost = calc_energy(pos,next);
                    if(cur[next] > cur[pos]+cost) {
                        // 1つ前の点を保存
                        prev_points[next] = pos;
                        // 値を更新
                        cur[next] = cur[pos]+cost;
                        Q.push(make_pair(cur[next],next));
                    }
                }
            }
            // dij[i] = cur;
        // }
        // debug(dij);
        // debug(cur);
        // debug(prev_points);

        // 経路復元
        // ゴールからたどっていく
        int v = j;
        vector<int> path;

        while(v != i) {
            path.push_back(v);
            v = prev_points[v];
        }
        reverse(path.begin(),path.end());

        return path;
    }

};



int main() {

    int n,m;
    cin >> n >> m;
    // vector<int> a(n),b(n);
    vector<Pos> points;
    for(int i=0; i<n; i++) {
        int a,b;
        cin >> a >> b;
        points.emplace_back(Pos(a,b,TYPE_PLANET));
    }
    debug(n,m,points);

    Solver solver(n,m,points);
    solver.solve();

	return 0;
}