N个城市,M条道路,每条道路有其经过的代价,每一个城市最多能够到达两次,求走全然部城市最小代价,起点随意。

三进制状压。存储每一个状态下每一个城市经过的次数。

转移方程： dp[i+b[k]][k]=Min(dp[i+b[k]][k],dp[i][j]+dis[j][k]);

#include "stdio.h"

#include "string.h"

const int inf=0x3f3f3f3f;

int b[15],mark[60010][15],dp[60010][15],dis[15][15];

int Min(int a,int b)

{

    if (a<b) return a;

    else return b;

}

int main()

{

    int i,j,n,m,k,temp,ans,flag;

    b[0]=1;

    for (i=1; i<=10; i++)

        b[i]=b[i-1]*3;

    for (i=0; i<b[10]; i++) // 记录每种状态下，每一个城市经过的情况。

{

        temp=i;

        for (j=0; j<10; j++)

        {

            mark[i][j]=temp%3;

            temp/=3;

        }

    }

    while (scanf("%d%d",&n,&m)!=EOF)

    {

        memset(dis,inf,sizeof(dis));

        memset(dp,inf,sizeof(dp));

        while (m--)

        {

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

            i--;

            j--;

            if (dis[i][j]>k)

                dis[i][j]=dis[j][i]=k;

        }

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

            dp[b[i]][i]=0;

        ans=inf;

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

        {

            flag=1;

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

            {

                if (mark[i][j]==0) flag=0;

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

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

                    if (k!=j && mark[i][k]<2 && dis[j][k]!=inf)

                        dp[i+b[k]][k]=Min(dp[i+b[k]][k],dp[i][j]+dis[j][k]);

            }

            if (flag==1)

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

                    ans=Min(ans,dp[i][j]);

        }

        if (ans==inf) printf("-1\n");

        else printf("%d\n",ans);

    }

    return 0;

}