a_10496.cpp

UVa ACM 10496 Accepted Code

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>


typedef struct{
	int r;
	int c;
}Position;

Position pos[12];
int pcnt;
int Graph[12][12];
int DP[12][1<<12];

int bitcount(int x){
	int i;
	int cnt = 0;
	if((x & 1)==1)
		cnt++;
	for(i=1;i<12;i++){
		x >>=1;
		if((x & 1) == 1)
			cnt++;
	}
	return cnt;
}

void TSP(){
	int i,j,k,s,min,tmp,buf,total;
	total = 1<<pcnt;
	for(i=1;i<=pcnt;i++)
		DP[i][0] = Graph[i][0];
	for(k=1;k<pcnt;k++)
		for(s=1;s<total;s++)
			if(bitcount(s) == k)
				for(i=1;i<=pcnt;i++)
					if((s & (1<<(i-1))) == 0){
						min = 100000000;
						for(j=1;j<=pcnt;j++)
							if((s & (1<<(j-1))) != 0){
								tmp = s & (((1<<pcnt)-1) ^ (1 <<(j-1)));
								buf = Graph[i][j] + DP[j][tmp];
								if(buf < min)
									min = buf;
							}
						DP[i][s] = min;
					}
	min = 100000000;
	for(i=1;i<=pcnt;i++){
		tmp = ((1<<pcnt)-1) ^ (1<<(i-1));
		buf = Graph[0][i]+DP[i][tmp];
		if(buf < min)
			min = buf;
	}
	printf("The shortest path has length %d\n",min);
}

int main(){
	int i,j,s,t,tmp,buf;
	int N;
	scanf("%d",&N);
	for(i=0;i<N;i++){
		memset(Graph,0x7f,sizeof(Graph));
		memset(DP,0,sizeof(DP));
		scanf("%d %d",&tmp,&buf);
		scanf("%d %d",&pos[0].r,&pos[0].c);
		scanf("%d",&pcnt);
		for(j=1;j<=pcnt;j++)
			scanf("%d %d",&pos[j].r,&pos[j].c);
		for(s=0;s<=pcnt;s++)
			for(t=s+1;t<=pcnt;t++){
				int tmp;
				tmp = abs(pos[s].r-pos[t].r)+abs(pos[s].c-pos[t].c);
				Graph[s][t] = tmp;
				Graph[t][s] = tmp;
			}
		TSP();
	}
	return 0;
}