結果

問題 No.5007 Steiner Space Travel
ユーザー rinrion
提出日時 2022-08-03 17:26:21
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 3 ms / 1,000 ms
コード長 1,235 bytes
コンパイル時間 2,314 ms
実行使用メモリ 3,820 KB
スコア 4,521,707
最終ジャッジ日時 2022-08-03 17:26:25
合計ジャッジ時間 3,857 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge13
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include<chrono> //時間計測
using namespace std;

double eu2(double x1,double y1, double x2, double y2){
	double s= sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
	return s*s;
}


int main(){
	int n,m;
	cin>>n>>m;
	
	vector<int>a(n),b(n);
	for(int i=0; i<n; i++){
		cin>>a[i]>>b[i];
	}

	vector<vector<tuple<double,int>>>dis_i(100,vector<tuple<double,int>>());
	
	for(int i=0;i<100;i++){
		for(int j=0;j<100;j++){
			if(i!=j){
				dis_i[i].push_back(make_tuple(eu2(a[i],b[i],a[j],b[j]),j));
			}
		}
		sort(dis_i[i].begin(),dis_i[i].end());
	}


	vector<pair<int,int>>tr;
	bitset<100>visited;
	int now=0;
	visited[now]=true;
	tr.emplace_back(1,1);

	while(true){
		bool jdg=false;
		for(int i=0; i<100; i++){
			if(!visited[get<1>(dis_i[now][i])]){
				int next=get<1>(dis_i[now][i]);
				tr.emplace_back(1,next+1);
				now=next;
				visited[next]=true;
				jdg=true;
				break;
			}
		}
		if(!jdg)break;
	}

	tr.emplace_back(1,1);

	vector<pair<int,int>>cd(8);//ロボてりーの位置　×8
		for(int i=0; i<8; i++){
		get<0>(cd[i])=0;
		get<1>(cd[i])=0;
	}
	
		for(auto x:cd){
		cout<<get<0>(x)<<" "<<get<1>(x)<<endl;
	}
	cout<<tr.size()<<endl;
	for(auto x:tr){
		cout<<get<0>(x)<<" "<<get<1>(x)<<endl;
	}

}
0