結果
問題 | No.5007 Steiner Space Travel |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
#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 500random_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);// ansfor(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';}}}