状态压缩 CSU1129 送货到家

多组数据 n

n*n 邻接矩阵

dp[i][j] 以i结束的到j状态的最短的路径

过的有点莫名

#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<math.h>

using namespace std;

#define MAXN 1<<15
#define inf 100000000
int dp[16][MAXN+2];
int x[16][16];

int main()
{
    int n;

    while(scanf("%d",&n)!=EOF)
    {
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                scanf("%d",&x[i][j]);
        int en=1<<n;
        for(int i=0;i<n;i++)
            for(int j=0;j<en;j++)
                dp[i][j]=inf;
        dp[0][0]=0;
        for(int i=0;i<en;i++)
        {
            for(int j=0;j<n;j++)
            {
                for(int k=0;k<n;k++)  //转移一下 没出现过这条边又存在
                {
                    if((!(i&(1<<k)))&&x[j][k])
                        dp[k][i|(1<<k)]=min(dp[k][i|(1<<k)],dp[j][i]+x[j][k]);
                }
            }
        }
        en--;
        if(dp[0][en]==inf)
            printf("NoAnswer
");
        else
            printf("%d
",dp[0][en]);
    }
    return 0;
}