UVa-10496, TJU-2696, POJ-2907 : Collecting Beepers

問題概要

N<10のTSP。

acceptされたコード

#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX_N = 10 + 1;
const int INF = 1<<29;

int N;
int xs[MAX_N], ys[MAX_N];
int dp[MAX_N][1<<MAX_N];

void init(){
	scanf("%*d%*d%d%d", xs, ys);
	scanf("%d", &N);
	N++;
	for(int i=1; i<N; i++){
		scanf("%d%d", xs+i, ys+i);
	}
}

int solve(){
	for(int i=0; i<N; i++){
		fill(dp[i], dp[i] + (1<<N), INF);
	}

	dp[0][0] = 0;
	for(int bit=0; bit<(1<<N); bit++){
		for(int i=0; i<N; i++)if(dp[i][bit] < INF){
			for(int j=0; j<N; j++){
				int nbit = bit | (1<<j);
				int dist = abs(xs[i] - xs[j]) + abs(ys[i] - ys[j]);
				dp[j][nbit] = min(dp[j][nbit], dp[i][bit] + dist);
			}
		}
	}

	return dp[0][(1<<N)-1];
}

int main(){
	int T;
	scanf("%d", &T);
	for(;T--;){
		init();
		printf("The shortest path has length %d\n", solve());
	}

	return 0;
}