1695.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include"iostream.h"
#define time TTTTSFG

int map[31][31];
int time[31][31][31];


int main()
{int i,j,k,t,n,s,a,b;
	cin>>t;
	while(t--)
	{cin>>n;
	for(i=1;i<=n;i++)
	for(j=i+1;j<=n;j++)
		cin>>map[i][j];
	
	time[1][1][1]=0;
	for(i=1;i<=n;i++)
	for(j=i;j<=n;j++)
	for(k=j;k<=n;k++)
	{if(i==1&&j==1&&k==1)continue;
	s=30000;
	for(a=1;a<i;a++)
		   if(s>time[a][j][k]+map[a][i])s=time[a][j][k]+map[a][i];
	
	if(i==j==k){time[i][j][k]=s;continue;}
	
	for(b=i;b<j;b++)
	           if(s>time[i][b][k]+map[b][j])s=time[i][b][k]+map[b][j];	
	 if(j==k){time[i][j][k]=s;continue;}
		 
	 if(j==k-1){for(a=1;a<i;a++)
		 if(s>time[a][i][j]+map[a][k])s=time[a][i][j]+map[a][k];
		    for(b=i;b<=j;b++)
		 if(s>time[i][b][j]+map[b][k])s=time[i][b][j]+map[b][k];	    		 time[i][j][k]=s;  }	
	 else {if(s>time[i][j][k-1]+map[k-1][k])s=time[i][j][k-1]+map[k-1][k];
	 	time[i][j][k]=s;}
	}	
	
/*	for(i=1;i<=n;i++)
	for(j=i;j<=n;j++)
	for(k=j;k<=n;k++)
	cout<<i<<' '<<j<<' '<<k<<':'<<time[i][j][k]<<endl;	*/
	s=30000;
	for(i=1;i<=n;i++)
	for(j=i;j<=n;j++)
	if(time[i][j][n]<s)s=time[i][j][n];
	
	cout<<s<<endl;
	}
return 0;
}