地址：

题意：n（最多10）个城市，可以从任意城市出发，每个城市最多走两次，问最短路径。

mark：TSP问题，由于最多走两次，所以是三进制状态压缩DP，第一次写，很艰难。

　　　可以转换成任意进制的~

代码：

#include 
     
      #include 
      
       #include 
       
        const int M = 67149;const int inf = 0x3f3f3f3f;int dp[70000][15];int adj[15][15];int three[15];int base[70000][15];int n,m;int min(int a, int b) {
   return a < b ? a : b;}void init()       //预处理，特别注意的是由于这里转换成对应禁制后的数是反过来的！！！ {    int i,j,k;    three[0] = 1;    for(i = 1; i < 11; i++)        three[i] = three[i-1]*3;    for(i = 0; i < three[10]; i++)    {        j = i;        k = 0;        while(j)        {            base[i][k++] = j%3;            j /= 3;        }    }}void add(int a, int b, int c){    int s = 0,i;    for(i = n-1; i >= 0; i--)    {        s = 3*s+base[a][i];        if(i == c) s += 1;    }    dp[s][c] = min(dp[s][c], dp[a][b]+adj[b][c]);}bool pd(int a){    int i;    for(i = 0; i < n; i++)        if(!base[a][i]) return 0;    return 1;}int main(){    int a,b,c,min1;    int i,j,k;    init();    while(~scanf("%d%d", &n, &m))    {        memset(adj, 0x3f, sizeof(adj));        for(i = 0; i < m; i++)        {            scanf("%d%d%d", &a, &b, &c);            a--, b--;            adj[a][b] = adj[b][a] = min(c, adj[a][b]);        }        memset(dp, 0x3f, sizeof(dp));        i = 1;        for(j = 0; j < n; j++)    //由于数是反过来的，所以j也是对应的。         {            dp[i][j] = 0;            i *= 3;        }        for(k = 1; k < three[n]; k++)        {            if(pd(k)) continue;            for(i = 0; i < n; i++)            {                if(dp[k][i] == inf) continue;                for(j = 0; j < n; j++)                {                    if(i == j || base[k][j] == 2 || adj[i][j] == inf) continue;                    add(k, i, j);                }            }        }        min1 = inf;        for(i = 0; i < three[n]; i++)        {            if(!pd(i)) continue;            for(j = 0; j < n; j++)                min1 = min(dp[i][j], min1);        }        printf("%d\n", min1 == inf ? -1 : min1);    //别忘记还有-1的情况……    }    return 0;}