結果

問題 No.5007 Steiner Space Travel
ユーザー yunix
提出日時 2022-07-30 15:12:49
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 287 ms / 1,000 ms
コード長 8,601 bytes
コンパイル時間 1,752 ms
実行使用メモリ 6,956 KB
スコア 8,237,894
最終ジャッジ日時 2022-07-30 15:13:20
合計ジャッジ時間 12,377 ms
ジャッジサーバーID
(参考情報)
judge11 / judge10
純コード判定しない問題か言語
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

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

#include <iostream>
#include <string>
#include <vector>
#include <tuple>
#include <chrono>
#include <algorithm>
#include <random>
#include <map>
#include <set>
#include <queue>
#include <random>
#include <chrono>
#include <cmath>
#include <climits>
using namespace std;
using vec_int = vector<int>;
using P = pair<int, int>;
using T = tuple<int, int, int>;
using ll = long long;
// using PQ = priority_queue<pair<float, int>, vector<pair<float,int>>, greater<pair<float, int>>>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
float initial_T = 100000;
float final_T = 20;
float TIME_LIMIT = 1000;
float TIME_LIMIT_STATION = 200;
int RAND_ARR_LEN = 100000;
int RAND_RANGE = 1000000000;
int N_VERTICAL = 10;
vector<P> DIRS = {make_pair(0, -1), make_pair(-1, 0), make_pair(0, 1), make_pair(1, 0)};
bool is_in(int x, int y, int N)
{
if (x >= 0 && x < N && y >= 0 && y < N)
return true;
return false;
}
// std::mt19937 mt{ std::random_device{}() };
std::mt19937 mt{12345};
std::uniform_int_distribution<int> dist(1, RAND_RANGE);
float get_time(bool init)
{
static std::chrono::system_clock::time_point start;
if (init)
{
start = std::chrono::system_clock::now();
}
std::chrono::system_clock::time_point end = std::chrono::system_clock::now();
return std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count(); //
}
class Rand
{
private:
int count = 0;
vec_int rand_arr;
public:
Rand(){
rep(i, RAND_ARR_LEN){
rand_arr.push_back(dist(mt));
}
}
;
int get();
int get_rand(int from, int to);
float get_float();
}
;
int Rand::get()
{
int num = rand_arr.at(count);
count += 1;
count %= RAND_ARR_LEN;
return num;
}
int Rand::get_rand(int from, int to)
{
int diff = to - from;
int num = get() % diff;
return num + from;
}
float Rand::get_float()
{
// 0~1
return (float)get() / (float)RAND_RANGE;
}
Rand ro;
float current_tmp_station(float current_time)
{
return final_T + (initial_T - final_T) * (TIME_LIMIT_STATION - current_time) / TIME_LIMIT_STATION;
}
bool is_valid_transition_station(int diff, float current_time)
{
float t = current_tmp_station(current_time);
float rand = ro.get_float();
// cerr<<"tmperature"<<t<<" "<<diff<<endl;
return rand < exp(((float)diff) / t);
}
int N, M;
vec_int a, b;
int alpha=5;
int sq_alpha=25;
class SpaceStation{
public:
int x;
int y;
SpaceStation(){
x=0;
y=0;
};
SpaceStation(int xpos, int ypos){
x=xpos;
y=ypos;
};
int square_distance(int x2, int y2){
return (x2-x)*(x2-x) + (y2-y)*(y2-y);
};
void set_pos(int xpos, int ypos){
x=xpos;
y=ypos;
};
void random_move(){
int dx = ro.get_rand(-20, 21);
int dy = ro.get_rand(-20, 21);
int x2 = x+dx;
int y2 = y+dy;
x2 = max(0, x2);
y2 = max(0, y2);
x2 = min(1000, x2);
y2 = min(1000, y2);
x=x2;
y=y2;
}
};
int tot_distance(vector<SpaceStation> &stations){
int result = 0;
rep(i, N){
int tmp_dist = INT_MAX;
rep(j, M){
tmp_dist = min(tmp_dist, stations.at(j).square_distance(a.at(i), b.at(i)));
}
result += tmp_dist;
}
return result;
}
void cout_ans(vector<P> &ans){
cout<<ans.size()<<endl;
rep(i, ans.size()){
cout<<ans.at(i).first<<" "<<ans.at(i).second+1<<endl;
}
}
int sq_dist_between_cities(int i, int j){
int result = 0;
result += (a.at(i)-a.at(j))*(a.at(i)-a.at(j));
result += (b.at(i)-b.at(j))*(b.at(i)-b.at(j));
return result;
}
vector<vector<pair<int, vector<P>>>> make_dist_map(vector<SpaceStation> &stations){
vector<vector<pair<int, vector<P>>>> result(N, vector<pair<int, vector<P>>>(N+M));
for(int i=0;i<N;i++){
// istart
vector<int> visited(N+M, 0);
vector<int> prev_city(N, -1);
priority_queue<T, vector<T>, greater<T>> pq;
pq.emplace(0, i, -1);
while(!pq.empty()){
int dist, pos, prev; tie(dist, pos, prev) = pq.top(); pq.pop();
if(visited.at(pos)==1)continue;
if(pos<N){
//
visited.at(pos) = 1;
vector<P> route;
if(prev!=-1){
route = result.at(i).at(prev).second;
}
route.push_back(make_pair(1, pos));
result.at(i).at(pos) = make_pair(dist, route);
for(int j=0;j<N;j++){
//
if(visited.at(j)==1)continue;
int add_dist = sq_dist_between_cities(pos, j) * sq_alpha;
pq.emplace(dist+add_dist, j, pos);
}
for(int j=0;j<M;j++){
//
if(visited.at(j)==1)continue;
int add_dist = stations.at(j).square_distance(a.at(pos), b.at(pos)) * alpha;
pq.emplace(dist+add_dist, j+N, pos);
}
}else{
//
visited.at(pos) = 1;
vector<P> route;
if(prev!=-1){
route = result.at(i).at(prev).second;
}
route.push_back(make_pair(2, pos-N));
result.at(i).at(pos) = make_pair(dist, route);
for(int j=0;j<N;j++){
//
if(visited.at(j)==1)continue;
int add_dist = stations.at(pos-N).square_distance(a.at(j), b.at(j))*alpha;
pq.emplace(dist+add_dist, j, pos);
}
for(int j=0;j<M;j++){
//
if(visited.at(j)==1)continue;
int add_dist = stations.at(pos-N).square_distance(stations.at(j).x, stations.at(j).y);
pq.emplace(dist+add_dist, j+N, pos);
}
}
}
}
return result;
}
void greedy_strategy(vector<P> &ans, vector<SpaceStation> &stations, vector<vector<pair<int, vector<P>>>> &dist_mat){
//
int pos = 0;
ans.push_back(make_pair(1, 0));
vec_int visited(N, 0);
while(true){
visited.at(pos) = true;
int min_dist = INT_MAX;
int next_pos = -1;
for(int i=0;i<N;i++){
if(visited.at(i)==1)continue;
int tmp_dist = dist_mat.at(pos).at(i).first;
if(min_dist>tmp_dist){
min_dist = tmp_dist;
next_pos = i;
}
}
if(next_pos==-1)break;
for(auto p_pos: dist_mat.at(pos).at(next_pos).second){
ans.push_back(p_pos);
}
pos = next_pos;
}
for(auto p_pos: dist_mat.at(pos).at(0).second){
ans.push_back(p_pos);
}
}
int main(){
get_time(true);
cin>>N>>M;
rep(i, N){
int aa, bb; cin>>aa>>bb;
a.push_back(aa);
b.push_back(bb);
}
vector<SpaceStation> stations(M);
rep(i, M){
stations.at(i) = SpaceStation(ro.get_rand(0, 1001), ro.get_rand(0, 1001));
}
int station_score = tot_distance(stations);
cerr<<"initial tot square distance:"<<station_score<<endl;
while(true){
float ct = get_time(false);
if(ct>TIME_LIMIT_STATION)break;
int selected_station = ro.get_rand(0, M);
int old_x = stations.at(selected_station).x;
int old_y = stations.at(selected_station).y;
stations.at(selected_station).random_move();
int new_score = tot_distance(stations);
int diff = new_score-station_score;
if(is_valid_transition_station(-1*diff, ct)){//
station_score = new_score;
}else{
stations.at(selected_station).set_pos(old_x, old_y);
}
}
vector<vector<pair<int, vector<P>>>> dist = make_dist_map(stations);
/*
rep(i, N){
sort(dist.at(i).begin(), dist.at(i).end());
}
*/
rep(i, M){
cout<<stations.at(i).x<<" "<<stations.at(i).y<<endl;
}
vector<P> ans;
greedy_strategy(ans, stations, dist);
cout_ans(ans);
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0