はやし屋

競技プログラミングのメモ きたない

AOJ 2117: Connect Line Segments

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2117

一筆書きしろという問題
TSPでやったけど
繋ぎ方が綺麗にかけなくて解答を見た
点線出して最後に繋ぐイメージでやった

#include<iostream>
#include<string>
#include<bitset>
#include<cctype>
#include<cstdlib>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<vector>
#include<cstring>
#include<sstream>
#include<iterator>
#include<algorithm>
#include<complex>
using namespace std;
  
// structure
typedef long long ll;
typedef pair < int , int > Pi;
typedef pair < int , Pi > Pii;
  
#define INF (1 << 28)
#define SQR(x) ((x)*(x))
  
//repetition
#define reps(i,j,n) for(int i = j ; i < n ; ++i)
#define rep(i, n) reps(i,0,n)
#define EACH(i,c) for(__typeof((c).begin()) ;i=(c).begin(); i!=(c).end(); ++i)
  
// containar
#define ALL(v) (v).begin(), (v).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define sz(z) (int)((z).size())
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define UNQ(s) {sort(ALL(s));(s).erase(unique(ALL(s)),(s).end());}
#define fr first
#define sc second
  
// debug
#define dump(x) cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
  
/*
// < v > ^
const int dx[] = {-1,0,1,0,0};
const int dy[] = {0,1,0,-1,0};
   
// convert
string itos(int v) {stringstream ss;ss<<v;return ss.str();}
int stoi(string s) {int v; stringstream ss(s);ss>>v;return v;}
   
*/
  
// PROG START
  
  
typedef pair < double , double > Pd;
typedef pair < Pd , Pd > P;
  
P data[22];
  
int n;
double d[15][2][15][2];
  
double calc(Pd a , Pd b){
  double ret = sqrt(SQR(a.fr-b.fr)+SQR(a.sc-b.sc));
  // printf("%lf %lf %lf\n",a.fr-b.fr,a.sc-b.sc,ret);
  return ret;
}
  
double dp[15][2][1<<15];
  
double getMin(int a, int b, int bit){
  if(bit + 1 == 1 << n)return 0;
  if(dp[a][b][bit] != -1)return dp[a][b][bit];
  double res = 1e15;
  
  rep(i,n)if(!((bit >> i) & 1))
    rep(ch,2)
      res = min(res,getMin(i,ch,bit|1<<i)+d[a][b^1][i][ch]);    
  
  return dp[a][b][bit] = res;
}
  
int main(){
  for(int Case = 1 ; scanf("%d",&n)&&n ;){
    rep(i,n)scanf("%lf%lf%lf%lf",&data[i].fr.fr,&data[i].fr.sc,&data[i].sc.fr,&data[i].sc.sc);
    rep(i,n){
      rep(j,n){
	d[i][0][j][0] = calc(data[i].fr,data[j].fr);
	d[i][0][j][1] = calc(data[i].fr,data[j].sc);
	d[i][1][j][0] = calc(data[i].sc,data[j].fr);
	d[i][1][j][1] = calc(data[i].sc,data[j].sc);
      }
    }
    rep(i,15)rep(j,2)rep(u,1<<15)dp[i][j][u] = -1;
    double res = 1e15;
    rep(i,n)rep(j,2)res = min(res,getMin(i,j,0));
    rep(i,n)res += d[i][0][i][1];
    printf("Case %d: %f\n",Case++,res);
  }
  
}