DISNEY1 - Công viên Disneyland (version 1)

Tác giả: hieult

Ngôn ngữ: C++

#include <stdio.h>
//#include <conio.h>
#define  oo 10000000;

int n;
int BestConfig,F[202][202],a[202][202];

void Enter()
{
    int i,j;
    scanf("%d",&n);
    for( i=1;i<=n;i++)
        for( j=1;j<=n;j++)
        {
        scanf("%d",&a[i][j]);
        F[i][j]= oo;
        }
}

int min(int a,int b)
{
    if(a<b) return a;
    else return b;
}

void Optimize()
{
    int i,j,k;
    F[2][1] = a[1][2];
    F[1][2] = a[1][2];
    F[2][2] = 2*a[1][2];
    for(i=2;i<=n;i++)
        for(j=1;j<=i;j++)
        {
                F[i+1][j] = min(F[i+1][j],F[i][j]+a[i][i+1]);
                F[j][i+1] = F[i+1][j];
                F[i][j+1] = min(F[i][j+1],F[i][j]+a[j][j+1]);
                F[j+1][i] = F[i][j+1];
                F[i][i+1] = min(F[i][i+1],F[i][j]+a[j][i+1]);
                F[i+1][i] = F[i][i+1];
        }
}
void PrintResult()
{
    int i;
    BestConfig = oo;
    for(i=1;i<=n;i++)
        if( BestConfig>F[n][i]+a[n][1]+a[i][1])
            BestConfig = F[n][i]+a[n][1]+a[i][1];
    printf("%d",BestConfig);
}
int main()
{
    //freopen("DISNEY1.in","r",stdin);
    Enter();
    if(n==1) printf("0");
    else
    {             
            Optimize();
            PrintResult();
    }
   // getch();
}

Download