# Classic Travelling Salesman Problem ( DP )

O( 2^N * N^2 )
Given a weighed graph, we are to find the minimum distance of starting from some node, travelling through each other node exactly once, and coming back to the start. Since that will form a cycle, we can start at any arbitrary node and go through each other nodes once, then add the cost between the last visited node and that start to calculate the cost.
dp[ S ][ u ] : Minimum cost of having been in cities of set S, with u being the last visited city

```void solve(){
int N, M; cin >> N >> M;
vvl adj_dis( N, vl( N, LINF ) );
for( int i = 0; i < M; ++i ){
int u, v; ll w; cin >> u >> v >> w;
upmin( adj_dis[ u - 1 ][ v - 1 ], w );
upmin( adj_dis[ v - 1 ][ u - 1 ], w );
}
vvl dp( 1 << N, vl( N, LINF ) );
vvi pre( 1 << N, vi( N, -1 ) );
dp[ 1 << 0 ][ 0 ] = 0;
for( int S = 0; S < 1 << N; ++S )
for( int i = 0; i < N; ++i ) if( S >> i & 1 )
for( int j = 0; j < N; ++j ) if( not ( S >> j & 1 ) )
if( upmin( dp[ S | 1 << j ][ j ], dp[ S ][ i ] + adj_dis[ i ][ j ] ) )
pre[ S | 1 << j ][ j ] = i;
ll min_cost = LINF;
vi ans;
for( int i = 0; i < N; ++i )
if( upmin( min_cost, dp[ ( 1 << N ) - 1 ][ i ] + adj_dis[ i ][ 0 ] ) ){
vi city;
for( int S = ( 1 << N ) - 1, u = i; ; ){
city.push_back( u );
int pu = pre[ S ][ u ];
if( pu == -1 ){
break;
}
S ^= 1 << u;
u = pu;
}
swap( ans, city );
}
if( min_cost == LINF )
cout << -1 << endl;
else{
cout << min_cost << endl;
for( int i = ans.size() - 1; i >= 0; --i )
cout << ans[ i ] + 1 << " \n"[ i == 0 ];
}
}
```