|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 |
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <string> using namespace std; struct HOUSE{ double x,y; }; string str[20]; HOUSE house[20]; double dp[(1<<16)-1]; double d[20][20]; int finalstate; int n; double _min(double a,double b) { return a<b?a:b; } double DP(int state) { if(state==finalstate) return 0; if(dp[state]!=-1) return dp[state]; int rest_state = finalstate-state; double val=(1<<20); for(int i=0;i<2*n;i++) { if(rest_state&(1<<i)) { for(int j=i+1;j<2*n;j++) { if(rest_state&(1<<j)) { val = _min(val,d[i][j]+DP(state|(1<<i)|(1<<j) )); } } } } return dp[state]=val; } int main() { int kase=1; while(scanf("%d",&n),n) { for(int i=0;i<(1<<2*n);i++) dp[i]=-1; finalstate=(1<<2*n)-1; for(int i=0;i<20;i++) for(int j=0;j<20;j++) d[i][j]=0; for(int i=0;i<2*n;i++) { cin>>str[i]; scanf("%lf%lf",&house[i].x,&house[i].y); } for(int i=0;i<2*n-1;i++) { for(int j=i+1;j<2*n;j++) { d[i][j] = sqrt( (house[i].x-house[j].x)*(house[i].x-house[j].x) + (house[i].y-house[j].y)*(house[i].y-house[j].y) ); d[j][i] = d[i][j]; } } printf("Case %d: %.2lf\n",kase++,DP(0)); } return 0; } |