結果

問題 No.5007 Steiner Space Travel
コンテスト
ユーザー yas_yasyu
提出日時 2023-04-25 05:28:23
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 8 ms / 1,000 ms
コード長 3,419 bytes
コンパイル時間 4,875 ms
コンパイル使用メモリ 274,988 KB
実行使用メモリ 4,376 KB
スコア 4,287,349
最終ジャッジ日時 2023-04-25 05:28:32
合計ジャッジ時間 7,054 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge14
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 30
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: 関数 ‘void solve()’ 内:
main.cpp:166:55: 警告: ‘nxtIdx’ may be used uninitialized [-Wmaybe-uninitialized]
  166 |                 ans.push_back(pair<int, int>(1, nxtIdx+1));
      |                                                 ~~~~~~^~
main.cpp:150:21: 備考: ‘nxtIdx’ はここで定義されています
  150 |                 int nxtIdx;
      |                     ^~~~~~

ソースコード

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 from = 0; from < v; ++from)
		{
			for (size_t to = 0; to < v; ++to)
			{
				if ((distances[from][i] < INF) && (distances[i][to] < INF))
				{
					distances[from][to] = min(distances[from][to], (distances[from][i] + distances[i][to]));
				}
			}
		}
	}

	return distances;
}

bool PlanetComp(const Planet &left, const Planet &right) {
    ll la, lb, ra, rb;
    ll leftDist, rightDist;
    la = left.a;
    lb = left.b;
    leftDist = (la - startPlanet.a) * (la - startPlanet.a) + (lb - startPlanet.b) * (lb - startPlanet.b);
    ra = right.a;
    rb = right.b;
    rightDist = (ra - startPlanet.a) * (ra - startPlanet.a) + (rb - startPlanet.b) * (rb - startPlanet.b);
    return leftDist < rightDist;
};


void Input() {
    cin >> N >> M;
    for(int i = 0; i < N; i++) {
        int a, b;
        cin >> a >> b;
        Planet p(a, b, i + 1);
        planet.push_back(p);
    }
    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 << endl; }

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

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

    return;
}



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++)
		{
			ll a, b;
			a = planet[i].a - planet[j].a;
			b = planet[i].b - planet[j].b;
			distances[i][j] = a*a + b*b;
		}
	}
	FloydWarshall(distances);

	set<int> bef;
	int frmIdx = 0;
	ans.push_back(pair<int, int>(1, 1));
	for(int i = 0; i < N; i++)
	{
		ll minDist = INF;
		int nxtIdx;
		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;
			}
		}
		ans.push_back(pair<int, int>(1, nxtIdx+1));
		frmIdx = nxtIdx;
	}
	ans.push_back(pair<int, int>(1, 1));

    return;
}

int main() {
    Input();

    solve();

    OutputStation();
    OutputRoute();

    return 0;
}
0