#783390 (C++14) No.5007 Steiner Space Travel

• 問題: No.5007 Steiner Space Travel
• ユーザー: oshamashama
• 提出日時: 2022-07-30 17:54:09
• 言語: C++14 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 956 ms / 1,000 ms
• コード長: 5,323 bytes
• コンパイル時間: 2,477 ms
• 実行使用メモリ: 6,952 KB
• スコア: 7,722,902
• 最終ジャッジ日時: 2022-07-30 17:55:16
• 合計ジャッジ時間: 32,977 ms
• ジャッジサーバーID （参考情報）: judge9 / judge12

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	935 ms; 4,904 KB
testcase_01	AC	909 ms; 4,908 KB
testcase_02	AC	921 ms; 4,908 KB
testcase_03	AC	931 ms; 4,900 KB
testcase_04	AC	915 ms; 6,952 KB
testcase_05	AC	914 ms; 4,900 KB
testcase_06	AC	909 ms; 4,904 KB
testcase_07	AC	927 ms; 4,900 KB
testcase_08	AC	910 ms; 3,608 KB
testcase_09	AC	932 ms; 4,904 KB
testcase_10	AC	906 ms; 4,900 KB
testcase_11	AC	910 ms; 4,900 KB
testcase_12	AC	908 ms; 6,952 KB
testcase_13	AC	934 ms; 6,952 KB
testcase_14	AC	906 ms; 4,904 KB
testcase_15	AC	937 ms; 6,948 KB
testcase_16	AC	915 ms; 6,952 KB
testcase_17	AC	904 ms; 4,900 KB
testcase_18	AC	906 ms; 6,948 KB
testcase_19	AC	936 ms; 6,952 KB
testcase_20	AC	911 ms; 4,904 KB
testcase_21	AC	911 ms; 4,908 KB
testcase_22	AC	934 ms; 4,904 KB
testcase_23	AC	918 ms; 4,900 KB
testcase_24	AC	915 ms; 6,948 KB
testcase_25	AC	956 ms; 6,952 KB
testcase_26	AC	910 ms; 4,900 KB
testcase_27	AC	908 ms; 4,904 KB
testcase_28	AC	912 ms; 4,900 KB
testcase_29	AC	936 ms; 6,952 KB

ソースコード

#include <bits/stdc++.h>

using namespace std;
const long long alpha = 5;
typedef long long ll;
struct solve
{
    ll N, M;
    ll best_score;
    vector<pair<ll, ll>> planet_coordinate;
    vector<pair<ll, ll>> station_coordinate;
    vector<pair<ll, ll>> best_planet_coordinate;
    vector<pair<ll, ll>> best_station_coordinate;
    vector<vector<ll>> m;
    vector<ll> d;
    vector<ll> last;
    solve()
    {
        cin >> N >> M;
        best_score = 0;
        best_planet_coordinate.resize(N);
        best_station_coordinate.resize(M);
        planet_coordinate.resize(N);
        station_coordinate.resize(M);
        m.resize(N + M, vector<ll>(N + M));
        d.resize(N + M, 1e18);
        last.resize(N + M, 1e18);
        for (int i = 0; i < N; i++)
        {
            cin >> planet_coordinate.at(i).first >> planet_coordinate.at(i).second;
        }
    }

    ll dist(pair<ll, ll> a, pair<ll, ll> b)
    {
        return ((a.first - b.first) * (a.first - b.first) +
                (a.second - b.second) * (a.second - b.second));
    }

    ll distance(int i, int j)
    {
        return dist((i < N ? planet_coordinate.at(i) : station_coordinate.at(i - N)),
                    (j < N ? planet_coordinate.at(j) : station_coordinate.at(j - N))) *
               (i < N ? 5 : 1) *
               (j < N ? 5 : 1);
    }

    ll get_shortest(int &start, vector<bool> &used, queue<int> &q)
    {
        for (int i = 0; i < N + M; i++)
        {
            for (int j = 0; j < N + M; j++)
            {
                m.at(i).at(j) = distance(i, j);
            }
        }
        priority_queue<pair<ll, ll>> pq;
        d.resize(N + M, 1e18);
        pq.push(make_pair(0, start));
        ll Md = 1e18;
        int ind = 0;
        for (int i = 0; i < N + M; i++)
        {
            // cerr << "hoge" << d.at(i) << endl;
            d.at(i) = 1e18;
        }
        d.at(start) = 0;

        while (pq.size())
        {
            int now = pq.top().second;
            pq.pop();
            for (int i = 0; i < N + M; i++)
            {
                int next = i;
                // cerr << "-----" << now << ' ' << next << endl;
                // cerr << d.size() << endl;
                // cerr << m.at(0).size() << endl;
                // cerr << d.at(next) << endl;
                if (d.at(next) > d.at(now) + m.at(now).at(next))
                {
                    d.at(next) = d.at(now) + m.at(now).at(next);
                    last.at(next) = now;
                    // cout << "Md " << endl;
                    if (N <= next)
                    {
                        pq.push(make_pair(d.at(next), next));
                    }
                    else if (Md > d.at(next) &&
                             used.at(next) == false)
                    {
                        // cout << "/* code */" << endl;
                        Md = d.at(next);
                        ind = next;
                    }
                }
            }
        }
        // cout << ind << endl;
        int next = ind;
        if (ind != -1)
        {
            stack<int> s;
            while (ind != start)
            {
                s.push(ind);
                // cerr << "check " << ind << ' ' << last.at(ind) << endl;
                ind = last.at(ind);
            }
            while (s.size())
            {
                q.push(s.top());
                s.pop();
            }
        }
        start = next;
        used.at(start) = true;
        return d.at(start);
    }

    void print_ans()
    {

        std::random_device rd;
        std::default_random_engine eng(rd());
        std::uniform_int_distribution<int> distr(100, 1000);

        ll ccc = 10;
        queue<int> best_q;
        ll time_limit = 900000;

        while (clock() < time_limit)
        {
            for (int i = 0; i < M; i++)
            {
                station_coordinate.at(i) = make_pair(distr(eng), distr(eng));
                // cerr << station_coordinate.at(i).first << ' ' << station_coordinate.at(i).second << endl;
            }
            queue<int> q;
            q.push(0);
            vector<bool> used(N + M, 0);
            used.at(0) = true;
            int start = 0;
            ll sum = 0;
            for (int i = 0; i < N; i++)
            {
                sum += get_shortest(start, used, q);
                // cout << start << endl;
            }
            ll now_score = 1000000000 / (1000 + sqrt(sum));
            cerr << now_score << endl;
            if (now_score > best_score)
            {
                best_q = q;
                best_planet_coordinate = planet_coordinate;
                best_station_coordinate = station_coordinate;
                best_score = now_score;
            }
        }
        for (int i = 0; i < M; i++)
        {
            cout << best_station_coordinate.at(i).first << ' ' << best_station_coordinate.at(i).second << endl;
        }
        cout << best_q.size() << endl;
        while (best_q.size())
        {
            int now = best_q.front();
            // cout << now << endl;
            cout << 1 + now / N
                 << ' '
                 << now % N + 1
                 << endl;
            best_q.pop();
        }
    }
};

int main()
{
    solve s;
    s.print_ans();
    return 0;
}