#include using namespace std; #include using namespace atcoder; using ll=long long; using Graph=vector>; #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 &path, vector> &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(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 a(N), b(N); for(int i=0;i>a[i]>>b[i]; } start_t=clock(); int alpha = 5; vector x={800, 800, 500, 200, 200, 200, 500, 800}; vector y={500, 800, 800, 800, 500, 200, 200, 200}; vector> dist(N+M,vector(N+M,INF)); vector> nextNode(N+M,vector(N+M)); for(int i=0;i path; for(int i=0;i<=N;i++){ path.push_back(i%N); } int S=0; for(int i=0;i ans; ans.push_back(path[0]); for(int i=0;i pathCnt(M,0); for(int i=0;i=N){ int v=ans[i+1]-N; int u=ans[i]; pathCnt[v]++; x[v]+=a[u]; y[v]+=b[u]; } else if(ans[i]>=N&&ans[i+1]0){ x[i]/=pathCnt[i]; y[i]/=pathCnt[i]; } } // 出力 for(int i=0;i