sicily 1404 第一道 状态DP

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;#define check_i(i, node) ((1<<i) & node)    //node第i位是不是有值，含第0位
#define MX 0x7f7f7f7fint n, w[11][11];
int dp[2<<10][11];int main()
{//freopen("1.txt", "r", stdin);while(scanf("%d", &n) && n){	memset(dp, 0x7f, sizeof(dp));for(int i = 0;i <= n;i++)for(int j = 0;j <= n;j++)scanf("%d", &w[i][j]);for(int i = 0;i <= n;i++)for(int j = 0;j <= n;j++)for(int k = 0;k <= n;k++)if(w[j][k] > w[j][i] + w[i][k])w[j][k] = w[j][i] + w[i][k];int mx = (1<<n+1)-1;dp[0][0] = 0;for(int i = 0; i <= n;i++){dp[(1<<i)][i] = w[0][i];}for(int i = 1; i <= mx;i++){for(int j = 0;j <= n;j++){if(check_i(j, i)){int k = (i & (~(1<<j)));if(i == (1<<j)) break;for(int z = 0;z <= n;z++){if(check_i(z, k) && dp[i][j] > dp[k][z] + w[z][j])dp[i][j] = dp[k][z] + w[z][j];					}}}}printf("%d\n", dp[mx][0]);}
}