結果

問題 No.5007 Steiner Space Travel
コンテスト
ユーザー yas_yasyu
提出日時 2023-04-26 03:04:00
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 844 ms / 1,000 ms
コード長 3,820 bytes
コンパイル時間 4,937 ms
コンパイル使用メモリ 275,556 KB
実行使用メモリ 4,372 KB
スコア 5,456,211
最終ジャッジ日時 2023-04-26 03:04:36
合計ジャッジ時間 31,359 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge12
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <atcoder/all>
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

const long double EPS = 1e-10;
const long long INF = 1e18;
const long double PI = acos(-1.0L);

const double TIME_LIMIT = 0.95;

struct Planet {
    int a;
    int b;
    int idx;
    Planet(int _a, int _b, int _idx) {
        a = _a;
        b = _b;
        idx = _idx;
    }
    Planet(const Planet &old) {
        a = old.a;
        b = old.b;
        idx = old.idx;
    }
};

struct Station {
    int a;
    int b;
    int idx;
    Station(int _a, int _b, int _idx) {
        a = _a;
        b = _b;
        idx = _idx;
    }
    Station(const Station &old) {
        a = old.a;
        b = old.b;
        idx = old.idx;
    }
};

int N, M;
vector<Planet> planet;
vector<Station> station;

const int A = 5;
/*Target to minimize */
ll energy = 0;
Planet startPlanet(0,0,0);

vector<pair<int, int>> ans;

vector<vector<ll>> FloydWarshall(vector<vector<ll>>& distances)
{
	const size_t v = distances.size();

	for (size_t i = 0; i < v; ++i)
	{
		for (size_t frm = 0; frm < v; ++frm)
		{
			for (size_t to = 0; to < v; ++to)
			{
				if ((distances[frm][i] < INF) && (distances[i][to] < INF))
				{
					distances[frm][to] = min(distances[frm][to], (distances[frm][i] + distances[i][to]));
				}
			}
		}
	}

	return distances;
}

void Input() {
    cin >> N >> M;
    for(int i = 0; i < N; i++) {
        int a, b;
        cin >> a >> b;
        planet.push_back(Planet(a, b, i + 1));
    }
    return;
}

void OutputStation() {
    for(int i = 0; i < M; i++) {
        cout << station[i].a << " " << station[i].b << endl;
    }
    return;
}

void OutputWayPoint(pair<int, int> wayPoint) { cout << wayPoint.first << " " << wayPoint.second+1 << endl; }

void OutputRoute() {
    int V = (int)ans.size();
    cout << V << endl;

    for(int i = 0; i < V; i++) {
        OutputWayPoint(ans[i]);
    }

    return;
}

ll Distance(Planet pa, Planet pb)
{
	ll a = (pa.a - pb.a);
	ll b = (pa.b - pb.b);
	return a*a + b*b;
}

void Pick(int &a, int &b)
{
	while(true)
	{
		a = rand()%ans.size();
		b = rand()%ans.size();
		if(a > b) swap(a, b);
		if (a+1 == b || b == N-1)
		{
			continue;
		}
		return;
	}
}

void EdgeSwap(int a, int b)
{
	a++;
	while(a < b)
	{
		swap(ans[a], ans[b]);
		a++;
		b--;
	}
}

void TwoOpt(vector<vector<ll>> distances, int cnt)
{
	do
	{
		int a, b;
		Pick(a, b);
		int na, nb;
		na = (a+1)%(ans.size());
		nb = (b+1)%(ans.size());

		ll beforeDist = distances[ans[a].second][ans[na].second] + distances[ans[b].second][ans[nb].second];
		ll afterDist = distances[ans[a].second][ans[b].second] + distances[ans[na].second][ans[nb].second];
		if (beforeDist > afterDist)
		{
			EdgeSwap(a, b);
		}
	} while (--cnt);
}

void solve() {
    for(int i = 1; i < M + 1; i++) {
        Station s(0, 0, i);
        station.push_back(s);
    }

	vector<vector<ll>> distances(N, vector(N, INF));
	startPlanet = planet[0];
	for(int i = 0; i < N; i++)
	{
		for(int j = 0; j < N; j++)
		{
			distances[i][j] = Distance(planet[i], planet[j]);
		}
	}
	FloydWarshall(distances);

	set<int> bef;
	int frmIdx = 0;
	ans.push_back(pair<int, int>(1, 0));
	for(int i = 0; i < N; i++)
	{
		ll minDist = INF;
		int nxtIdx = -1;
		bef.insert(frmIdx + 1);


		for(int toIdx = 0; toIdx < N; toIdx++)
		{
			if(bef.find(toIdx+1) != bef.end())
			{
				continue;
			}
			if(minDist > distances[frmIdx][toIdx])
			{
				minDist = distances[frmIdx][toIdx];
				nxtIdx = toIdx;
			}
		}
		if(nxtIdx == -1) continue;
		ans.push_back(pair<int, int>(1, nxtIdx));
		frmIdx = nxtIdx;
	}
	ans.push_back(pair<int, int>(1, 0));

	TwoOpt(distances, 10000000);

    return;
}

int main() {
	srand(time(NULL));
    Input();

    solve();

    OutputStation();
    OutputRoute();

    return 0;
}
0