#define int_m 2000000000
int bw[1001][17][17][17],array_a[1001],array_b[1001],f[17][17],n;
int min(int a,int b)
{
if(a>b)
return b;
return a;
}
void cal()
{
int ans,tt,i,j,k;
ans=int_m;
for(tt=1;tt<=n;tt++)
for(i=1;i<=16;i++)
for(j=1;j<=16;j++)
for(k=1;k<=16;k++)
bw[n][i][j][k]=int_m;
bw[0][array_b[1]][1][1]=0;
bw[0][1][array_b[1]][1]=0;
bw[0][1][1][array_b[1]]=0;
for(tt=2;tt<=n;tt++)
{
for(i=1;i<=16;i++)
for(j=1;j<=16;j++)
{
bw[tt][array_b[tt]][j][array_b[tt-1]]=min(bw[tt][array_b[tt]][j][array_b[tt-1]],bw[tt-1][i][j][array_b[tt-1]]+f[i][array_b[tt]]);
bw[tt][i][array_b[tt]][array_b[tt-1]]=min(bw[tt][i][array_b[tt]][array_b[tt-1]],bw[tt-1][i][j][array_b[tt-1]]+f[j][array_b[tt]]);
bw[tt][i][j][array_b[tt]]=min(bw[tt][i][j][array_b[tt]],bw[tt-1][i][j][array_b[tt-1]]+f[array_b[tt-1]][array_b[tt]]);
bw[tt][array_b[tt]][array_b[tt-1]][j]=min(bw[tt][array_b[tt]][array_b[tt-1]][j],bw[tt-1][i][array_b[tt-1]][j]+f[i][array_b[tt]]);
bw[tt][i][array_b[tt-1]][array_b[tt]]=min(bw[tt][i][array_b[tt-1]][array_b[tt]],bw[tt-1][i][array_b[tt-1]][j]+f[j][array_b[tt]]);
bw[tt][i][array_b[tt]][j]=min(bw[tt][i][array_b[tt]][j],bw[tt-1][i][array_b[tt-1]][j]+f[array_b[tt-1]][array_b[tt]]);
bw[tt][array_b[tt-1]][array_b[tt]][j]=min(bw[tt][array_b[tt-1]][array_b[tt]][j],bw[tt-1][array_b[tt-1]][i][j]+f[i][array_b[tt]]);
bw[tt][array_b[tt-1]][i][array_b[tt]]=min(bw[tt][array_b[tt-1]][i][array_b[tt]],bw[tt-1][array_b[tt-1]][i][j]+f[j][array_b[tt]]);
bw[tt][array_b[tt]][i][j]=min(bw[tt][array_b[tt]][i][j],bw[tt-1][array_b[tt-1]][i][j]+f[array_b[tt-1]][array_b[tt]]);
}
}
for(i=1;i<=16;i++)
for(j=1;j<=16;j++)
for(k=1;k<=16;k++)
if(bw[n][i][j][k]<ans)
ans=bw[n][i][j][k];
printf("%d\n",ans);
}
void qsort(int l,int r)
{
if(l>=r)
return ;
int i=l,j=r-1,k,s1,s2;
k=r;
s1=array_a[r];
s2=array_b[r];
while(i<j)
{
for(;i<=j;i++)
if(array_a[i]>s1)
{
array_a[k]=array_a[i];
array_b[k]=array_b[i];
k=i;
break;
}
for(;j>i;j--)
if(array_a[j]<s1)
{
array_a[k]=array_a[j];
array_b[k]=array_b[j];
k=j;
break;
}
}
array_a[k]=s1;
array_b[k]=s2;
qsort(l,k-1);
qsort(k+1,r);
}
void getn()
{
int t,i,j,k;
scanf("%d",&t);
for(i=1;i<=t;i++)
{
scanf("%d",&n);
for(j=1;j<=n;j++)
scanf("%d%d",&array_a[j],&array_b[j]);
for(j=1;j<=16;j++)
for(k=1;k<=16;k++)
scanf("%d",&f[j][k]);
qsort(1,n);
cal();
}
}
int main()
{
getn();
return 0;
}
我的程序放上去无输出。这是为什么?
我无奈了。
仔细看题目!!!
引用“接下来有三组格式相同的输入,都是一个16*16的矩阵,表示三根手指中的某根手指从i格子移动到j格子需要F[i][j]的体力。输入保证F[i][j]=F[j][i],并且F[i][i]=0。矩阵中所有元素小于500。”