結果

問題 No.5007 Steiner Space Travel
ユーザー monnu
提出日時 2022-07-30 15:24:35
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 835 ms / 1,000 ms
コード長 2,897 bytes
コンパイル時間 3,545 ms
実行使用メモリ 5,160 KB
スコア 2,656,168
最終ジャッジ日時 2022-07-30 15:25:06
合計ジャッジ時間 30,949 ms
ジャッジサーバーID
(参考情報)
judge15 / judge10
純コード判定しない問題か言語
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
using ll=long long;
using Graph=vector<vector<int>>;
#define INF 1000000000
#define MOD 998244353
#define MAX 500
random_device seed;
mt19937 engine(seed());
uniform_real_distribution<> uniform_real_dist(0.0,1.0);
clock_t start_t,end_t;
double elapsed_time;
//
double time_limit=0.8;
//
double T0=1e8;
//
double T1=1e2;
void two_opt(vector<int> &path, vector<vector<int>> &dist, int &S)
{
int n=path.size();
end_t=clock();
elapsed_time=(double)(end_t-start_t)/CLOCKS_PER_SEC;
// path[1, n-2]
while (elapsed_time <= time_limit) {
double T=pow(T0,1.0-elapsed_time/time_limit)*pow(T1,elapsed_time/time_limit);
int left = rand()%(n-2) + 1;
int right = rand()%(n-2) + 1;
if (left == right) {
continue;
}
if (right < left) {
swap(left, right);
}
int deltaS = 0.0;
deltaS -= dist[path[left-1]][path[left]] + dist[path[right]][path[right+1]];
deltaS += dist[path[left-1]][path[right]] + dist[path[left]][path[right+1]];
int diff = round(1.0e9/(1.0e3 + sqrt(S+deltaS))) - round(1.0e9/(1.0e3 + sqrt(S)));
//
double p=min<double>(1.0,exp(diff/T));
if(uniform_real_dist(engine)<=p){
S += deltaS;
reverse(path.begin() + left, path.begin() + (right+1));
}
end_t=clock();
elapsed_time=(double)(end_t-start_t)/CLOCKS_PER_SEC;
}
}
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];
}
start_t=clock();
int alpha = 5;
vector<int> x={800, 800, 500, 200, 200, 200, 500, 800};
vector<int> y={500, 800, 800, 800, 500, 200, 200, 200};
vector<vector<int>> dist(N+M,vector<int>(N+M,INF));
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
dist[i][j] = alpha*alpha * ((a[i]-a[j])*(a[i]-a[j]) + (b[i]-b[j])*(b[i]-b[j]));
}
}
for(int i=0;i<N;i++){
for(int j=0;j<M;j++){
dist[i][M+j] = alpha * ((a[i]-x[j])*(a[i]-x[j]) + (b[i]-y[j])*(b[i]-y[j]));
dist[M+j][i] = alpha * ((a[i]-x[j])*(a[i]-x[j]) + (b[i]-y[j])*(b[i]-y[j]));
}
}
for(int i=0;i<M;i++){
for(int j=0;j<M;j++){
dist[M+i][M+j] = (x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]);
}
}
for(int k=0;k<N+M;k++){
for(int i=0;i<N+M;i++){
for(int j=0;j<N+M;j++){
dist[i][j]=min(dist[i][j], dist[i][k]+dist[k][j]);
}
}
}
vector<int> path;
for(int i=0;i<=N;i++){
path.push_back(i%N);
}
int S=0;
for(int i=0;i<N;i++){
S+=dist[path[i]][path[i+1]];
}
two_opt(path, dist, S);
// ans
for(int i=0;i<M;i++){
cout<<x[i]<<" "<<y[i]<<'\n';
}
cout<<path.size()<<'\n';
for(int i=0;i<path.size();i++){
if(path[i]<N){
cout<<"1 "<<path[i]+1<<'\n';
}else{
cout<<"2 "<<(path[i]-N)+1<<'\n';
}
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0