結果

問題 No.5007 Steiner Space Travel
ユーザー tmikadatmikada
提出日時 2023-04-29 18:00:24
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 16 ms / 1,000 ms
コード長 6,737 bytes
コンパイル時間 2,642 ms
コンパイル使用メモリ 222,000 KB
実行使用メモリ 4,372 KB
スコア 6,187,502
最終ジャッジ日時 2023-04-29 18:00:31
合計ジャッジ時間 5,077 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge14
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 15 ms
4,368 KB
testcase_01 AC 15 ms
4,368 KB
testcase_02 AC 13 ms
4,372 KB
testcase_03 AC 16 ms
4,368 KB
testcase_04 AC 15 ms
4,368 KB
testcase_05 AC 13 ms
4,372 KB
testcase_06 AC 15 ms
4,368 KB
testcase_07 AC 15 ms
4,368 KB
testcase_08 AC 15 ms
4,368 KB
testcase_09 AC 15 ms
4,368 KB
testcase_10 AC 15 ms
4,368 KB
testcase_11 AC 14 ms
4,368 KB
testcase_12 AC 14 ms
4,372 KB
testcase_13 AC 14 ms
4,368 KB
testcase_14 AC 14 ms
4,372 KB
testcase_15 AC 16 ms
4,372 KB
testcase_16 AC 14 ms
4,368 KB
testcase_17 AC 15 ms
4,372 KB
testcase_18 AC 15 ms
4,368 KB
testcase_19 AC 14 ms
4,372 KB
testcase_20 AC 14 ms
4,368 KB
testcase_21 AC 15 ms
4,368 KB
testcase_22 AC 15 ms
4,372 KB
testcase_23 AC 16 ms
4,372 KB
testcase_24 AC 15 ms
4,372 KB
testcase_25 AC 14 ms
4,368 KB
testcase_26 AC 15 ms
4,372 KB
testcase_27 AC 14 ms
4,372 KB
testcase_28 AC 14 ms
4,372 KB
testcase_29 AC 15 ms
4,368 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

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