結果

問題 No.5007 Steiner Space Travel
ユーザー oshamashamaoshamashama
提出日時 2022-07-30 17:41:22
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 11 ms / 1,000 ms
コード長 4,530 bytes
コンパイル時間 2,098 ms
実行使用メモリ 6,952 KB
スコア 7,466,624
最終ジャッジ日時 2022-07-30 17:41:51
合計ジャッジ時間 4,157 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge11
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;
const long long alpha = 5;
typedef long long ll;
struct solve
{
    ll N, M;
    vector<pair<ll, ll>> planet_coordinate;
    vector<pair<ll, ll>> station_coordinate;
    vector<vector<ll>> m;
    vector<ll> d;
    vector<ll> last;
    solve()
    {
        cin >> N >> 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;
        }
        station_coordinate.at(0) = make_pair(300, 300);
        station_coordinate.at(1) = make_pair(700, 300);
        station_coordinate.at(2) = make_pair(300, 700);
        station_coordinate.at(3) = make_pair(700, 700);
        station_coordinate.at(4) = make_pair(300, 500);
        station_coordinate.at(5) = make_pair(500, 300);
        station_coordinate.at(6) = make_pair(700, 500);
        station_coordinate.at(7) = make_pair(500, 700);
    }

    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();
            }
        }
        used.at(next) = true;
        return next;
    }

    void print_ans()
    {
        queue<int> q;
        q.push(0);
        vector<bool> used(N + M, 0);
        used.at(0) = true;
        int start = 0;
        for (int i = 0; i < N; i++)
        {
            start = get_shortest(start, used, q);
            // cout << start << endl;
        }
        for (int i = 0; i < M; i++)
        {
            cout << station_coordinate.at(i).first << ' ' << station_coordinate.at(i).second << endl;
        }
        cout << q.size() << endl;
        while (q.size())
        {
            int now = q.front();
            // cout << now << endl;
            cout << 1 + now / N
                 << ' '
                 << now % N + 1
                 << endl;
            q.pop();
        }
    }
};

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