思路：和黑书上的跳舞机类似
#include<map> #include<set> #include<cmath> #include<queue> #include<cstdio> #include<vector> #include<string> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> #define Maxn 31 #define Maxm 100010 #define LL __int64 #define Abs(x) ((x)>0?(x):(-x)) #define lson(x) (x<<1) #define rson(x) (x<<1|1) #define inf 0x7fffffff #define Mod 1000000007 using namespace std; int dp[Maxn][Maxn][Maxn][Maxn]; int dis[Maxn][Maxn]; int main() { int t,n,i,j,x,k,r; scanf("%d",&t); while(t--){ memset(dis,0,sizeof(dis)); memset(dp,48,sizeof(dp)); scanf("%d",&n); for(i=1;i<n;i++){ for(j=i+1;j<=n;j++){ scanf("%d",&x); dis[i][j]=dis[j][i]=x; } } memset(dp[1],0,sizeof(dp[1])); for(i=2;i<=n;i++){ for(j=1;j<=i-1;j++){ for(k=1;k<=i-1;k++){ for(r=1;r<=i-1;r++){ dp[i][i][k][r]=min(dp[i][i][k][r],dp[i-1][j][k][r]+dis[j][i]); dp[i][j][i][r]=min(dp[i][j][i][r],dp[i-1][j][k][r]+dis[k][i]); dp[i][j][k][i]=min(dp[i][j][k][i],dp[i-1][j][k][r]+dis[r][i]); } } } } int ans=100000000; for(i=1;i<=n;i++){ for(j=1;j<=n;j++){ for(k=1;k<=n;k++){ ans=min(dp[n][i][j][k],ans); } } } printf("%d\n",ans); } return 0; }