DISNEY2 - Công viên Disneyland (version 2)
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][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();
}