思路

设dp(i,j)表示对图的遍历情况为i的二进制数时走到点j的最短路。考虑什么状态可以更新dp(i,j)。 由于每个点只能被经过一次，设更新i的状态为k，那么显然i的第j位为1，k的第j位为0，并且除此之外k和i没有别的不同。所以我们不需要枚举k，只需i^(1<<j)即可。如果k能够更新i，那么肯定是从k的情况时经过的点走过来，也就是k中有1的位置。那么： dp(i,j)=Min{dp(iXOR(1<<j),k)}

其中k和i满足上述的所有条件。

#include<stdio.h>
#include <string.h>
#define MAX 0x7fffffff
int min,n,map[42][42],dis[42];
bool used[42];
void search(int a,int b,int c)
 {
    if (b==n){
        if (map[a][1]+c<min)min=map[a][1]+c;
        return;
    }

    if(c+dis[a]>min)
      return;
    for (int i=1;i<=n;i++)
        if (!used[i]&&i!=a)
            {
                 used[i]=true;
                 search(i,b+1,c+map[a][i]);            
                 used[i]=false;
             }    
 }

void dijk()
 {
     int sel;
     for (int i=1;i<=n;i++) 
         dis[i]=MAX;  
    dis[1]=0;

    for (int i=1;i<=n;i++){
         min=MAX;
         for (int j=1;j<=n;j++)
             if (!used[j]&&dis[j]<min) {
                 min=dis[j];
                 sel=j;
             }
        used[sel]=true;
    for (int j=1;j<=n;j++)
         if (j!=sel)
             if (dis[sel]+map[sel][j]<dis[j])
                 dis[j]=dis[sel]+map[sel][j];        
   }
  memset(used,0,sizeof(used));
 }

int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
            scanf("%d",&map[i][j]);
    dijk();
    min=MAX;
    used[1]=true;
    search(1,1,0);
    printf("%d\n",min);
    fclose(stdout);
    return 0;    
}