这题卡了一天 刚开始没考虑第一个传的和最后一个传的 感觉挺简单 啪啪的敲完 居然还过了17组数据。。
正解：dp数组一维保存状态 一维保存当前传到了谁 再枚举是由谁传过来的 这样可以保证正确性
1 #include <iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<stdlib.h> 6 using namespace std; 7 #define INF 0xfffffff 8 #define M 100010 9 int dp[M][20],a[20][20],q[2][M],f[M]; 10 int main() 11 { 12 int i,j,k,n; 13 while(scanf("%d",&n)!=EOF) 14 { 15 memset(f,0,sizeof(f)); 16 for(i = 1; i <= n ; i++) 17 for(j = 1; j <= n ;j++) 18 scanf("%d",&a[i][j]); 19 int ans = INF; 20 for(i = 0 ; i <= n ;i++) 21 for(j =0 ; j <= 1<<n ;j++) 22 dp[j][i] = INF; 23 for(i = 0 ; i < n ; i++) 24 { 25 q[1][i+1] = 1<<i; 26 dp[1<<i][i+1] = 0; 27 } 28 k = n; 29 for(i = 2; i <= n ;i++) 30 { 31 int tt = 0; 32 for(j = 1 ; j <= k ; j++) 33 { 34 for(int e = 0 ; e < n ; e++) 35 { 36 for(int o = 0 ; o < n ; o++) 37 { 38 if(((~q[(i-1)%2][j])&(1<<o))==0) 39 continue; 40 if(o!=e) 41 { 42 dp[q[(i-1)%2][j]+(1<<o)][o+1] = min(dp[q[(i-1)%2][j]+(1<<o)][o+1],dp[q[(i-1)%2][j]][e+1]+a[e+1][o+1]); 43 } 44 if(!f[q[(i-1)%2][j]+(1<<o)]) 45 { 46 tt++; 47 q[i%2][tt] = q[(i-1)%2][j]+(1<<o); 48 f[q[(i-1)%2][j]+(1<<o)] = 1; 49 } 50 } 51 } 52 } 53 k = tt; 54 } 55 for(i = 1; i <= n ; i++) 56 ans = min(ans,dp[(1<<n)-1][i]); 57 printf("%d ",ans); 58 } 59 return 0; 60 }