HDU_3001

    相比于普通的TSP问题，这个题加了“每个点之多经过两次”的限制，因此改用三进制表示每个点的状态就可以了。

#include
     
      #include
      
       #include
       
        #define INF 0x3f3f3f3f#define MAXD 15#define ST 59049int N, M, D, g[MAXD][MAXD], f[ST][MAXD], ANS;int bit[] = {
   1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049};void init(){    int i, x, y, z;    memset(g, 0x3f, sizeof(g));    for(i = 0; i < M; i ++)    {        scanf("%d%d%d", &x, &y, &z), -- x, -- y;        if(z < g[x][y]) g[x][y] = g[y][x] = z;        }}int can(int st){    for(int i = 0; i < N; i ++, st /= 3) if(st % 3 == 0) return 0;    return 1;}void solve(){    int i, j, k, n, t;    for(i = 0, D = 1; i < N; i ++) D *= 3;    ANS = INF;    for(i = 0; i < D; i ++)        for(j = 0; j < N; j ++) f[i][j] = INF;    for(i = 0; i < N; i ++)        f[bit[i]][i] = 0;    for(i = 0; i < D; i ++)        for(j = 0; j < N; j ++)            if(f[i][j] != INF)            {                for(k = 0, t = i; k < N; k ++, t /= 3)                    if(t % 3 < 2)                        f[i + bit[k]][k] = std::min(f[i + bit[k]][k], f[i][j] + g[j][k]);                if(can(i)) ANS = std::min(ANS, f[i][j]);            }    printf("%d\n", ANS == INF ? -1 : ANS);}int main(){    while(scanf("%d%d", &N, &M) == 2)    {        init();        solve();        }    return 0;    }