Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 为什么不是0MS?

Posted by cgp2001 at 2007-12-16 10:21:54 on Problem 1695
```哪位大牛帮我看下，如何优化到0MS?
#define INF  (1<<29)
#include "stdio.h"
int F[2][31][31][31];
int path[31][31];
int M,N;
int main(int argc, char* argv[])
{
int i,j,k,l;
scanf("%d",&M);
while (M--)
{
scanf("%d",&N);
for(i=1;i<=N;++i)
for(j=i+1;j<=N;++j)
{
scanf("%d",&path[i][j]);
path[j][i]=path[i][j];
}
for(i=0;i<=1;++i)
for(j=1;j<=N;++j)
for(k=1;k<=N;++k)
for(l=1;l<=N;++l)
F[i][j][k][l]=INF;
F[1][1][1][1]=0;
for(i=2;i<=N;++i)
{
for(j=1;j<i;++j)
for(k=1;k<i;++k)
for(l=1;l<i;++l)
if(F[(i-1)%2][j][k][l] != INF)
{
if(F[i%2][i][k][l]>F[(i-1)%2][j][k][l]+path[j][i])
F[i%2][i][k][l]=F[(i-1)%2][j][k][l]+path[j][i];
if( F[i%2][j][i][l]>F[(i-1)%2][j][k][l]+path[k][i])
F[i%2][j][i][l]=F[(i-1)%2][j][k][l]+path[k][i];
if(F[i%2][j][k][i]>F[(i-1)%2][j][k][l]+path[l][i])
F[i%2][j][k][i]=F[(i-1)%2][j][k][l]+path[l][i];
}
for(j=1;j<=N;++j)
for(k=1;k<=N;++k)
for(l=1;l<=N;++l)
F[(i-1)%2][j][k][l]=INF;
}
int minMIN=INF;
for(i=1;i<=N;++i)
for(j=1;j<=N;++j)
for(k=1;k<=N;++k)
if(minMIN>F[N%2][i][j][k])
minMIN=F[N%2][i][j][k];
printf("%d\n",minMIN);
}
return 0;
}

```

Followed by: