记录编号	434360	评测结果	AAAAAAAAAA
题目名称	售货员的难题	最终得分	100
用户昵称	OI永别	是否通过	通过
代码语言	C++	运行时间	0.012 s
提交时间	2017-08-07 19:46:35	内存使用	0.31 MiB

#include<bits/stdc++.h>
using namespace std;
// const
const int INF = 0x3f3f3f3f;
#define sqr(x) ((x)*(x))
//define the variable
string file_name;
int type;// type == 1 full martix data, type == 2 EUC_2D data
int s;
int N;//number of nodes
int init_point;
double **dp;//the dynamic optimize function
double **dis;//distance between two city
// the struct of vertex
double ans;
struct vertex{
	double x, y;// coord of vertex
	int id;// the id of vertex 
	
	int input(FILE *fp){
		return fscanf(fp, "%d %lf %lf", &id, &x, &y);
	}
	
}*node;

double EUC_2D(const vertex &a, const vertex &b){
	return sqrt(sqr(a.x - b.x) + sqr(a.y - b.y));
} 

void io(){// to input some information
//	cin >> file_name >> type;
	type = 1;
	FILE *fp = fopen("salesman.in", "r");
	fscanf(fp, "%d", &N);
	node = new vertex[N + 5];
	dis = new double*[N + 5];
	if (type == 1){
		for (int i = 0; i < N; i ++){
			dis[i] = new double[N];
			for (int j = 0; j < N; j ++)
				fscanf(fp, "%lf", &dis[i][j]);
		}
	}else{
		for (int i = 0; i < N; i ++){
			node[i].input(fp);
		}
		for (int i = 0; i < N; i ++){
			dis[i] = new double[N];
			for (int j = 0; j < N; j ++)
				dis[i][j] = EUC_2D(node[i], node[j]);
		}
	}
	fclose(fp);
	return;
}


void init(){// initilization

    dp = new double*[(1 << N) + 5];
    for(int i = 0; i < (1 << N); i++){
    	dp[i] = new double[N + 5];
    	for(int j = 0; j < N; j++)
        	dp[i][j] = INF;//initilize the dp function
    }
    ans = INF;
    return;
}

double slove(){
	int M = (1 << N);
	dp[1][0] = 0;
	for (int i = 1; i < M; i ++){
		for (int j = 1; j < N; j ++){
			if (i & (1 << j)) continue;
			if (!(i & 1)) continue;
			for (int k = 0; k < N; k ++){
				if (i & (1 << k)){
					dp[(1 << j) | i][j] = min(dp[(1 << j) | i][j], dp[i][k] + dis[k][j]);
				}
			}
		}
	}
	for (int i = 0; i < N; i ++)
		ans = min(dp[M - 1][i] + dis[i][0], ans);
	return ans;
}

int main(){
	io();
	init();
	FILE *fp = fopen("salesman.out", "w");
	fprintf(fp, "%.0lf\n", slove());
	delete[] dp;
	delete[] node;
	delete[] dis;
	fclose(fp);
	return 0;
}