记录编号	86351	评测结果	AAAAA
题目名称	奶牛运输	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.010 s
提交时间	2014-01-25 09:41:19	内存使用	0.55 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iomanip>
#include<deque>
using namespace std;
//注释部分包含了输出答案需要的代码
const int SIZEN=10;
//下标从0开始
int N=7;//农场个数
int dis[SIZEN][SIZEN]={
{00,56,43,71,35,41,36},//A
{56,00,54,58,36,79,31},//B
{43,54,00,30,20,31,58},//C
{71,58,30,00,38,59,75},//D
{35,36,20,38,00,44,67},//E
{41,79,31,59,44,00,72},//F
{36,31,58,75,67,72,00} //G
};
void floyd(void){
	for(int k=0;k<N;k++){
		for(int i=0;i<N;i++){
			for(int j=0;j<N;j++){
				dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
			}
		}
	}
}
const int SIZES=4096,SIZEM=12,INF=0x7fffffff;
int M;//M是任务个数
int ms1[SIZEM]={0},ms2[SIZEM]={0};
int f[SIZES][SIZEM]={0};
bool vis[SIZES][SIZEM]={0};
//int father[SIZES][SIZEM]={0};
int getdig(int x,int k){
	return (x>>k)&1;
}
int changedig(int x,int k,int t){
	x&=(~(1<<k));
	return x|(t<<k);
}
void printdig(int x){//调试接口,打印x的二进制位
	for(int i=0;i<M;i++) cout<<getdig(x,i);
}
int DP(int state,int x){//状态为state,最后一个任务是x
	if(vis[state][x]) return f[state][x];
	vis[state][x]=true;
	f[state][x]=INF;
	for(int i=0;i<M;i++){//倒数第二个任务是i
		if(i==x) continue;
		if(!getdig(state,i)) continue;//任务集里面没有这个任务
		int tps=changedig(state,x,0);//少了一个任务x
		int nowdis=DP(tps,i);//状态变成tps,最后一个任务是i
		nowdis+=dis[ms2[i]][ms1[x]];//从i的终点到x的起点
		nowdis+=dis[ms1[x]][ms2[x]];//这个任务需要跑的距离
		nowdis-=dis[ms2[i]][0];nowdis+=dis[ms2[x]][0];//"返回"的路程从i的终点~A变为x的终点~A
		if(nowdis<f[state][x]){
			f[state][x]=nowdis;
			//father[state][x]=i;
		}
	}
	return f[state][x];
}
void prepare(){//DP的预处理
	for(int i=0;i<M;i++){
		int nowst=(1<<i);
		vis[nowst][i]=true;
		f[nowst][i]=dis[0][ms1[i]]+dis[ms1[i]][ms2[i]]+dis[ms2[i]][0];//只执行一个任务
	}
}
void work(void){
	int endst=(1<<M)-1;//所有任务均被执行
	int best=INF,last;
	for(int i=0;i<M;i++){
		if(DP(endst,i)<best){
			best=f[endst][i];
			//last=i;
		}
	}
	cout<<best<<endl;
	/*deque<int> ans;
	for(int i=0;i<M;i++){
		ans.push_front(last);
		int temp=last;
		last=father[endst][last];
		endst=changedig(endst,temp,0);
	}
	ans.push_front(M);//从1出发
	ms2[M]=0;
	cout<<'A'<<" ";
	for(int i=1;i<=M;i++){
		if(ms1[ans[i]]!=ms2[ans[i-1]]) cout<<char(ms1[ans[i]]+'A')<<" ";
		cout<<char(ms2[ans[i]]+'A')<<" ";
	}
	if(ms2[ans[M]]!=0) cout<<'A'<<" ";*/
}
void read(void){
	cin>>M;
	char ch1,ch2;
	for(int i=0;i<M;i++){
		cin>>ch1>>ch2;
		ms1[i]=ch1-'A';
		ms2[i]=ch2-'A';
	}
}
int main(){
	freopen("cowtrans.in","r",stdin);
	freopen("cowtrans.out","w",stdout);
	//floyd();
	read();
	prepare();
	work();
	return 0;
}