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; }