Lib/TSP(巡回セールスマン問題)
二次元平面
code:cpp
struct point {
double x, y;
};
double dist(point a,point b){
return sqrtl(powl(abs(a.x-b.x),2)+powl(abs(a.y-b.y),2));
}
signed main(void){
ll n;
cin >> n;
vector<point> v(n);
rep(i,n) cin >> vi.x >> vi.y; vector<vector<double>> dp(1 << n,vector<double>(n,inf));
rep1(i,1 << n){
rep1(j,n){
if(!(i & (1 << j)) || !(i&1)){
continue;
}else{
ll t = i - (1 << j);
double next = inf;
rep(k,n){
chmin(next,dptk+dist(vk,vj)); //print(i,j,k,dptk,dist(vk,vj)); }
// print(i,j,next);
}
}
}
double ans = inf;
rep1(i,n){
chmin(ans,a + dist(v0,vi)); // print(i,a);
}
cout << setprecision(12) << ans << endl;
}
O(N^2*2^N) たぶん
validation: