TSP template

TSP2.cpp

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 15;
int n, dis[maxn][maxn], dp[maxn][1 << maxn];
int main(){
   while(scanf("%d", &n) == 1){
	memset(dp, 0x3f, sizeof(dp));
	// input a matrix represent the each dot-to-dot distance  
	for(int i = 0; i < n; i++){
	    for(int j = 0; j < n; j++){
		scanf("%d", &dis[i][j]);
	    }
	    dp[i][0] = dis[0][i];
	}

	// 轉移 dp(i, s) = min(dp(j, s - {j}) + dist(i, j) | j 屬於 s)
	// d(i, s)代表目前在城市 i , 還須造訪集合S的城市各一次後回到城市0長度
	for(int s = 0; s < (1 << n); s++){
	    for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
		    if(s & (1 << j)){
			dp[i][s] = min(dp[i][s], dp[j][s ^ (1 << j)] + dis[i][j]);
		    }
		}
	    }
	}
	printf("%d\n", dp[0][(1 << n) - 1]);

   } 
}