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

## Re:为什么不是0MS?

Posted by CSU_ACM1174 at 2011-08-04 14:49:58 on Problem 1695
In Reply To:为什么不是0MS? Posted by:cgp2001 at 2007-12-16 10:21:54
```> 哪位大牛帮我看下，如何优化到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: