2117-Connect Line Segments

問題概要

n(<=14)個の線分が与えられる．
これらの線分全てを通るように折れ線の一筆書を構築する(詳しくは問題文の図を参照)
最短の長さを求めよ．

解法

現在使った線分と現在居る点をもとにビットDP(メモ化再帰)する．
計算量は2^n*n^2ぐらい

実装(C++)

#include <iostream>
#include <algorithm>
#include <complex>
#include <vector>
#include <cstdio>
#include <iomanip>
using namespace std;
const double EPS=1e-7;
const double INF=1e10;

typedef complex<double> Point;
inline double cross(const Point &a,const Point &b){return imag(conj(a)*b);}
inline double dot(const Point &a,const Point &b){return real(conj(a)*b);}
inline double atan(const Point &a){return atan2(imag(a),real(a));}
namespace std{
	bool operator<(const Point &a,const Point &b){return real(a)==real(b)?imag(a)<imag(b):real(a)<real(b);}
	Point operator*(const Point &a,const double &b){return Point(real(a)*b,imag(a)*b);}
}
struct Line:vector<Point>{
	Line(double x1=0,double y1=0,double x2=0,double y2=0){
		(*this).push_back(Point(x1,y1));
		(*this).push_back(Point(x2,y2));
	}
	Line(Point a,Point b){
		(*this).push_back(a);(*this).push_back(b);
	}
	Point vector(){
		return at(1)-at(0);
	}
};
inline double abs(const Line &a){
	return abs(a[1]-a[0]);
}
struct Circle{
	Circle(Point center,double radius):c(center),r(radius){};
	Circle(double x=0,double y=0,double r=0){(*this)=Circle(Point(x,y),r);}
	Point c;double r;
};
typedef vector<Point> Polygon;
Line getside(const Polygon& p,int no){
	return Line(p[no],p[(no+1)%p.size()]);
}
#define TYPE(now) [now/2][now%2]
Line pts[16];
double dp[1<<14][28];
int n;
double solve(int bit,int now){
	if(bit==(1<<n)-1)return  0;
	double &res=dp[bit][now];
	if(res==-1){
		res=1e9;
		for(int i=0;i<n;i++){
			if((bit>>i)&1)continue;
			res=min(res,solve(bit|(1<<i),i*2)+abs(pts TYPE(now)-pts[i][1]));
			res=min(res,solve(bit|(1<<i),i*2+1)+abs(pts TYPE(now)-pts[i][0]));
		}
	}
	return res;
}
int main() {
	int T=1;
	for(;cin>>n;){
		if(n==0)break;
		for(int i=0;i<n;i++)for(int j=0;j<2;j++)cin>>pts[i][j].real()>>pts[i][j].imag();
		for(int i=0;i<(1<<n);i++)for(int j=0;j<n*2;j++)dp[i][j]=-1;
		double ans=1e9;
		double pans=0;
		for(int i=0;i<n;i++)pans+=abs(pts[i]);
		for(int i=0;i<2*n;i++){
			ans=min(ans,solve(1<<(i/2),i));
		}
		printf("Case %d: %.5f\n",T++,ans+pans);
	}
	return 0;
}