题目链接：点击打开链接

题目大意：有n个城市。在n个城市之间有m条双向路。每条路有一个距离。如今问从1号城市去游览其他的2到n号城市最后回到1号城市的最短路径（保证1能够直接或间接到达2到n）。（n<=16）

首先用floyd跑出随意一点到其它点最短路。

从n小于等于16就能够看出用状压，从1点開始，dp[i][j]当前经过了i中为1的城市。最后经过的城市是j，不断维护。最后得到dp[1<<n-1][j]+dis[j][1]的距离最短的值。

#include <iostream>

#include <string.h>

#include <math.h>

#include <queue>

#include <algorithm>

#include <stdlib.h>

#include <map>

#include <set>

#include <stdio.h>

#include <time.h>

using namespace std;

#define LL __int64

#define pi acos(-1.0)

#pragma comment(linker, "/STACK:1024000000")

const int mod=1e9+7;

const int INF=0x3f3f3f3f;

const double eqs=1e-9 ;

int Map[20][20] ;

int dp[200000][20] , dis[20] ;

int main() {

    int t , n , m ;

    int i , j , w , k , min1 ;

    scanf("%d", &t) ;

    while( t-- ) {

        scanf("%d %d", &n, &m) ;

        memset(Map,INF,sizeof(Map)) ;

        while( m-- ) {

            scanf("%d %d %d", &i, &j, &w) ;

            i-- ; j-- ;

            if( Map[i][j] > w )

                Map[i][j] = Map[j][i] = w ;

        }

        for(i = 0 ; i < n ; i++) Map[i][i] = 0 ;

        for(k = 0 ; k < n ; k++) {

            for(i = 0 ; i < n ; i++) {

                for(j = 0 ; j < n ; j++) {

                    Map[i][j] = min(Map[i][j],Map[i][k]+Map[k][j]) ;

                }

            }

        }

        memset(dp,INF,sizeof(dp)) ;

        memset(dis,INF,sizeof(dis)) ;

        dp[1][0] = 0 ;

        dis[0] = 0 ;

        m = 1<<n ;

        for(i = 1 ; i < m ; i++) {

            for(j = 0 ; j < n ; j++) {

                if( dp[i][j] == INF ) continue ;

                for(k = 0 ; k < n ; k++) {

                    if( (i&(1<<k)) || Map[j][k] == INF ) continue ;

                    if( dp[ i|(1<<k) ][k] > dp[i][j]+Map[j][k] ) {

                        dp[ i|(1<<k) ][k] = dp[i][j]+Map[j][k] ;

                        dis[k] = min(dis[k],dp[ i|(1<<k) ][k]) ;

                    }

                }

            }

        }

        min1 = INF ;

        for(i = 0 ; i < n ; i++) {

            min1 = min(min1,dp[m-1][i]+dis[i]) ;

        }

        printf("%d\n", min1) ;

    }

    return 0 ;

}